text:
import Base.show
"""
    AbstractVertex
Vertex base type
"""
abstract type AbstractVertex end

Base.Broadcast.broadcastable(v::AbstractVertex) = Ref(v)

"""
    inputs(v::AbstractVertex)

Return an Array of vertices which are input to the given vertex.

# Examples
```julia-repl
julia> using NaiveNASlib

julia> inputs(CompVertex(identity, InputVertex(1)))
1-element Array{AbstractVertex,1}:
 InputVertex(1, [CompVertex(identity)])
```
"""
function inputs end

"""
    outputs(v::AbstractVertex)

Return an Array of vertices for which the given vertex is input to.

# Examples
```julia-repl
julia> using NaiveNASlib

julia> iv = InputVertex(1);

julia> cv = (CompVertex(identity, iv));

julia> outputs(iv)
1-element Array{AbstractVertex,1}:
 CompVertex(identity, [InputVertex(1)], [])
```
"""
function outputs end

"""
    InputVertex

Acts as a source of data to the graph and therefore does not need
any input vertices to feed it

# Examples
```julia-repl
julia> using NaiveNASlib

julia> InputVertex(1)
InputVertex(1)

julia> InputVertex("input")
InputVertex("input")
```
"""
struct InputVertex <: AbstractVertex
    name
end
clone(v::InputVertex, ins::AbstractVertex...;cf=clone) = isempty(ins) ? InputVertex(cf(v.name,cf=cf)) : error("Input vertex got inputs: $(ins)!")
inputs(v::InputVertex)::AbstractArray{AbstractVertex,1} = []
(v::InputVertex)(x...) = error("Missing input $(v.name) to graph!")

"""
    CompVertex

Maps input from input vertices to output. Must have at least one input vertex

# Examples
```julia-repl
julia> using NaiveNASlib

julia> CompVertex(+, InputVertex(1), InputVertex(2))
CompVertex(+, [InputVertex(1), InputVertex(2)])

julia> CompVertex(x -> 4x, InputVertex(1))(2)
8

julia>CompVertex(*, InputVertex(1), InputVertex(2))(2,3)
6
```
"""
struct CompVertex <: AbstractVertex
    computation
    inputs::AbstractVector{AbstractVertex}
end
CompVertex(c, ins::AbstractVertex...) = CompVertex(c, collect(ins))
clone(v::CompVertex, ins::AbstractVertex...;cf=clone) = CompVertex(cf(v.computation, cf=cf), ins...)
inputs(v::CompVertex)::AbstractVector{AbstractVertex} = v.inputs
(v::CompVertex)(x...) = v.computation(x...)

## Stuff for displaying information about vertices

# To avoid too verbose console output
function Base.show(io::IO, vs::Array{AbstractVertex,1})
    print(io, "[")
    for (i, v) in enumerate(vs)
        show_less(io, v)
        i != length(vs) && print(io, ", ")
    end
    print(io, "]")
end
show_less(io::IO, v::AbstractVertex) = summary(io, v)

show_less(io::IO, v::InputVertex) = show_less(io, v, v.name)
show_less(io::IO, v::InputVertex, name::String) = print(io, name)
show_less(io::IO, v::InputVertex, name) = print(io, "InputVertex($(v.name))")

function show_less(io::IO, v::CompVertex)
    summary(io, v)
    print(io, "(")
    show(io, v.computation)
    print(io, ")")
end

function Base.show(io::IO, v::CompVertex)
    show_less(io, v)
    print(io, ", inputs=")
    show(io, inputs(v))
end

# Stuff for logging

name(v::AbstractVertex) = summary(v)
name(v::InputVertex) = v.name

# Don't call the mental hospital about the stuff below just yet!
# Let me explain: Debugging this library can be quite confusing due to the recursive nature of how changes propagate. To lessen the pain, is important to be able to format the vertices into something readable which carries the relevant information. As this varies from case to case it is highly customizable what can be printed and what can not.

abstract type InfoStr end
Base.Broadcast.broadcastable(i::InfoStr) = Ref(i)
Base.show(io::IO, istr::T) where T<:InfoStr = print(io, T)
clone(i::InfoStr, cf=clone) = i

struct RawInfoStr <: InfoStr end
struct NameInfoStr <: InfoStr end
struct BracketInfoStr <: InfoStr
    infostr::InfoStr
end

struct InputsInfoStr <: InfoStr
    infostr::InfoStr
end
InputsInfoStr() = BracketInfoStr(InputsInfoStr(NameInfoStr()))

struct PrefixedInfoStr <: InfoStr
    prefix
    infostr::InfoStr
end

struct ComposedInfoStr <: InfoStr
    infostrs::AbstractVector{<:InfoStr}
end
ComposedInfoStr(infostrs...) = ComposedInfoStr(collect(infostrs))
NameAndInputsInfoStr() = ComposedInfoStr(NameInfoStr(), PrefixedInfoStr("inputs=",  InputsInfoStr()))

function Base.push!(i::ComposedInfoStr, items...)
     push!(i.infostrs, items...)
     return i
 end

infostr(::RawInfoStr, v::AbstractVertex) = replace(string(v), "\"" => "")
infostr(::NameInfoStr, v::AbstractVertex) = name(v)
infostr(i::BracketInfoStr, v::AbstractVertex) = "[" * infostr(i.infostr, v) * "]"
infostr(i::InputsInfoStr, v::AbstractVertex) = join(infostr.(i.infostr, inputs(v)), ", ")
infostr(i::PrefixedInfoStr, v::AbstractVertex) = i.prefix * infostr(i.infostr, v)
infostr(i::ComposedInfoStr, v::AbstractVertex) = join(infostr.(i.infostrs, v), ", ")


text:
"""
    regular_pattern(sz; offset=0, step=1)

Returns a generator with tuples that point to a regular grid pattern.

 ### Arguments:
+ `sz`: size of the underlaying array for which to generate the regular pattern
+ `offset`: offset of the first position. Can be tuple or scalar.
+ `step`: step between the indices. Can be tuple or scalar.

 ## Examples
```jldoctest
julia> MicroscopyTools.regular_pattern((3,3))
Base.Generator{CartesianIndices{2, Tuple{Base.OneTo{Int64}, Base.OneTo{Int64}}}, MicroscopyTools.var"#46#47"{Int64, Int64}}(MicroscopyTools.var"#46#47"{Int64, Int64}(1, 1), CartesianIndex{2}[CartesianIndex(1, 1) CartesianIndex(1, 2) CartesianIndex(1, 3); CartesianIndex(2, 1) CartesianIndex(2, 2) CartesianIndex(2, 3); CartesianIndex(3, 1) CartesianIndex(3, 2) CartesianIndex(3, 3)])

julia> collect(MicroscopyTools.regular_pattern((3,3)))
3×3 Matrix{Tuple{Int64, Int64}}:
 (1, 1)  (1, 2)  (1, 3)
 (2, 1)  (2, 2)  (2, 3)
 (3, 1)  (3, 2)  (3, 3)

julia> collect(MicroscopyTools.regular_pattern((3,3), step=2))
2×2 Matrix{Tuple{Int64, Int64}}:
 (1, 1)  (1, 3)
 (3, 1)  (3, 3)

julia> collect(MicroscopyTools.regular_pattern((3,3), step=2, offset=-1))
2×2 Matrix{Tuple{Int64, Int64}}:
 (-1, -1)  (-1, 1)
 (1, -1)   (1, 1)
```
"""
function regular_pattern(sz; offset=1, step=1) # zero-based
    return (offset .+step.*(Tuple(pos).-1)
            for pos in CartesianIndices(1 .+ (((sz.-1)) .÷ step)))
end

"""
    get_scan_pattern([T=Float64,] sz, pitch=1, step=1; flatten_scan_dims=false)

Generates a scan pattern in N dimensions based on scanning an array of size `sz`
with a scan pitch of `pitch` and stepping by `step`.
The result is an array with `2*length(sz)` dimensions.
Note that the scan needs to be commensurate, implying that `pitch` is an integer multiple of `step`.
"""
 #function get_scan_pattern(dtype::DataType, sz, pitch=1, step=1; flatten_scan_dims=false)
 #    if any(pitch .% step .!= 0)
 #        error("Scan pitch needs to be commensurate with scan step")
 #    end
 #
 #    sz = Tuple(sz)
 #    pitch = Tuple(step)
 #    step = Tuple(step)
 #
 #    scan_sz = pitch .÷ step;
 #    res = zeros(dtype, (sz..., scan_sz...))
 #    for scan_pos in regular_pattern(scan_sz)
 #        for pos in regular_pattern(sz, step=step.*scan_pos, offset=pitch)
 #            res[pos..., scan_pos...] = one(dtype)
 #        end
 #    end
 #    if flatten_scan_dims
 #        return flatten_trailing_dims(res, length(sz)+1);
 #    else
 #        return res
 #    end
 #end
 #
 #function get_scan_pattern(sz, pitch=1, step=1; flatten_scan_dims=false)
 #    MicroscopyTools.get_scan_pattern(Float64, sz, pitch, step,
 #                                     flatten_scan_dims=flatten_scan_dims)
 #end

ext: jl

max_stars_repo_name: JuliaMicroscopy/MicroscopyTools

max_issues_repo_name: JuliaMicroscopy/MicroscopyTools


text:
"""
    Optimize

Basic Powell's method optimizer.

"""
module Optimize

"""
    minbracket(f, a, b, c, epsabs, epsrel, epsdx)

Find a minimum of `f(x)` for `a <= x <= c`.  Uses basic bracketing.

On entry, `f(b) < f(a)` and `f(b) < f(c)`.  Termination when either
`c-a <= epsdx` or the range of `f` on `a`, `b`, `c` satisfies `range
<= epsabs + epsrel*abs(f(b))`.

"""
function minbracket(f, a, b, c, epsabs, epsrel, epsdx)
    minbracket(f, a, f(x), b, f(b), c, f(c), epsabs, epsrel, epsdx)
end

function minbracket(f, a, fa, b, fb, c, fc, epsabs, epsrel, epsdx)
    @assert(fb < fa && fb < fc, "minimize: values must bracket a minimum")

    while c - a > epsdx && ((fc - fb) + (fa - fb))/2.0 > epsabs + epsrel/3.0*(abs(fa) + abs(fb) + abs(fc))
        if fa > fc
            x = a + 0.5*(b-a)
            fx = f(x)

            if fx > fb
                fa = fx
                a = x
            else
                fc = fb
                c = b
                fb = fx
                b = x
            end
        else
            x = b + 0.5*(c-b)
            fx = f(x)

            if fx > fb
                fc = fx
                c = x
            else
                fa = fb
                a = b
                fb = fx
                b = x
            end
        end
    end
    b, fb
end

function find_bounds(f, fx0)
    x0 = -1.0
    x1 = 0.0
    x2 = 1.0

    f0 = f(x0)
    f1 = fx0
    f2 = f(x2)

    while f1 > f2 || f1 > f0
        grad = (f1-f0)/(x1-x0) + (f2-f1)/(x2-x1) - (f2-f0)/(x2-x0)

        if grad > 0.0  # Going to expand to the left
            x0 = x1 - 2.0*(x1-x0)
            f0 = f(x0)
        else # Expand to the right
            x2 = x1 + 2.0*(x2-x1)
            f2 = f(x2)
        end
    end

    x0, f0, x1, f1, x2, f2
end

"""
    minpowell(f, x0, epsabs, epsrel, epsdx)
    minpowell(f, x0, direc, epsabs, epsrel, epsdx)

Returns the `x` that minimises `f` starting from `x0` using Powell's
method.

Termination when change in `f` on iteration is `df <= epsabs +
epsrel*abs(f)` or when the change in `x` satisfies `norm(dx) <=
epsdx`.

The optional `direc` argument gives the initial direction set.
`direc[:,i]` is the `i`th direction for the optimization.
"""
function minpowell(f, x0, epsabs, epsrel, epsdx)
    minpowell(f, x0, eye(size(x0,1)), epsabs, epsrel, epsdx)
end

function minpowell(f, x0, direc, epsabs, epsrel, epsdx)
    n = size(x0, 1)

    df_max = -Inf
    i_max = -1
    fx0 = Inf
    fbest = Inf
    new_direc = copy(direc)
    x = copy(x0)
    for i in 1:n
        dx = direc[:,i]

        function fone(y)
            xx = x + y*dx
            f(xx)
        end

        fone0 = fone(0.0)
        if i == 1
            fx0 = fone0
        end
        a, fa, b, fb, c, fc = find_bounds(fone, fone0)

        y, fy = minbracket(fone, a, fa, b, fb, c, fc, epsabs, epsrel, 0.0)

        fbest = fy

        # Update the scale of new_direc
        x = x + y*dx

        df = fone0 - fy
        if df > df_max
            df_max = df
            i_max = i
        end
    end

    dx = x - x0
    df = fx0 - fbest

    new_direc[:,i_max] = dx / norm(dx)

    if df < epsabs + abs(fbest)*epsrel || norm(dx) < epsdx
        x, fbest
    else
        minpowell(f, x, new_direc, epsabs, epsrel, epsdx)
    end
end

end


text:
using PrettyTables

export CouplerState
export coupler_push!, coupler_pull!, coupler_put!, coupler_get
export coupler_add_field!

mutable struct CplFieldInfo{AT, MD}
    data::AT
    metadata::MD
end

mutable struct CouplerState{DT}
    coupled_fields::DT
end

_fields(coupler::CouplerState) = getfield(coupler, :coupled_fields)

"""
    CouplerState()

Type for holding coupler "state". This is the namespace through which coupled components
communicate. Its role is to provide a level of indirection so that components remain modular
and so that any data communication, interpolation, reindexing/unit conversions and filtering
etc... can be embeded in the intermdediate coupling layer.

A field is exported by one component and imported by one or more other components.
"""
function CouplerState()
    return CouplerState(Dict{Symbol, CplFieldInfo}())
end

"""
    coupler_add_field!(
            coupler::CouplerState,
            fieldname::Symbol,
            fieldvalue,
        )

Add a field to the coupler that is accessible with key `fieldname`.

# Arguments
- `coupler`: coupler object the field is added to.
- `fieldname`: key to access the field in the coupler.
- `fieldvalue`: data array of field values.
"""
function coupler_add_field!(coupler::CouplerState, fieldname::Symbol, fieldvalue, metadata = nothing)
    push!(coupler.coupled_fields, fieldname => CplFieldInfo(fieldvalue, metadata))
end

"""
    coupler_put!(coupler::CouplerState, fieldname::Symbol, fieldvalue)

Sets coupler field `fieldname` to `fieldvalue`.
"""
function coupler_put!(coupler::CouplerState, fieldname::Symbol, fieldvalue)
    cplfield = coupler.coupled_fields[fieldname]

    cplfield.data .= fieldvalue

    return nothing
end

"""
    coupler_push!(coupler::CouplerState, model)

Update coupler with fields retrieved from the coupler.

`coupler_push!` is an adapter function to be implemented for each
model component using the coupler. It should send coupling fields via
`coupler_put!` calls and perform any operations on these fields to prepare
them for the coupler.
"""
function coupler_push!(coupler::CouplerState, model) end

"""
    coupler_get(coupler::CouplerState, fieldname::Symbol)

Retrieve data array corresponding to `fieldname`.

Returns data on the grid specified by `gridinfo` and in the units of `units`. Checks that
the coupler data field is the state at time `datetime`.
"""
function coupler_get(coupler::CouplerState, fieldname::Symbol)
    cplfield = coupler.coupled_fields[fieldname]

    return cplfield.data
end

"""
    coupler_pull!(model, coupler::CouplerState)

Update model with fields retrieved from the coupler.

`coupler_pull!` is an adapter function to be implemented for each
model component using the coupler. It should get coupling fields via
`coupler_get` calls and perform any operations on these fields to prepare
them for use in the component model.
"""
function coupler_pull!(model, coupler::CouplerState) end

# display table of registered fields & their info
function Base.show(io::IO, coupler::CouplerState)
    #=
    ----------------
    |  Field Name  |
    ----------------
    |  :OceanSST   |
    |  :Field2     |
    ----------------
    =#
    fields = _fields(coupler)
    data = Array{Any}(undef, length(fields), 1)
    for (i, k) in enumerate(keys(fields))
        entry = fields[k]
        data[i, :] = [k]
    end
    header = (["Field Name"], [""])
    pretty_table(data, header = header)
end

max_stars_repo_name: CliMA/ClimaCoupler


text:
using ImageMagick
using Images, TestImages, StaticArrays, ImageTracking, ImageView, LinearAlgebra, CoordinateTransformations, Gtk.ShortNames
#=Image Credit:  C. Liu. Beyond Pixels: Exploring New Representations and
#Applications for Motion Analysis. Doctoral Thesis. Massachusetts Institute of
#Technology. May 2009. =#
img1 = load("car2.jpg")
img2 = load("car1.jpg")

algorithm = Farneback(50, estimation_window = 11,
                         σ_estimation_window = 9.0,
                         expansion_window = 6,
                         σ_expansion_window = 5.0)

flow = optical_flow(Gray{Float32}.(img1), Gray{Float32}.(img2), algorithm)

# flow visualization
hsv = visualize_flow(flow, ColorBased(), RasterConvention())

imshow(RGB.(hsv))
save("./optical_flow_farneback.jpg", hsv)


text:
### A Pluto.jl notebook ###
# v0.17.1

using Markdown
using InteractiveUtils

# ╔═╡ cc180e7e-46c3-11ec-3fff-05e1b5c77986
md"""
# Download Data URLs

"""

# ╔═╡ 2385dd3b-15f8-4790-907f-e0576a56c4c0
random_data = rand(UInt8, 30)

# ╔═╡ d8ed6d44-33cd-4c9d-828b-d237d43769f5
# try
# download("asdffads")
# catch e
# 	e
# end |> typeof

# ╔═╡ e1610184-5d16-499b-883e-7ef92f402ebb
function is_inside_pluto(m::Module)
	if isdefined(m, :PlutoForceDisplay)
		return m.PlutoForceDisplay
	else
		isdefined(m, :PlutoRunner) && parentmodule(m) == Main
	end
end

# ╔═╡ b987a8a2-6ab0-4e88-af3c-d7f2778af657
begin
	if is_inside_pluto(@__MODULE__)
		import Pkg

		# create a local environment for this notebook
		# used to install and load PlutoTest
		local_env = mktempdir()
		Pkg.activate(local_env)
		Pkg.add(name="PlutoTest", version="0.2")
		pushfirst!(LOAD_PATH, local_env)

		# activate Pluto's environment, used to load HTTP.jl
		Pkg.activate(Base.current_project(@__FILE__))
		using PlutoTest
	else
		if !isdefined(@__MODULE__, Symbol("@test"))
			macro test(e...) nothing; end
			macro test_throws(e...) nothing; end
			macro test_broken(e...) nothing; end
			macro testset(e...) nothing; end
		end
	end
	import HTTP.URIs
	import Base64
end

# ╔═╡ a85c0c0b-47d0-4377-bc22-3c87239a67b3
"""
```julia
download_cool(url::AbstractString, [path::AbstractString = tempname()]) -> path
```

The same as [`Base.download`](@ref), but also supports [Data URLs](https://developer.mozilla.org/en-US/docs/Web/HTTP/Basics_of_HTTP/Data_URIs).
"""
function download_cool(url::AbstractString, path::AbstractString=tempname())
	if startswith(url, "data:")
		comma_index = findfirst(',', url)

		@assert comma_index isa Int "Invalid data URL."

		metadata_str = url[length("data:")+1:comma_index-1]
		metadata_parts = split(metadata_str, ';'; limit=2)

		if length(metadata_parts) == 2
			@assert metadata_parts[2] == "base64" "Invalid data URL."
		end

		mime = MIME(first(metadata_parts))
		is_base64 = length(metadata_parts) == 2

		data_str = SubString(url, comma_index+1)

		data = is_base64 ?
			Base64.base64decode(data_str) :
			URIs.unescapeuri(data_str)

		write(path, data)
		path
	else
		download(url, path)
	end
end

# ╔═╡ 6e1dd79c-a7bf-44d6-bfa6-ced75b45170a
download_cool_string(args...) = read(download_cool(args...), String)

# ╔═╡ 3630b4bc-ff63-426d-b95d-ae4e4f9ccd88
download_cool_data(args...) = read(download_cool(args...))

# ╔═╡ 6339496d-11be-40d0-b4e5-9247e5199367
@test download_cool_string("data:,Hello%2C%20World%21") == "Hello, World!"

# ╔═╡ bf7b4241-9cb0-4d90-9ded-b527bf220803
@test download_cool_string("data:text/plain,Hello%2C%20World%21") == "Hello, World!"

# ╔═╡ d6e01532-a8e4-4173-a270-eae37c8002c7
@test download_cool_string("data:text/plain;base64,SGVsbG8sIFdvcmxkIQ==") == "Hello, World!"

# ╔═╡ b0ba1add-f452-4a44-ab23-becbc610e2b9
@test download_cool_string("data:;base64,SGVsbG8sIFdvcmxkIQ==") == "Hello, World!"

# ╔═╡ e630e261-1c2d-4117-9c44-dd49199fa3de
@test download_cool_string("data:,hello") == "hello"

# ╔═╡ 4bb75573-09bd-4ce7-b76f-34c0249d7b88
@test download_cool_string("data:text/html,%3Ch1%3EHello%2C%20World%21%3C%2Fh1%3E") == "
Hello, World!
"

# ╔═╡ 301eee81-7715-4d39-89aa-37bffde3557f
@test download_cool_string("data:text/html,") == ""

# ╔═╡ ae296e09-08dd-4ee8-87ac-eb2bf24b28b9
random_data_url = "data:asf;base64,$(
	Base64.base64encode(random_data)
)"

# ╔═╡ 2eabfa58-2d8f-4479-9c00-a58b934638d9
@test download_cool_data(random_data_url) == random_data

# ╔═╡ 525b2cb6-b7b9-436e-898e-a951e6a1f2f1
@test occursin("reactive", download_cool_string("https://raw.githubusercontent.com/fonsp/Pluto.jl/v0.17.1/README.md"))

# ╔═╡ 40b48818-e191-4509-85ad-b9ff745cd0cb
@test_throws Exception download_cool("data:xoxo;base10,asdfasdfasdf")

# ╔═╡ 1f175fcd-8b94-4f13-a912-02a21c95f8ca
@test_throws Exception download_cool("data:text/plain;base10,asdfasdfasdf")

# ╔═╡ a4f671e6-0e23-4753-9301-048b2ef505e3
@test_throws Exception download_cool("data:asdfasdfasdf")

# ╔═╡ Cell order:
# ╟─cc180e7e-46c3-11ec-3fff-05e1b5c77986
# ╠═a85c0c0b-47d0-4377-bc22-3c87239a67b3
# ╠═6339496d-11be-40d0-b4e5-9247e5199367
# ╠═bf7b4241-9cb0-4d90-9ded-b527bf220803
# ╠═d6e01532-a8e4-4173-a270-eae37c8002c7
# ╠═b0ba1add-f452-4a44-ab23-becbc610e2b9
# ╠═e630e261-1c2d-4117-9c44-dd49199fa3de
# ╠═4bb75573-09bd-4ce7-b76f-34c0249d7b88
# ╠═301eee81-7715-4d39-89aa-37bffde3557f
# ╠═2385dd3b-15f8-4790-907f-e0576a56c4c0
# ╠═ae296e09-08dd-4ee8-87ac-eb2bf24b28b9
# ╠═2eabfa58-2d8f-4479-9c00-a58b934638d9
# ╠═525b2cb6-b7b9-436e-898e-a951e6a1f2f1
# ╠═6e1dd79c-a7bf-44d6-bfa6-ced75b45170a
# ╠═3630b4bc-ff63-426d-b95d-ae4e4f9ccd88
# ╠═40b48818-e191-4509-85ad-b9ff745cd0cb
# ╠═1f175fcd-8b94-4f13-a912-02a21c95f8ca
# ╠═a4f671e6-0e23-4753-9301-048b2ef505e3
# ╠═d8ed6d44-33cd-4c9d-828b-d237d43769f5
# ╟─e1610184-5d16-499b-883e-7ef92f402ebb
# ╠═b987a8a2-6ab0-4e88-af3c-d7f2778af657


text:
import SeisIO: get_svn
path = joinpath(Base.source_dir(),"../test/TestHelpers/0_check_deps.jl")
include(path)
include("./check_data.jl")
pkg_check(["DSP", "SeisIO", "IJulia"])
get_svn("https://github.com/jpjones76/SeisIO-TestData/trunk/Tutorial", "DATA")

using IJulia
jupyterlab(dir=joinpath(dirname(dirname(pathof(SeisIO))),"tutorial"))


text:
#abstract type AbstractCachedArray{TO,TI,N,NC,AA} <: AbstractArray{TO,N} end
abstract type AbstractCachedArray{TO,N,TI,NC,AA} <: AbstractArray{TO,N} end

#IndexCartesian is the default, but in case that changes...
Base.IndexStyle(::Type{<:AbstractCachedArray}) = IndexCartesian()

#The four functions below and the update_cache! function may be enough
#to define an interface that's easily extended
parent(A::AbstractCachedArray) = A.parent
cache(A::AbstractCachedArray) = A.cached
current_I(A::AbstractCachedArray) = A.current_I
set_I!(A, inds) = A.current_I = inds

size(A::AbstractCachedArray) = size(parent(A))
axes(A::AbstractCachedArray) = axes(parent(A))

#Return the axes of the parent array corresponding with the cache
#(The first nd_cache dimensions)
cached_axes(A::AbstractCachedArray) = _cached_axes(axes(cache(A)), axes(parent(A)))
_cached_axes(ac, ap) = (first(ap), _cached_axes(Base.tail(ac), Base.tail(ap))...)
_cached_axes(ac::Tuple{}, ap) = ()

#Return the axes of the parent array not included in the cache
#(The last N-nd_cache dimensions)
noncached_axes(A::AbstractCachedArray) = _noncached_axes(axes(cache(A)), axes(parent(A)))
_noncached_axes(ac, ap) = _noncached_axes(Base.tail(ac), Base.tail(ap))
_noncached_axes(ac::Tuple{}, ap) = ap

function update_cache!(A::AbstractCachedArray{T}, inds::NTuple{N, Int}) where {T, N}
    cache(A) .= parent(A)[cached_axes(A)...,inds...]
    set_I!(A, inds)
end

Base.show(io::IO, A::AbstractCachedArray) = print(io, summary(A)*"\n")
Base.show(io::IO, ::MIME"text/plain", A::AbstractCachedArray) = show(io, A)

getindex(A::AbstractCachedArray{TO,N,TI,NC,AA}, I::Vararg{Int,N}) where {TO,N,TI,NC,AA} =
    _getslice(A, _cached_axes(axes(cache(A)), (I...,)), _noncached_axes(axes(cache(A)), (I...,)))

setindex!(A::AbstractCachedArray{TO,N,TI,NC,AA}, v, I::Vararg{Int, N}) where {TO,N,TI,NC,AA} =
    _setslice!(A, v, _cached_axes(axes(cache(A)), (I...,)), _noncached_axes(axes(cache(A)), (I...,)))

function _getslice(A::AbstractCachedArray{TO,N,TI,NC,AA}, cidxs::NTuple{NC,Int}, ncidxs::NTuple{NV,Int}) where {TO,N,TI,NC,AA,NV}
    if current_I(A) != ncidxs
        update_cache!(A, ncidxs)
    end
    return cache(A)[cidxs...] #Assumes the cache and the parent have the same indexing conventions. May be fine since we constructed with similar.
end

function _setslice!(A::AbstractCachedArray{TO,N,TI,NC,AA}, val, cidxs::NTuple{NC,Int}, ncidxs::NTuple{NV,Int}) where {TO,N,TI,NC,AA,NV}
    A.parent[cidxs..., ncidxs...] = val
    if current_I(A) != ncidxs
        update_cache!(A, ncidxs)
    else
        cache(A)[cidxs...] = val
    end
    return A
end


text:
@testset "sl" begin
    Sl1(x) = 0.5*(pi - x)
    Sl2(x) = pi^2/6 - pi/2*x + x^2/4
    Sl3(x) = pi^2/6*x - pi/4*x^2 + x^3/12
    Sl4(x) = pi^4/90 - pi^2/12*x^2 + pi/12*x^3 - x^4/48

    n = 10
    x_min = 0.0
    x_max = 2.0*pi
    data = (x_max - x_min)*rand(Float64, n) + x_min*ones(n)

    for x in data
        @test ≈(ClausenFunctions.sl(1, x), Sl1(x), atol=1e-14)
        @test ≈(ClausenFunctions.sl(2, x), Sl2(x), atol=1e-14)
        @test ≈(ClausenFunctions.sl(3, x), Sl3(x), atol=1e-14)
        @test ≈(ClausenFunctions.sl(4, x), Sl4(x), atol=1e-13)
    end

    for n in vcat(collect(1:31), [1000, 1001])
        data = open(readdlm, joinpath(@__DIR__, "data", "Sl$(n).txt"))

        for r in 1:size(data, 1)
            row      = data[r, :]
            x        = row[1]
            expected = row[2]

            @test ClausenFunctions.sl(n, x) == (-1)^n*ClausenFunctions.sl(n, -x)
            @test ClausenFunctions.sl(n, x) ≈ expected atol=1e-14
        end
    end

    @test_throws DomainError ClausenFunctions.sl(0, 1.0)
    @test_throws DomainError ClausenFunctions.sl(-1, 1.0)
    @test_throws DomainError ClausenFunctions.sl(-2, 1.0)
end


text:
using LinearAlgebra: givensAlgorithm
using Base: @propagate_inbounds

import LinearAlgebra: lmul!, rmul!
import Base: Matrix

@propagate_inbounds is_offdiagonal_small(H::AbstractMatrix{T}, i::Int, tol = eps(real(T))) where {T} =
    abs(H[i+1,i]) ≤ tol*(abs(H[i,i]) + abs(H[i+1,i+1]))

abstract type SmallRotation end

"""
Given's rotation acting on rows i:i+1
"""
struct Rotation2{Tc,Ts} <: SmallRotation
    c::Tc
    s::Ts
    i::Int
end

"""
Two Given's rotations acting on rows i:i+2. This could also be implemented as one Householder
reflector!
"""
struct Rotation3{Tc,Ts} <: SmallRotation
    c₁::Tc
    s₁::Ts
    c₂::Tc
    s₂::Ts
    i::Int
end

# Some utility to materialize a rotation to a matrix.
function Matrix(r::Rotation2{Tc,Ts}, n::Int) where {Tc,Ts}
    r.i < n || throw(ArgumentError("Matrix should have order $(r.i+1) or larger"))
    G = Matrix{promote_type(Tc,Ts)}(I, n, n)
    G[r.i+0,r.i+0] = r.c
    G[r.i+1,r.i+0] = -conj(r.s)
    G[r.i+0,r.i+1] = r.s
    G[r.i+1,r.i+1] = r.c
    return G
end

function Matrix(r::Rotation3{Tc,Ts}, n::Int) where {Tc,Ts}
    G₁ = Matrix(Rotation2(r.c₁, r.s₁, r.i + 1), n)
    G₂ = Matrix(Rotation2(r.c₂, r.s₂, r.i), n)
    return G₂ * G₁
end

"""
Get a rotation that maps [p₁, p₂] to a multiple of [1, 0]
"""
function get_rotation(p₁, p₂, i::Int)
    c, s, nrm = givensAlgorithm(p₁, p₂)
    Rotation2(c, s, i), nrm
end

"""
Get a rotation that maps [p₁, p₂, p₃] to a multiple of [1, 0, 0]
"""
function get_rotation(p₁, p₂, p₃, i::Int)
    c₁, s₁, nrm₁ = givensAlgorithm(p₂, p₃)
    c₂, s₂, nrm₂ = givensAlgorithm(p₁, nrm₁)
    Rotation3(c₁, s₁, c₂, s₂, i), nrm₂
end

"""
Passed into the Schur factorization function if you do not wish to have the Schur vectors.
"""
struct NotWanted end

@inline lmul!(G::SmallRotation, A::AbstractMatrix) = lmul!(G, A, 1, size(A, 2))
@inline rmul!(A::AbstractMatrix, G::SmallRotation) = rmul!(A, G, 1, size(A, 1))

lmul!(::SmallRotation, ::NotWanted, args...) = nothing
rmul!(::NotWanted, ::SmallRotation, args...) = nothing

@inline function lmul!(G::Rotation3, A::AbstractMatrix, from::Int, to::Int)
    @inbounds for j = from:to
        a₁ = A[G.i+0,j]
        a₂ = A[G.i+1,j]
        a₃ = A[G.i+2,j]

        a₂′ = G.c₁ * a₂ + G.s₁ * a₃
        a₃′ = -G.s₁' * a₂ + G.c₁ * a₃

        a₁′′ = G.c₂ * a₁ + G.s₂ * a₂′
        a₂′′ = -G.s₂' * a₁ + G.c₂ * a₂′

        A[G.i+0,j] = a₁′′
        A[G.i+1,j] = a₂′′
        A[G.i+2,j] = a₃′
    end

    A
end

@inline function rmul!(A::AbstractMatrix, G::Rotation3, from::Int, to::Int)
    @inbounds for j = from:to
        a₁ = A[j,G.i+0]
        a₂ = A[j,G.i+1]
        a₃ = A[j,G.i+2]

        a₂′ = a₂ * G.c₁ + a₃ * G.s₁'
        a₃′ = a₂ * -G.s₁ + a₃ * G.c₁

        a₁′′ = a₁ * G.c₂ + a₂′ * G.s₂'
        a₂′′ = a₁ * -G.s₂ + a₂′ * G.c₂

        A[j,G.i+0] = a₁′′
        A[j,G.i+1] = a₂′′
        A[j,G.i+2] = a₃′
    end
    A
end

@inline function lmul!(G::Rotation2, A::AbstractMatrix, from::Int, to::Int)
    @inbounds for j = from:to
        a₁ = A[G.i+0,j]
        a₂ = A[G.i+1,j]

        a₁′ = G.c * a₁ + G.s * a₂
        a₂′ = -G.s' * a₁ + G.c * a₂

        A[G.i+0,j] = a₁′
        A[G.i+1,j] = a₂′
    end

    A
end

@inline function rmul!(A::AbstractMatrix, G::Rotation2, from::Int, to::Int)
    @inbounds for j = from:to
        a₁ = A[j,G.i+0]
        a₂ = A[j,G.i+1]

        a₁′ = a₁ * G.c + a₂ * G.s'
        a₂′ = a₁ * -G.s + a₂ * G.c

        A[j,G.i+0] = a₁′
        A[j,G.i+1] = a₂′
    end
    A
end

function double_shift_schur!(H::AbstractMatrix{Tv}, from::Int, to::Int,
                             μ::Complex, Q = NotWanted()) where {Tv<:Real}
    m, n = size(H)

    # Compute the nonzero entries of p = (H - μI)(H - μ'I)e₁.
    # Because of the Hessenberg structure we only need H[min:min+2,min:min+1] to form p.
    @inbounds H₁₁ = H[from+0,from+0]
    @inbounds H₂₁ = H[from+1,from+0]

    @inbounds H₁₂ = H[from+0,from+1]
    @inbounds H₂₂ = H[from+1,from+1]
    @inbounds H₃₂ = H[from+2,from+1]

    p₁ = abs2(μ) - 2real(μ) * H₁₁ + H₁₁ * H₁₁ + H₁₂ * H₂₁
    p₂ = -2real(μ) * H₂₁ + H₂₁ * H₁₁ + H₂₂ * H₂₁
    p₃ = H₃₂ * H₂₁

    # Map that column to a mulitiple of e₁ via two Given's rotations
    G₁, nrm = get_rotation(p₁, p₂, p₃, from)

    # Apply the Given's rotations
    lmul!(G₁, H, from, n)
    rmul!(H, G₁, 1, min(from + 3, m))
    rmul!(Q, G₁)

    # Bulge chasing. First step of the for-loop below looks like:
    #  from           to
    #     ↓           ↓
    #     x x x x x x x     x x x x x x x     x + + + x x x
    # i → x x x x x x x     + + + + + + +     x + + + x x x
    #     x x x x x x x     o + + + + + +       + + + x x x
    #     x x x x x x x  ⇒  o + + + + + +  ⇒    + + + x x x
    #       |   x x x x           x x x x       + + + x x x
    #       |     x x x             x x x             x x x
    #       |       x x               x x               x x
    #       ↑
    #       i
    #
    # Last iterations looks like:
    #  from           to
    #     ↓           ↓
    #     x x x x x x x     x x x x x x x     x x x x + + +
    #     x x x x x x x     x x x x x x x     x x x x + + +
    #       x x x x x x       x x x x x x       x x x + + +
    #         x x x x x  ⇒    x x x x x x  ⇒      x x + + +
    # i → ----- x x x x           + + + +           x + + +
    #           x x x x           o + + +             + + +
    #           x x x x           o + + +             + + +
    #             ↑
    #             i

    @inbounds for i = from + 1 : to - 2
        p₁ = H[i+0,i-1]
        p₂ = H[i+1,i-1]
        p₃ = H[i+2,i-1]

        G, nrm = get_rotation(p₁, p₂, p₃, i)

        # First column is done by hand
        H[i+0,i-1] = nrm
        H[i+1,i-1] = zero(Tv)
        H[i+2,i-1] = zero(Tv)

        # Rotate remaining columns
        lmul!(G, H, i, n)

        # Create a new bulge
        rmul!(H, G, 1, min(i + 3, m))
        rmul!(Q, G)
    end

    # Last bulge is just one Given's rotation
    #     from          to
    #       ↓           ↓
    #from → x x x x x x x    x x x x x x x    x x x x x + +
    #       x x x x x x x    x x x x x x x    x x x x x + +
    #         x x x x x x      x x x x x x      x x x x + +
    #           x x x x x  ⇒     x x x x x  ⇒     x x x + +
    #             x x x x          x x x x          x x + +
    #               x x x            + + +            x + +
    # to  → ------- x x x            o + +              + +

    @inbounds Gₙ, nrm = get_rotation(H[to-1,to-2], H[to,to-2], to-1)
    @inbounds H[to-1,to-2] = nrm
    @inbounds H[to,to-2] = zero(Tv)

    lmul!(Gₙ, H, to-1, n)
    rmul!(H, Gₙ, 1, to)
    rmul!(Q, Gₙ)

    H
end

function single_shift_schur!(H::AbstractMatrix{Tv}, from::Int, to::Int,
                             μ::Number, Q = NotWanted()) where {Tv<:Number}
    m, n = size(H)

    # Compute the nonzero entries of p = (H - μI)e₁.
    @inbounds H₁₁ = H[from+0,from+0]
    @inbounds H₂₁ = H[from+1,from+0]

    p₁ = H₁₁ - μ
    p₂ = H₂₁

    # Map that column to a mulitiple of e₁ via two Given's rotations
    G₁, nrm = get_rotation(p₁, p₂, from)

    # Apply the Given's rotations
    lmul!(G₁, H, from, n)
    rmul!(H, G₁, 1, min(from + 2, m))
    rmul!(Q, G₁)

    # Bulge chasing. First step of the for-loop below looks like:
    #  from           to
    #     ↓           ↓
    #     x x x x x x x     x x x x x x x     x + + x x x x
    # i → x x x x x x x     + + + + + + +     x + + x x x x
    #     x x x x x x x     o + + + + + +       + + x x x x
    #         x x x x x  ⇒      x x x x x  ⇒    + + x x x x
    #       |   x x x x           x x x x           x x x x
    #       |     x x x             x x x             x x x
    #       |       x x               x x               x x
    #       ↑
    #       i
    #
    # Last iterations looks like:
    #  from           to
    #     ↓           ↓
    #     x x x x x x x     x x x x x x x     x x x x x + +
    #     x x x x x x x     x x x x x x x     x x x x x + +
    #       x x x x x x       x x x x x x       x x x x + +
    #         x x x x x  ⇒      x x x x x  ⇒      x x x + +
    #           x x x x           x x x x           x x + +
    # i → ------- x x x             + + +             x + +
    #             x x x             0 + +               + +
    #               ↑
    #               i

    @inbounds for i = from + 1 : to - 1
        p₁ = H[i+0,i-1]
        p₂ = H[i+1,i-1]

        G, nrm = get_rotation(p₁, p₂, i)

        # First column is done by hand
        H[i+0,i-1] = nrm
        H[i+1,i-1] = zero(Tv)

        # Rotate remaining columns
        lmul!(G, H, i, n)

        # Create a new bulge
        rmul!(H, G, 1, min(i + 2, m))
        rmul!(Q, G)
    end

    H
end

###
### Real arithmetic
###
function local_schurfact!(H::AbstractMatrix{T}, start::Int, to::Int,
                          Q = NotWanted(), tol = eps(T),
                          maxiter = 100*size(H, 1)) where {T<:Real}
    # iteration count
    iter = 0

    @inbounds while true
        iter += 1

        if iter > maxiter
            throw("QR algorithm did not converge")
        end

        # Indexing
        # `to` points to the column where the off-diagonal value was last zero.
        # while `from` points to the smallest index such that there is no small off-diagonal
        # value in columns from:end-1. Sometimes `from` is just 1. Cartoon of a split
        # with from != 1:
        #
        #  + + | | | | + +
        #  + + | | | | + +
        #    o X X X X = =
        #      X X X X = =
        #      . X X X = =
        #      .   X X = =
        #      .     o + +
        #      .     . + +
        #      ^     ^
        #   from   to
        # The X's form the unreduced Hessenberg matrix we are applying QR iterations to,
        # the | and = values get updated by Given's rotations, while the + values remain
        # untouched! The o's are zeros -- or numerically considered zeros.

        # We keep `from` one column past the zero off-diagonal value, so we check whether
        # the `from - 1` column has a small off-diagonal value.
        from = to
        while from > start && !is_offdiagonal_small(H, from - 1, tol)
            from -= 1
        end

        if from == to
            # This just means H[to, to-1] == 0, so one eigenvalue converged at the end
            H[from,from-1] = zero(T)
            to -= 1
        else
            # Now we are sure we can work with a 2×2 block H[to-1:to,to-1:to]
            # We check if this block has a conjugate eigenpair, which might mean we have
            # converged w.r.t. this block if from + 1 == to.
            # Otherwise, if from + 1 < to, we do either a single or double shift, based on
            # whether the H[to-1:to,to-1:to] part has real eigenvalues or a conjugate pair.

            H₁₁, H₁₂ = H[to-1,to-1], H[to-1,to]
            H₂₁, H₂₂ = H[to  ,to-1], H[to  ,to]

            # Scaling to avoid losing precision in the case where we have nearly
            # repeated eigenvalues.
            scale = abs(H₁₁) + abs(H₁₂) + abs(H₂₁) + abs(H₂₂)
            H₁₁ /= scale; H₁₂ /= scale; H₂₁ /= scale; H₂₂ /= scale

            # Trace and discriminant of small eigenvalue problem.
            t = (H₁₁ + H₂₂) / 2
            d = (H₁₁ - t) * (H₂₂ - t) - H₁₂ * H₂₁
            sqrt_discr = sqrt(abs(d))

            # Very important to have a strict comparison here!
            if d < zero(T)
                # Real eigenvalues.
                # Note that if from + 1 == to in this case, then just one additional
                # iteration is necessary, since the Wilkinson shift will do an exact shift.

                # Determine the Wilkinson shift -- the closest eigenvalue of the 2x2 block
                # near H[to,to]

                λ₁ = t + sqrt_discr
                λ₂ = t - sqrt_discr
                λ = abs(H₂₂ - λ₁) < abs(H₂₂ - λ₂) ? λ₁ : λ₂
                λ *= scale

                # Run a bulge chase
                single_shift_schur!(H, from, to, λ, Q)
            else
                # Conjugate pair
                if from + 1 == to
                    # A conjugate pair has converged apparently!
                    if from != 1
                        H[from,from-1] = zero(T)
                    end
                    to -= 2
                else
                    # Otherwise we do a double shift!
                    complex_shift = scale * (t + sqrt_discr * im)
                    double_shift_schur!(H, from, to, complex_shift, Q)
                end
            end
        end

        # Converged!
        to ≤ start && break
    end

    return true
end

###
### Generic implementation
###
function local_schurfact!(H::AbstractMatrix{T}, start::Int, to::Int,
                          Q = NotWanted(), tol = eps(real(T)),
                          maxiter = 100*size(H, 1)) where {T}
    # iteration count
    iter = 0

    @inbounds while true
        iter += 1
        iter > maxiter && return false

        # Indexing, see the real arithmetic version!

        from = to
        while from > start && !is_offdiagonal_small(H, from - 1, tol)
            from -= 1
        end

        if from == to
            # This just means H[to, to-1] == 0, so one eigenvalue converged at the end
            H[from,from-1] = zero(T)
            to -= 1
        else
            # Compute Wilkinson shift
            H₁₁, H₁₂ = H[to-1,to-1], H[to-1,to]
            H₂₁, H₂₂ = H[to  ,to-1], H[to  ,to]
            d = H₁₁ * H₂₂ - H₂₁ * H₁₂
            t = H₁₁ + H₂₂
            sqr = sqrt(t * t - 4d)
            λ₁ = (t + sqr) / 2
            λ₂ = (t - sqr) / 2
            λ = abs(H₂₂ - λ₁) < abs(H₂₂ - λ₂) ? λ₁ : λ₂

            # Run a bulge chase
            single_shift_schur!(H, from, to, λ, Q)
        end

        # Converged!
        to ≤ start && break
    end

    return true
end

local_schurfact!(H::AbstractMatrix{T}, Q = NotWanted(), tol = eps(real(T)), maxiter = 100*size(H, 1)) where {T} =
    local_schurfact!(H, 1, size(H, 2), Q, tol, maxiter)


text:
# Container for a DataFrame row
struct DataFrameRow{T <: AbstractDataFrame}
    df::T
    row::Int
end

function Base.getindex(r::DataFrameRow, idx::AbstractArray)
    return DataFrameRow(r.df[idx], r.row)
end

function Base.getindex(r::DataFrameRow, idx::Any)
    return r.df[r.row, idx]
end

function Base.setindex!(r::DataFrameRow, value::Any, idx::Any)
    return setindex!(r.df, value, r.row, idx)
end

Base.names(r::DataFrameRow) = names(r.df)
_names(r::DataFrameRow) = _names(r.df)

Base.view(r::DataFrameRow, c) = DataFrameRow(r.df[[c]], r.row)

index(r::DataFrameRow) = index(r.df)

Base.length(r::DataFrameRow) = size(r.df, 2)

Compat.lastindex(r::DataFrameRow) = size(r.df, 2)

Base.collect(r::DataFrameRow) = Tuple{Symbol, Any}[x for x in r]

Base.start(r::DataFrameRow) = 1

Base.next(r::DataFrameRow, s) = ((_names(r)[s], r[s]), s + 1)

Base.done(r::DataFrameRow, s) = s > length(r)

Base.convert(::Type{Array}, r::DataFrameRow) = convert(Array, r.df[r.row,:])

# hash column element
Base.@propagate_inbounds hash_colel(v::AbstractArray, i, h::UInt = zero(UInt)) = hash(v[i], h)
Base.@propagate_inbounds hash_colel(v::AbstractCategoricalArray, i, h::UInt = zero(UInt)) =
    hash(CategoricalArrays.index(v.pool)[v.refs[i]], h)
Base.@propagate_inbounds function hash_colel(v::AbstractCategoricalArray{>: Missing}, i, h::UInt = zero(UInt))
    ref = v.refs[i]
    ref == 0 ? hash(missing, h) : hash(CategoricalArrays.index(v.pool)[ref], h)
end

# hash of DataFrame rows based on its values
# so that duplicate rows would have the same hash
# table columns are passed as a tuple of vectors to ensure type specialization
rowhash(cols::Tuple{AbstractVector}, r::Int, h::UInt = zero(UInt))::UInt =
    hash_colel(cols[1], r, h)
function rowhash(cols::Tuple{Vararg{AbstractVector}}, r::Int, h::UInt = zero(UInt))::UInt
    h = hash_colel(cols[1], r, h)
    rowhash(Base.tail(cols), r, h)
end

Base.hash(r::DataFrameRow, h::UInt = zero(UInt)) =
    rowhash(ntuple(i -> r.df[i], ncol(r.df)), r.row, h)

# comparison of DataFrame rows
# only the rows of the same DataFrame could be compared
# rows are equal if they have the same values (while the row indices could differ)
# if all non-missing values are equal, but there are missings, returns missing
Base.:(==)(r1::DataFrameRow, r2::DataFrameRow) = isequal(r1, r2)

function Base.isequal(r1::DataFrameRow, r2::DataFrameRow)
    isequal_row(r1.df, r1.row, r2.df, r2.row)
end

# internal method for comparing the elements of the same data table column
isequal_colel(col::AbstractArray, r1::Int, r2::Int) =
    (r1 == r2) || isequal(Base.unsafe_getindex(col, r1), Base.unsafe_getindex(col, r2))

# table columns are passed as a tuple of vectors to ensure type specialization
isequal_row(cols::Tuple{AbstractVector}, r1::Int, r2::Int) =
    isequal(cols[1][r1], cols[1][r2])
isequal_row(cols::Tuple{Vararg{AbstractVector}}, r1::Int, r2::Int) =
    isequal(cols[1][r1], cols[1][r2]) && isequal_row(Base.tail(cols), r1, r2)

isequal_row(cols1::Tuple{AbstractVector}, r1::Int, cols2::Tuple{AbstractVector}, r2::Int) =
    isequal(cols1[1][r1], cols2[1][r2])
isequal_row(cols1::Tuple{Vararg{AbstractVector}}, r1::Int,
            cols2::Tuple{Vararg{AbstractVector}}, r2::Int) =
    isequal(cols1[1][r1], cols2[1][r2]) &&
        isequal_row(Base.tail(cols1), r1, Base.tail(cols2), r2)

function isequal_row(df1::AbstractDataFrame, r1::Int, df2::AbstractDataFrame, r2::Int)
    if df1 === df2
        if r1 == r2
            return true
        end
    elseif !(ncol(df1) == ncol(df2))
        throw(ArgumentError("Rows of the tables that have different number of columns cannot be compared. Got $(ncol(df1)) and $(ncol(df2)) columns"))
    end
    @inbounds for (col1, col2) in zip(columns(df1), columns(df2))
        isequal(col1[r1], col2[r2]) || return false
    end
    return true
end

# lexicographic ordering on DataFrame rows, missing > !missing
function Base.isless(r1::DataFrameRow, r2::DataFrameRow)
    (ncol(r1.df) == ncol(r2.df)) ||
        throw(ArgumentError("Rows of the data tables that have different number of columns cannot be compared ($(ncol(df1)) and $(ncol(df2)))"))
    @inbounds for i in 1:ncol(r1.df)
        if !isequal(r1.df[i][r1.row], r2.df[i][r2.row])
            return isless(r1.df[i][r1.row], r2.df[i][r2.row])
        end
    end
    return false
end


text:
# pair
# Construct a Pair object with type Pair{typeof(x), typeof(y)}. The elements are stored in the fields first and second. They can also be accessed via iteration.
p = Pair("A", 1)
println(p)
println(typeof(p))

println(p.first)
println(p.second)

for x in p
    println(x)
end

# pairs
Ps = Pair(["A", "B", "C"], [1, 2, 3])
println(Ps)

for x in Ps
    println(x)
end

max_stars_repo_name: startprogress/Hello-Julia

max_issues_repo_name: startprogress/Hello-Julia

max_forks_repo_name: startprogress/Hello-Julia


text:
# module Bukdu.Plug

function simple_el(x::AbstractString)::String
    string('"', x, '"')
end

function simple_el(x)
    x
end

function simple_repr(pair::Pair)::String
    string(Pair, '(', simple_el(pair.first), ", ", simple_el(pair.second), ')')
end

function simple_repr(pairs::Vector{<:Pair})::String
    string('[', join(simple_repr.(pairs), ", "), ']')
end

function simple_repr(x)
    x
end

# module Bukdu.Plug

max_stars_repo_name: wookay/TestBukdu

max_issues_repo_name: wookay/TestBukdu

max_forks_repo_name: wookay/TestBukdu


text:
### A Pluto.jl notebook ###
# v0.16.0

using Markdown
using InteractiveUtils

# ╔═╡ 94dde840-54f6-4fe4-846b-bc15f8fca9fa
begin
	# Packages
	using PlutoUI, LightGraphs, GraphPlot, Clustering, SparseArrays
	using LinearAlgebra, Plots, Distances, Random
end

# ╔═╡ c9cf879e-0b01-4e0a-b31c-2ca5c6f03e63
TableOfContents(title="📚 Table of Contents", aside=true)

# ╔═╡ 81efb137-7e14-4091-a7f0-c6b72e2d77f7
md"""
# Spectral Graph K-partitioning

Instead of using recursive spectral bipartitioning, the graph $k$-partitioning problem can be solved using $k$ eigenvectors which correspond to $k$ smallest eigenvalues of Laplace matrix (Laplacian) or normalized Laplace matrix (normalized Laplacian), respectively.

Suggested reading is [U. von Luxburg, A Tutorial on Spectral Clustering](http://www.kyb.mpg.de/fileadmin/user_upload/files/publications/attachments/luxburg06_TR_v2_4139%5b1%5d.pdf), which includes the quote

_"Spectral clustering cannot serve as a “black box algorithm” which automatically detects the correct clusters in any given data set. But it can be considered as a powerful tool which can produce good results if applied with care."_

__Prerequisites__

The reader should be familiar with k-means algorithm, spectral graph bipartitioning and recursive bipartitioning.

__Competences__

The reader should be able to apply graph spectral k-partitioning to data clustering problems.

__Credits.__ The notebook was initially derived from M.Sc. Thesis of Ivančica Mirošević.
"""

# ╔═╡ 75cd6187-4c51-426c-8a3c-d7b6c922ae0b
md"""

# Definitions

Let $G=(V,E)$ be a weighted graph with weights $\omega$, with weights matrix $W$, Laplacian matrix $L=D-W$, and normalized Laplacian matrix $L_n=D^{-1/2}(D-W)D^{-1/2}$.

Let the $k$-partition $\pi_k =\{V_{1},V_{2},...,V_{k}\}$, the cut $\mathop{\mathrm{cut}}(\pi_k)$, the proportional cut $\mathop{\mathrm{pcut}}(\pi_k)$ and the normalized cut $\mathop{\mathrm{ncut}}(\pi_k)$ be defined as in the
[Spectral Graph Bipartitioning](https://ivanslapnicar.github.io/NumericalMathematics/C2%20Spectral%20Graph%20Bipartitioning.jl.html) notebook.

__Partition vectors__ of a $k$-partition $\pi_k$ are

$$
\begin{aligned}
h_{1} &=[\overset{\displaystyle |V_{1}|}{\overbrace{1,\cdots
,1}},0,\cdots
,0,\cdots ,0,\cdots ,0]^{T}  \\
h_{2} &=[0,\cdots
,0,\overset{\displaystyle |V_{2}|}{\overbrace{1,\cdots ,1}} ,\cdots ,0,\cdots
,0]^{T} \\
&\vdots \\
h_{k} &=[0,\cdots ,0,0,\cdots ,0,\cdots
,\overset{\displaystyle |V_{k}|}{ \overbrace{1,\cdots ,1}}]^{T}.
\end{aligned}$$

# Facts

1. Set

$$
\begin{aligned}
X&=\begin{bmatrix} x_1 & x_2 &\cdots & x_k \end{bmatrix}, \quad
x_i=\displaystyle \frac{h_i}{\|h_i\|_2}, \\
Y&=\begin{bmatrix} y_1 & y_2 &\cdots & y_k \end{bmatrix}, \quad
y_i=\displaystyle \frac{D^{1/2}h_i}{\|D^{1/2}h_i\|_2}.
\end{aligned}$$

It holds

$$
\begin{aligned}
& \mathop{\mathrm{cut}}(V_{i},V\backslash V_{i})=h_{i}^{T}(D-W)h_{i}=h_{i}^{T}L h_{i},\quad
\omega( C_{i})=h_{i}^{T}D h_{i},\quad |C_{i}| =h_{i}^{T}h_{i},\\
& \mathop{\mathrm{pcut}}(\pi_k) =\frac{h_{1}^{T}L h_{1}}{h_{1}^{T} h_{1}}+
\cdots + \frac{h_{k}^{T}L h_{k}}{h_{k}^{T}h_{k}}
=x_{1}^{T}L x_{1}+\cdots +x_{k}^{T}Lx_{k}=\mathop{\mathrm{trace}}(X^{T}LX),\\
& \mathop{\mathrm{ncut}}(\pi_k)=\frac{h_{1}^{T}L h_{1}}{h_{1}^{T}D h_{1}}+\cdots
+\frac{h_{k}^{T}L h_{k}}{h_{k}^{T}D h_{k}}
=\mathop{\mathrm{trace}}(Y^{T}L_{n}Y).
\end{aligned}$$

2. The __relaxed__ $k$-partitioning problems are trace-minimization problems,

$$
\begin{aligned}
\min_{\displaystyle \pi_k} \mathop{\mathrm{pcut}}(\pi_k) &\geq
\underset{\displaystyle X\in\mathbb{R}^{n\times k}}{\min_{\displaystyle X^{T}X=I}}
\mathop{\mathrm{trace}}(X^{T}LX),\\
\min_{\displaystyle \pi_k} \mathop{\mathrm{ncut}}(\pi_k) &\geq
\underset{\displaystyle Y\in\mathbb{R}^{n\times
k}}{\min_{\displaystyle Y^{T}Y=I}}\mathop{\mathrm{trace}}(Y^{T}L_{n}Y).
\end{aligned}$$

3. __Ky-Fan  Theorem.__ Let $A\in \mathbb{R}^{n\times n}$ be a symmetric matrix with eigenvalues $\lambda _1\leq \cdots \leq \lambda_n$. Then

$$
\underset{\displaystyle Z^TZ=I}{\min_{\displaystyle Z\in \mathbb{R}^{n\times
k}}}\mathop{\mathrm{trace}}\left(Z^{T}AZ\right)
=\sum_{i=1}^{k}\lambda_{i}.$$

4. Let $\lambda_1\leq \cdots \leq \lambda_n$ be the eigenvalues of $L$ with eigenvectors $v^{[1]},\cdots ,v^{[k]}$. The solution of the relaxed proportional cut problem is the matrix $X=\begin{bmatrix}v^{[1]} & \cdots & v^{[k]}\end{bmatrix}$, and it holds

$\min\limits_{\displaystyle \pi_k} \mathop{\mathrm{pcut}}(\pi_k)\geq \sum\limits_{i=1}^k \lambda_i.$

5. Let $\mu_1\leq \cdots \leq \mu_n$ be the eigenvalues of $L_n$ with eigenvectors $w^{[1]},\cdots ,w^{[k]}$. The solution of the relaxed normalized cut problem is the matrix $Y=\begin{bmatrix}w^{[1]} & \cdots & w^{[k]}\end{bmatrix}$, and it holds

$\min\limits_{\displaystyle \pi_k} \mathop{\mathrm{ncut}}(\pi_k)\geq \sum\limits_{i=1}^k \mu_i$.

6. It remains to recover the $k$-partition. The k-means algorithm applied to rows of the matrices $X$ or $D^{-1/2}Y$, will compute the $k$ centers and the assignment vector whose $i$-th component denotes the subset $V_j$ to which the vertex $i$ belongs.
"""

# ╔═╡ 639758a5-413d-408a-ace9-3741322c3dc2
md"""

# Examples

## Graph with three clusters
"""

# ╔═╡ d367f447-16e1-4cbc-b05f-b807d4ef955b
begin
	# Sources, targets, and weights
	n=9
	sn=[1,1,1,2,2,2,3,3,5,6,7,7,8]
	tn=[2,3,4,3,4,7,4,5,6,9,8,9,9]
	wn=[2,3,4,4,5,1,6,1,7,1,4,3,2]
	[sn tn wn]
end

# ╔═╡ 9438ace8-4290-4caa-bb34-24c1c8f4f66a
begin
	# What is the optimal tripartition?
	G=Graph(n)
	for i=1:length(sn)
	    add_edge!(G,sn[i],tn[i])
	end
	gplot(G, nodelabel=1:n, edgelabel=wn)
end

# ╔═╡ f05bae5c-8d1c-4f68-a299-fab3af2432ae
begin
	# We define some functions
	function WeightMatrix(src::Array,dst::Array,weights::Array)
	    n=nv(G)
	    sparse([src;dst],[dst;src],[weights;weights],n,n)
	end

	Laplacian(W::AbstractMatrix)=spdiagm(0=>vec(sum(W,dims=2)))-W

	function NormalizedLaplacian(L::AbstractMatrix)
	    D=1.0./sqrt.(diag(L))
	    n=length(D)
	    [L[i,j]*(D[i]*D[j]) for i=1:n, j=1:n]
	end
end

# ╔═╡ 357b8af9-700a-4a2d-9703-575af5b9ab13
begin
	W=WeightMatrix(sn,tn,wn)
	L=Laplacian(W)
	Lₙ=NormalizedLaplacian(L)
end

# ╔═╡ 085b49b4-08a2-4e6e-8cbe-6a011a93b551
Matrix(L)

# ╔═╡ 280049be-261e-49d7-a6fc-2211afe94e06
# Proportional cut. The clustering is visible in
# the components of v₂ and v₃
# E=eigs(L,nev=3,which=:SM)
E=eigen(Matrix(L))

# ╔═╡ 64730ce5-61b4-405d-9a41-81d0253a4713
# Check the assignments
out=kmeans(Matrix(transpose(E.vectors[:,1:3])),3)

# ╔═╡ 692cbb97-2a5f-42c9-b829-e08d5e7479a8
begin
	# Normalized cut
	# Lanczos cannot be used for the "smallest in magnitude"
	# eienvalues of a singular matrix
	# λ,Y=eigs(Ln,nev=3,which=:SM) does not work
	Eₙ=eigen(Lₙ)
	D=sqrt.(diag(L))
	Y=inv(Diagonal(D))*Eₙ.vectors[:,1:3]
	outₙ=kmeans(Matrix(transpose(Y)),3)
end

# ╔═╡ 662b7b01-883f-4d51-b696-26f7559e0211
md"""
## Concentric rings
"""

# ╔═╡ 55d217d5-c31a-431d-bd46-f9f09280cf5b
function plotKpartresult(C::Vector,X::Array)
    k=maximum(C)
    scatter(aspect_ratio=1)
    for j=1:k
        scatter!(X[1,findall(C.==j)],X[2,findall(C.==j)],label="Cluster $j")
    end
	scatter!()
end

# ╔═╡ 3f815c3e-850d-4ca7-af1c-a2ff14e429db
begin
	# Generate concentric rings
	k=4
	Random.seed!(541)
	# Center
	center=[0,0]
	# Radii
	radii=Random.randperm(10)[1:k]
	# Number of points in rings
	sizes=rand(300:500,k)
	center,radii,sizes
end

# ╔═╡ 967b8e40-1f95-11eb-0aa1-8f4592054357
begin
	# Generate points
	X=Array{Float64}(undef,2,sum(sizes))
	csizes=cumsum(sizes)
	# Random angles
	ϕ=2*π*rand(sum(sizes))
	for i=1:csizes[1]
		X[:,i]=center+radii[1]*[cos(ϕ[i]);sin(ϕ[i])] + (rand(2).-0.5)/50
	end
	for j=2:k
		for i=csizes[j-1]+1:csizes[j]
			X[:,i]=center+radii[j]*[cos(ϕ[i]);sin(ϕ[i])] + (rand(2).-0.5)/50
		end
	end
	scatter(X[1,:],X[2,:],title="Concentric rings", aspect_ratio=1,label="Points")
end

# ╔═╡ 708a16c5-f755-490b-abcb-89788813b7d0
begin
	S=pairwise(SqEuclidean(),X,dims=2)
	# S=pairwise(Cityblock(),X)
	β=60
	W₁=exp.(-β*S);
end

# ╔═╡ c298ccfe-f15e-4652-baa7-c122cb22f22f
begin
	L₁=Laplacian(W₁)
	Ln₁=NormalizedLaplacian(L₁);
end

# ╔═╡ 9d8aef37-9640-4d67-9c33-bb6513938ae1
begin
	# Laplacian
	E₁=eigen(L₁)
	sp=sortperm(abs.(E₁.values))[1:k]
	λ₁=E₁.values[sp]
	Y₁=E₁.vectors[:,sp]
	out₁=kmeans(Matrix(transpose(Y₁)),k)
	plotKpartresult(out₁.assignments,X)
end

# ╔═╡ 7c72773d-0915-4ef0-aa7e-7f0474426bfa
begin
	# Normalized Laplacian
	En₁=eigen(Ln₁)
	spn=sortperm(abs.(En₁.values))[1:k]
	λ=En₁.values[spn]
	Yn₁=En₁.vectors[:,spn]
	Yn₁=Diagonal(1.0./sqrt.(diag(L₁)))*Y₁
	outn₁=kmeans(Matrix(transpose(Y₁)),k)
	plotKpartresult(outn₁.assignments,X)
end

# ╔═╡ 00000000-0000-0000-0000-000000000001
PLUTO_PROJECT_TOML_CONTENTS = """
[deps]
Clustering = "aaaa29a8-35af-508c-8bc3-b662a17a0fe5"
Distances = "b4f34e82-e78d-54a5-968a-f98e89d6e8f7"
GraphPlot = "a2cc645c-3eea-5389-862e-a155d0052231"
LightGraphs = "093fc24a-ae57-5d10-9952-331d41423f4d"
LinearAlgebra = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"
Plots = "91a5bcdd-55d7-5caf-9e0b-520d859cae80"
PlutoUI = "7f904dfe-b85e-4ff6-b463-dae2292396a8"
Random = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"
SparseArrays = "2f01184e-e22b-5df5-ae63-d93ebab69eaf"

[compat]
Clustering = "~0.14.2"
Distances = "~0.10.4"
GraphPlot = "~0.4.4"
LightGraphs = "~1.3.5"
Plots = "~1.21.3"
PlutoUI = "~0.7.9"
"""

# ╔═╡ 00000000-0000-0000-0000-000000000002
PLUTO_MANIFEST_TOML_CONTENTS = """
# This file is machine-generated - editing it directly is not advised

[[Adapt]]
deps = ["LinearAlgebra"]
git-tree-sha1 = "84918055d15b3114ede17ac6a7182f68870c16f7"
uuid = "79e6a3ab-5dfb-504d-930d-738a2a938a0e"
version = "3.3.1"

[[ArgTools]]
uuid = "0dad84c5-d112-42e6-8d28-ef12dabb789f"

[[ArnoldiMethod]]
deps = ["LinearAlgebra", "Random", "StaticArrays"]
git-tree-sha1 = "f87e559f87a45bece9c9ed97458d3afe98b1ebb9"
uuid = "ec485272-7323-5ecc-a04f-4719b315124d"
version = "0.1.0"

[[Artifacts]]
uuid = "56f22d72-fd6d-98f1-02f0-08ddc0907c33"

[[Base64]]
uuid = "2a0f44e3-6c83-55bd-87e4-b1978d98bd5f"

[[Bzip2_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "19a35467a82e236ff51bc17a3a44b69ef35185a2"
uuid = "6e34b625-4abd-537c-b88f-471c36dfa7a0"
version = "1.0.8+0"

[[Cairo_jll]]
deps = ["Artifacts", "Bzip2_jll", "Fontconfig_jll", "FreeType2_jll", "Glib_jll", "JLLWrappers", "LZO_jll", "Libdl", "Pixman_jll", "Pkg", "Xorg_libXext_jll", "Xorg_libXrender_jll", "Zlib_jll", "libpng_jll"]
git-tree-sha1 = "f2202b55d816427cd385a9a4f3ffb226bee80f99"
uuid = "83423d85-b0ee-5818-9007-b63ccbeb887a"
version = "1.16.1+0"

[[Clustering]]
deps = ["Distances", "LinearAlgebra", "NearestNeighbors", "Printf", "SparseArrays", "Statistics", "StatsBase"]
git-tree-sha1 = "75479b7df4167267d75294d14b58244695beb2ac"
uuid = "aaaa29a8-35af-508c-8bc3-b662a17a0fe5"
version = "0.14.2"

[[ColorSchemes]]
deps = ["ColorTypes", "Colors", "FixedPointNumbers", "Random"]
git-tree-sha1 = "9995eb3977fbf67b86d0a0a0508e83017ded03f2"
uuid = "35d6a980-a343-548e-a6ea-1d62b119f2f4"
version = "3.14.0"

[[ColorTypes]]
deps = ["FixedPointNumbers", "Random"]
git-tree-sha1 = "32a2b8af383f11cbb65803883837a149d10dfe8a"
uuid = "3da002f7-5984-5a60-b8a6-cbb66c0b333f"
version = "0.10.12"

[[Colors]]
deps = ["ColorTypes", "FixedPointNumbers", "Reexport"]
git-tree-sha1 = "417b0ed7b8b838aa6ca0a87aadf1bb9eb111ce40"
uuid = "5ae59095-9a9b-59fe-a467-6f913c188581"
version = "0.12.8"

[[Compat]]
deps = ["Base64", "Dates", "DelimitedFiles", "Distributed", "InteractiveUtils", "LibGit2", "Libdl", "LinearAlgebra", "Markdown", "Mmap", "Pkg", "Printf", "REPL", "Random", "SHA", "Serialization", "SharedArrays", "Sockets", "SparseArrays", "Statistics", "Test", "UUIDs", "Unicode"]
git-tree-sha1 = "727e463cfebd0c7b999bbf3e9e7e16f254b94193"
uuid = "34da2185-b29b-5c13-b0c7-acf172513d20"
version = "3.34.0"

[[CompilerSupportLibraries_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "e66e0078-7015-5450-92f7-15fbd957f2ae"

[[Compose]]
deps = ["Base64", "Colors", "DataStructures", "Dates", "IterTools", "JSON", "LinearAlgebra", "Measures", "Printf", "Random", "Requires", "Statistics", "UUIDs"]
git-tree-sha1 = "c6461fc7c35a4bb8d00905df7adafcff1fe3a6bc"
uuid = "a81c6b42-2e10-5240-aca2-a61377ecd94b"
version = "0.9.2"

[[Contour]]
deps = ["StaticArrays"]
git-tree-sha1 = "9f02045d934dc030edad45944ea80dbd1f0ebea7"
uuid = "d38c429a-6771-53c6-b99e-75d170b6e991"
version = "0.5.7"

[[DataAPI]]
git-tree-sha1 = "bec2532f8adb82005476c141ec23e921fc20971b"
uuid = "9a962f9c-6df0-11e9-0e5d-c546b8b5ee8a"
version = "1.8.0"

[[DataStructures]]
deps = ["Compat", "InteractiveUtils", "OrderedCollections"]
git-tree-sha1 = "7d9d316f04214f7efdbb6398d545446e246eff02"
uuid = "864edb3b-99cc-5e75-8d2d-829cb0a9cfe8"
version = "0.18.10"

[[DataValueInterfaces]]
git-tree-sha1 = "bfc1187b79289637fa0ef6d4436ebdfe6905cbd6"
uuid = "e2d170a0-9d28-54be-80f0-106bbe20a464"
version = "1.0.0"

[[Dates]]
deps = ["Printf"]
uuid = "ade2ca70-3891-5945-98fb-dc099432e06a"

[[DelimitedFiles]]
deps = ["Mmap"]
uuid = "8bb1440f-4735-579b-a4ab-409b98df4dab"

[[Distances]]
deps = ["LinearAlgebra", "Statistics", "StatsAPI"]
git-tree-sha1 = "9f46deb4d4ee4494ffb5a40a27a2aced67bdd838"
uuid = "b4f34e82-e78d-54a5-968a-f98e89d6e8f7"
version = "0.10.4"

[[Distributed]]
deps = ["Random", "Serialization", "Sockets"]
uuid = "8ba89e20-285c-5b6f-9357-94700520ee1b"

[[Downloads]]
deps = ["ArgTools", "LibCURL", "NetworkOptions"]
uuid = "f43a241f-c20a-4ad4-852c-f6b1247861c6"

[[EarCut_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "3f3a2501fa7236e9b911e0f7a588c657e822bb6d"
uuid = "5ae413db-bbd1-5e63-b57d-d24a61df00f5"
version = "2.2.3+0"

[[Expat_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "b3bfd02e98aedfa5cf885665493c5598c350cd2f"
uuid = "2e619515-83b5-522b-bb60-26c02a35a201"
version = "2.2.10+0"

[[FFMPEG]]
deps = ["FFMPEG_jll"]
git-tree-sha1 = "b57e3acbe22f8484b4b5ff66a7499717fe1a9cc8"
uuid = "c87230d0-a227-11e9-1b43-d7ebe4e7570a"
version = "0.4.1"

[[FFMPEG_jll]]
deps = ["Artifacts", "Bzip2_jll", "FreeType2_jll", "FriBidi_jll", "JLLWrappers", "LAME_jll", "Libdl", "Ogg_jll", "OpenSSL_jll", "Opus_jll", "Pkg", "Zlib_jll", "libass_jll", "libfdk_aac_jll", "libvorbis_jll", "x264_jll", "x265_jll"]
git-tree-sha1 = "d8a578692e3077ac998b50c0217dfd67f21d1e5f"
uuid = "b22a6f82-2f65-5046-a5b2-351ab43fb4e5"
version = "4.4.0+0"

[[FixedPointNumbers]]
deps = ["Statistics"]
git-tree-sha1 = "335bfdceacc84c5cdf16aadc768aa5ddfc5383cc"
uuid = "53c48c17-4a7d-5ca2-90c5-79b7896eea93"
version = "0.8.4"

[[Fontconfig_jll]]
deps = ["Artifacts", "Bzip2_jll", "Expat_jll", "FreeType2_jll", "JLLWrappers", "Libdl", "Libuuid_jll", "Pkg", "Zlib_jll"]
git-tree-sha1 = "21efd19106a55620a188615da6d3d06cd7f6ee03"
uuid = "a3f928ae-7b40-5064-980b-68af3947d34b"
version = "2.13.93+0"

[[Formatting]]
deps = ["Printf"]
git-tree-sha1 = "8339d61043228fdd3eb658d86c926cb282ae72a8"
uuid = "59287772-0a20-5a39-b81b-1366585eb4c0"
version = "0.4.2"

[[FreeType2_jll]]
deps = ["Artifacts", "Bzip2_jll", "JLLWrappers", "Libdl", "Pkg", "Zlib_jll"]
git-tree-sha1 = "87eb71354d8ec1a96d4a7636bd57a7347dde3ef9"
uuid = "d7e528f0-a631-5988-bf34-fe36492bcfd7"
version = "2.10.4+0"

[[FriBidi_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "aa31987c2ba8704e23c6c8ba8a4f769d5d7e4f91"
uuid = "559328eb-81f9-559d-9380-de523a88c83c"
version = "1.0.10+0"

[[GLFW_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Libglvnd_jll", "Pkg", "Xorg_libXcursor_jll", "Xorg_libXi_jll", "Xorg_libXinerama_jll", "Xorg_libXrandr_jll"]
git-tree-sha1 = "dba1e8614e98949abfa60480b13653813d8f0157"
uuid = "0656b61e-2033-5cc2-a64a-77c0f6c09b89"
version = "3.3.5+0"

[[GR]]
deps = ["Base64", "DelimitedFiles", "GR_jll", "HTTP", "JSON", "Libdl", "LinearAlgebra", "Pkg", "Printf", "Random", "Serialization", "Sockets", "Test", "UUIDs"]
git-tree-sha1 = "182da592436e287758ded5be6e32c406de3a2e47"
uuid = "28b8d3ca-fb5f-59d9-8090-bfdbd6d07a71"
version = "0.58.1"

[[GR_jll]]
deps = ["Artifacts", "Bzip2_jll", "Cairo_jll", "FFMPEG_jll", "Fontconfig_jll", "GLFW_jll", "JLLWrappers", "JpegTurbo_jll", "Libdl", "Libtiff_jll", "Pixman_jll", "Pkg", "Qt5Base_jll", "Zlib_jll", "libpng_jll"]
git-tree-sha1 = "ef49a187604f865f4708c90e3f431890724e9012"
uuid = "d2c73de3-f751-5644-a686-071e5b155ba9"
version = "0.59.0+0"

[[GeometryBasics]]
deps = ["EarCut_jll", "IterTools", "LinearAlgebra", "StaticArrays", "StructArrays", "Tables"]
git-tree-sha1 = "58bcdf5ebc057b085e58d95c138725628dd7453c"
uuid = "5c1252a2-5f33-56bf-86c9-59e7332b4326"
version = "0.4.1"

[[Gettext_jll]]
deps = ["Artifacts", "CompilerSupportLibraries_jll", "JLLWrappers", "Libdl", "Libiconv_jll", "Pkg", "XML2_jll"]
git-tree-sha1 = "9b02998aba7bf074d14de89f9d37ca24a1a0b046"
uuid = "78b55507-aeef-58d4-861c-77aaff3498b1"
version = "0.21.0+0"

[[Glib_jll]]
deps = ["Artifacts", "Gettext_jll", "JLLWrappers", "Libdl", "Libffi_jll", "Libiconv_jll", "Libmount_jll", "PCRE_jll", "Pkg", "Zlib_jll"]
git-tree-sha1 = "7bf67e9a481712b3dbe9cb3dac852dc4b1162e02"
uuid = "7746bdde-850d-59dc-9ae8-88ece973131d"
version = "2.68.3+0"

[[GraphPlot]]
deps = ["ArnoldiMethod", "ColorTypes", "Colors", "Compose", "DelimitedFiles", "LightGraphs", "LinearAlgebra", "Random", "SparseArrays"]
git-tree-sha1 = "dd8f15128a91b0079dfe3f4a4a1e190e54ac7164"
uuid = "a2cc645c-3eea-5389-862e-a155d0052231"
version = "0.4.4"

[[Graphite2_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "344bf40dcab1073aca04aa0df4fb092f920e4011"
uuid = "3b182d85-2403-5c21-9c21-1e1f0cc25472"
version = "1.3.14+0"

[[Grisu]]
git-tree-sha1 = "53bb909d1151e57e2484c3d1b53e19552b887fb2"
uuid = "42e2da0e-8278-4e71-bc24-59509adca0fe"
version = "1.0.2"

[[HTTP]]
deps = ["Base64", "Dates", "IniFile", "Logging", "MbedTLS", "NetworkOptions", "Sockets", "URIs"]
git-tree-sha1 = "60ed5f1643927479f845b0135bb369b031b541fa"
uuid = "cd3eb016-35fb-5094-929b-558a96fad6f3"
version = "0.9.14"

[[HarfBuzz_jll]]
deps = ["Artifacts", "Cairo_jll", "Fontconfig_jll", "FreeType2_jll", "Glib_jll", "Graphite2_jll", "JLLWrappers", "Libdl", "Libffi_jll", "Pkg"]
git-tree-sha1 = "8a954fed8ac097d5be04921d595f741115c1b2ad"
uuid = "2e76f6c2-a576-52d4-95c1-20adfe4de566"
version = "2.8.1+0"

[[Inflate]]
git-tree-sha1 = "f5fc07d4e706b84f72d54eedcc1c13d92fb0871c"
uuid = "d25df0c9-e2be-5dd7-82c8-3ad0b3e990b9"
version = "0.1.2"

[[IniFile]]
deps = ["Test"]
git-tree-sha1 = "098e4d2c533924c921f9f9847274f2ad89e018b8"
uuid = "83e8ac13-25f8-5344-8a64-a9f2b223428f"
version = "0.5.0"

[[InteractiveUtils]]
deps = ["Markdown"]
uuid = "b77e0a4c-d291-57a0-90e8-8db25a27a240"

[[IterTools]]
git-tree-sha1 = "05110a2ab1fc5f932622ffea2a003221f4782c18"
uuid = "c8e1da08-722c-5040-9ed9-7db0dc04731e"
version = "1.3.0"

[[IteratorInterfaceExtensions]]
git-tree-sha1 = "a3f24677c21f5bbe9d2a714f95dcd58337fb2856"
uuid = "82899510-4779-5014-852e-03e436cf321d"
version = "1.0.0"

[[JLLWrappers]]
deps = ["Preferences"]
git-tree-sha1 = "642a199af8b68253517b80bd3bfd17eb4e84df6e"
uuid = "692b3bcd-3c85-4b1f-b108-f13ce0eb3210"
version = "1.3.0"

[[JSON]]
deps = ["Dates", "Mmap", "Parsers", "Unicode"]
git-tree-sha1 = "8076680b162ada2a031f707ac7b4953e30667a37"
uuid = "682c06a0-de6a-54ab-a142-c8b1cf79cde6"
version = "0.21.2"

[[JpegTurbo_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "d735490ac75c5cb9f1b00d8b5509c11984dc6943"
uuid = "aacddb02-875f-59d6-b918-886e6ef4fbf8"
version = "2.1.0+0"

[[LAME_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "f6250b16881adf048549549fba48b1161acdac8c"
uuid = "c1c5ebd0-6772-5130-a774-d5fcae4a789d"
version = "3.100.1+0"

[[LZO_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "e5b909bcf985c5e2605737d2ce278ed791b89be6"
uuid = "dd4b983a-f0e5-5f8d-a1b7-129d4a5fb1ac"
version = "2.10.1+0"

[[LaTeXStrings]]
git-tree-sha1 = "c7f1c695e06c01b95a67f0cd1d34994f3e7db104"
uuid = "b964fa9f-0449-5b57-a5c2-d3ea65f4040f"
version = "1.2.1"

[[Latexify]]
deps = ["Formatting", "InteractiveUtils", "LaTeXStrings", "MacroTools", "Markdown", "Printf", "Requires"]
git-tree-sha1 = "a4b12a1bd2ebade87891ab7e36fdbce582301a92"
uuid = "23fbe1c1-3f47-55db-b15f-69d7ec21a316"
version = "0.15.6"

[[LibCURL]]
deps = ["LibCURL_jll", "MozillaCACerts_jll"]
uuid = "b27032c2-a3e7-50c8-80cd-2d36dbcbfd21"

[[LibCURL_jll]]
deps = ["Artifacts", "LibSSH2_jll", "Libdl", "MbedTLS_jll", "Zlib_jll", "nghttp2_jll"]
uuid = "deac9b47-8bc7-5906-a0fe-35ac56dc84c0"

[[LibGit2]]
deps = ["Base64", "NetworkOptions", "Printf", "SHA"]
uuid = "76f85450-5226-5b5a-8eaa-529ad045b433"

[[LibSSH2_jll]]
deps = ["Artifacts", "Libdl", "MbedTLS_jll"]
uuid = "29816b5a-b9ab-546f-933c-edad1886dfa8"

[[Libdl]]
uuid = "8f399da3-3557-5675-b5ff-fb832c97cbdb"

[[Libffi_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "761a393aeccd6aa92ec3515e428c26bf99575b3b"
uuid = "e9f186c6-92d2-5b65-8a66-fee21dc1b490"
version = "3.2.2+0"

[[Libgcrypt_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Libgpg_error_jll", "Pkg"]
git-tree-sha1 = "64613c82a59c120435c067c2b809fc61cf5166ae"
uuid = "d4300ac3-e22c-5743-9152-c294e39db1e4"
version = "1.8.7+0"

[[Libglvnd_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll", "Xorg_libXext_jll"]
git-tree-sha1 = "7739f837d6447403596a75d19ed01fd08d6f56bf"
uuid = "7e76a0d4-f3c7-5321-8279-8d96eeed0f29"
version = "1.3.0+3"

[[Libgpg_error_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "c333716e46366857753e273ce6a69ee0945a6db9"
uuid = "7add5ba3-2f88-524e-9cd5-f83b8a55f7b8"
version = "1.42.0+0"

[[Libiconv_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "42b62845d70a619f063a7da093d995ec8e15e778"
uuid = "94ce4f54-9a6c-5748-9c1c-f9c7231a4531"
version = "1.16.1+1"

[[Libmount_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "9c30530bf0effd46e15e0fdcf2b8636e78cbbd73"
uuid = "4b2f31a3-9ecc-558c-b454-b3730dcb73e9"
version = "2.35.0+0"

[[Libtiff_jll]]
deps = ["Artifacts", "JLLWrappers", "JpegTurbo_jll", "Libdl", "Pkg", "Zlib_jll", "Zstd_jll"]
git-tree-sha1 = "340e257aada13f95f98ee352d316c3bed37c8ab9"
uuid = "89763e89-9b03-5906-acba-b20f662cd828"
version = "4.3.0+0"

[[Libuuid_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "7f3efec06033682db852f8b3bc3c1d2b0a0ab066"
uuid = "38a345b3-de98-5d2b-a5d3-14cd9215e700"
version = "2.36.0+0"

[[LightGraphs]]
deps = ["ArnoldiMethod", "DataStructures", "Distributed", "Inflate", "LinearAlgebra", "Random", "SharedArrays", "SimpleTraits", "SparseArrays", "Statistics"]
git-tree-sha1 = "432428df5f360964040ed60418dd5601ecd240b6"
uuid = "093fc24a-ae57-5d10-9952-331d41423f4d"
version = "1.3.5"

[[LinearAlgebra]]
deps = ["Libdl"]
uuid = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"

[[Logging]]
uuid = "56ddb016-857b-54e1-b83d-db4d58db5568"

[[MacroTools]]
deps = ["Markdown", "Random"]
git-tree-sha1 = "0fb723cd8c45858c22169b2e42269e53271a6df7"
uuid = "1914dd2f-81c6-5fcd-8719-6d5c9610ff09"
version = "0.5.7"

[[Markdown]]
deps = ["Base64"]
uuid = "d6f4376e-aef5-505a-96c1-9c027394607a"

[[MbedTLS]]
deps = ["Dates", "MbedTLS_jll", "Random", "Sockets"]
git-tree-sha1 = "1c38e51c3d08ef2278062ebceade0e46cefc96fe"
uuid = "739be429-bea8-5141-9913-cc70e7f3736d"
version = "1.0.3"

[[MbedTLS_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "c8ffd9c3-330d-5841-b78e-0817d7145fa1"

[[Measures]]
git-tree-sha1 = "e498ddeee6f9fdb4551ce855a46f54dbd900245f"
uuid = "442fdcdd-2543-5da2-b0f3-8c86c306513e"
version = "0.3.1"

[[Missings]]
deps = ["DataAPI"]
git-tree-sha1 = "2ca267b08821e86c5ef4376cffed98a46c2cb205"
uuid = "e1d29d7a-bbdc-5cf2-9ac0-f12de2c33e28"
version = "1.0.1"

[[Mmap]]
uuid = "a63ad114-7e13-5084-954f-fe012c677804"

[[MozillaCACerts_jll]]
uuid = "14a3606d-f60d-562e-9121-12d972cd8159"

[[NaNMath]]
git-tree-sha1 = "bfe47e760d60b82b66b61d2d44128b62e3a369fb"
uuid = "77ba4419-2d1f-58cd-9bb1-8ffee604a2e3"
version = "0.3.5"

[[NearestNeighbors]]
deps = ["Distances", "StaticArrays"]
git-tree-sha1 = "16baacfdc8758bc374882566c9187e785e85c2f0"
uuid = "b8a86587-4115-5ab1-83bc-aa920d37bbce"
version = "0.4.9"

[[NetworkOptions]]
uuid = "ca575930-c2e3-43a9-ace4-1e988b2c1908"

[[Ogg_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "7937eda4681660b4d6aeeecc2f7e1c81c8ee4e2f"
uuid = "e7412a2a-1a6e-54c0-be00-318e2571c051"
version = "1.3.5+0"

[[OpenSSL_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "15003dcb7d8db3c6c857fda14891a539a8f2705a"
uuid = "458c3c95-2e84-50aa-8efc-19380b2a3a95"
version = "1.1.10+0"

[[Opus_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "51a08fb14ec28da2ec7a927c4337e4332c2a4720"
uuid = "91d4177d-7536-5919-b921-800302f37372"
version = "1.3.2+0"

[[OrderedCollections]]
git-tree-sha1 = "85f8e6578bf1f9ee0d11e7bb1b1456435479d47c"
uuid = "bac558e1-5e72-5ebc-8fee-abe8a469f55d"
version = "1.4.1"

[[PCRE_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "b2a7af664e098055a7529ad1a900ded962bca488"
uuid = "2f80f16e-611a-54ab-bc61-aa92de5b98fc"
version = "8.44.0+0"

[[Parsers]]
deps = ["Dates"]
git-tree-sha1 = "438d35d2d95ae2c5e8780b330592b6de8494e779"
uuid = "69de0a69-1ddd-5017-9359-2bf0b02dc9f0"
version = "2.0.3"

[[Pixman_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "b4f5d02549a10e20780a24fce72bea96b6329e29"
uuid = "30392449-352a-5448-841d-b1acce4e97dc"
version = "0.40.1+0"

[[Pkg]]
deps = ["Artifacts", "Dates", "Downloads", "LibGit2", "Libdl", "Logging", "Markdown", "Printf", "REPL", "Random", "SHA", "Serialization", "TOML", "Tar", "UUIDs", "p7zip_jll"]
uuid = "44cfe95a-1eb2-52ea-b672-e2afdf69b78f"

[[PlotThemes]]
deps = ["PlotUtils", "Requires", "Statistics"]
git-tree-sha1 = "a3a964ce9dc7898193536002a6dd892b1b5a6f1d"
uuid = "ccf2f8ad-2431-5c83-bf29-c5338b663b6a"
version = "2.0.1"

[[PlotUtils]]
deps = ["ColorSchemes", "Colors", "Dates", "Printf", "Random", "Reexport", "Statistics"]
git-tree-sha1 = "9ff1c70190c1c30aebca35dc489f7411b256cd23"
uuid = "995b91a9-d308-5afd-9ec6-746e21dbc043"
version = "1.0.13"

[[Plots]]
deps = ["Base64", "Contour", "Dates", "Downloads", "FFMPEG", "FixedPointNumbers", "GR", "GeometryBasics", "JSON", "Latexify", "LinearAlgebra", "Measures", "NaNMath", "PlotThemes", "PlotUtils", "Printf", "REPL", "Random", "RecipesBase", "RecipesPipeline", "Reexport", "Requires", "Scratch", "Showoff", "SparseArrays", "Statistics", "StatsBase", "UUIDs"]
git-tree-sha1 = "2dbafeadadcf7dadff20cd60046bba416b4912be"
uuid = "91a5bcdd-55d7-5caf-9e0b-520d859cae80"
version = "1.21.3"

[[PlutoUI]]
deps = ["Base64", "Dates", "InteractiveUtils", "JSON", "Logging", "Markdown", "Random", "Reexport", "Suppressor"]
git-tree-sha1 = "44e225d5837e2a2345e69a1d1e01ac2443ff9fcb"
uuid = "7f904dfe-b85e-4ff6-b463-dae2292396a8"
version = "0.7.9"

[[Preferences]]
deps = ["TOML"]
git-tree-sha1 = "00cfd92944ca9c760982747e9a1d0d5d86ab1e5a"
uuid = "21216c6a-2e73-6563-6e65-726566657250"
version = "1.2.2"

[[Printf]]
deps = ["Unicode"]
uuid = "de0858da-6303-5e67-8744-51eddeeeb8d7"

[[Qt5Base_jll]]
deps = ["Artifacts", "CompilerSupportLibraries_jll", "Fontconfig_jll", "Glib_jll", "JLLWrappers", "Libdl", "Libglvnd_jll", "OpenSSL_jll", "Pkg", "Xorg_libXext_jll", "Xorg_libxcb_jll", "Xorg_xcb_util_image_jll", "Xorg_xcb_util_keysyms_jll", "Xorg_xcb_util_renderutil_jll", "Xorg_xcb_util_wm_jll", "Zlib_jll", "xkbcommon_jll"]
git-tree-sha1 = "ad368663a5e20dbb8d6dc2fddeefe4dae0781ae8"
uuid = "ea2cea3b-5b76-57ae-a6ef-0a8af62496e1"
version = "5.15.3+0"

[[REPL]]
deps = ["InteractiveUtils", "Markdown", "Sockets", "Unicode"]
uuid = "3fa0cd96-eef1-5676-8a61-b3b8758bbffb"

[[Random]]
deps = ["Serialization"]
uuid = "9a3f8284-a2c9-5f02-9a11-845980a1fd5c"

[[RecipesBase]]
git-tree-sha1 = "44a75aa7a527910ee3d1751d1f0e4148698add9e"
uuid = "3cdcf5f2-1ef4-517c-9805-6587b60abb01"
version = "1.1.2"

[[RecipesPipeline]]
deps = ["Dates", "NaNMath", "PlotUtils", "RecipesBase"]
git-tree-sha1 = "d4491becdc53580c6dadb0f6249f90caae888554"
uuid = "01d81517-befc-4cb6-b9ec-a95719d0359c"
version = "0.4.0"

[[Reexport]]
git-tree-sha1 = "45e428421666073eab6f2da5c9d310d99bb12f9b"
uuid = "189a3867-3050-52da-a836-e630ba90ab69"
version = "1.2.2"

[[Requires]]
deps = ["UUIDs"]
git-tree-sha1 = "4036a3bd08ac7e968e27c203d45f5fff15020621"
uuid = "ae029012-a4dd-5104-9daa-d747884805df"
version = "1.1.3"

[[SHA]]
uuid = "ea8e919c-243c-51af-8825-aaa63cd721ce"

[[Scratch]]
deps = ["Dates"]
git-tree-sha1 = "0b4b7f1393cff97c33891da2a0bf69c6ed241fda"
uuid = "6c6a2e73-6563-6170-7368-637461726353"
version = "1.1.0"

[[Serialization]]
uuid = "9e88b42a-f829-5b0c-bbe9-9e923198166b"

[[SharedArrays]]
deps = ["Distributed", "Mmap", "Random", "Serialization"]
uuid = "1a1011a3-84de-559e-8e89-a11a2f7dc383"

[[Showoff]]
deps = ["Dates", "Grisu"]
git-tree-sha1 = "91eddf657aca81df9ae6ceb20b959ae5653ad1de"
uuid = "992d4aef-0814-514b-bc4d-f2e9a6c4116f"
version = "1.0.3"

[[SimpleTraits]]
deps = ["InteractiveUtils", "MacroTools"]
git-tree-sha1 = "5d7e3f4e11935503d3ecaf7186eac40602e7d231"
uuid = "699a6c99-e7fa-54fc-8d76-47d257e15c1d"
version = "0.9.4"

[[Sockets]]
uuid = "6462fe0b-24de-5631-8697-dd941f90decc"

[[SortingAlgorithms]]
deps = ["DataStructures"]
git-tree-sha1 = "b3363d7460f7d098ca0912c69b082f75625d7508"
uuid = "a2af1166-a08f-5f64-846c-94a0d3cef48c"
version = "1.0.1"

[[SparseArrays]]
deps = ["LinearAlgebra", "Random"]
uuid = "2f01184e-e22b-5df5-ae63-d93ebab69eaf"

[[StaticArrays]]
deps = ["LinearAlgebra", "Random", "Statistics"]
git-tree-sha1 = "3240808c6d463ac46f1c1cd7638375cd22abbccb"
uuid = "90137ffa-7385-5640-81b9-e52037218182"
version = "1.2.12"

[[Statistics]]
deps = ["LinearAlgebra", "SparseArrays"]
uuid = "10745b16-79ce-11e8-11f9-7d13ad32a3b2"

[[StatsAPI]]
git-tree-sha1 = "1958272568dc176a1d881acb797beb909c785510"
uuid = "82ae8749-77ed-4fe6-ae5f-f523153014b0"
version = "1.0.0"

[[StatsBase]]
deps = ["DataAPI", "DataStructures", "LinearAlgebra", "Missings", "Printf", "Random", "SortingAlgorithms", "SparseArrays", "Statistics", "StatsAPI"]
git-tree-sha1 = "8cbbc098554648c84f79a463c9ff0fd277144b6c"
uuid = "2913bbd2-ae8a-5f71-8c99-4fb6c76f3a91"
version = "0.33.10"

[[StructArrays]]
deps = ["Adapt", "DataAPI", "StaticArrays", "Tables"]
git-tree-sha1 = "1700b86ad59348c0f9f68ddc95117071f947072d"
uuid = "09ab397b-f2b6-538f-b94a-2f83cf4a842a"
version = "0.6.1"

[[Suppressor]]
git-tree-sha1 = "a819d77f31f83e5792a76081eee1ea6342ab8787"
uuid = "fd094767-a336-5f1f-9728-57cf17d0bbfb"
version = "0.2.0"

[[TOML]]
deps = ["Dates"]
uuid = "fa267f1f-6049-4f14-aa54-33bafae1ed76"

[[TableTraits]]
deps = ["IteratorInterfaceExtensions"]
git-tree-sha1 = "c06b2f539df1c6efa794486abfb6ed2022561a39"
uuid = "3783bdb8-4a98-5b6b-af9a-565f29a5fe9c"
version = "1.0.1"

[[Tables]]
deps = ["DataAPI", "DataValueInterfaces", "IteratorInterfaceExtensions", "LinearAlgebra", "TableTraits", "Test"]
git-tree-sha1 = "d0c690d37c73aeb5ca063056283fde5585a41710"
uuid = "bd369af6-aec1-5ad0-b16a-f7cc5008161c"
version = "1.5.0"

[[Tar]]
deps = ["ArgTools", "SHA"]
uuid = "a4e569a6-e804-4fa4-b0f3-eef7a1d5b13e"

[[Test]]
deps = ["InteractiveUtils", "Logging", "Random", "Serialization"]
uuid = "8dfed614-e22c-5e08-85e1-65c5234f0b40"

[[URIs]]
git-tree-sha1 = "97bbe755a53fe859669cd907f2d96aee8d2c1355"
uuid = "5c2747f8-b7ea-4ff2-ba2e-563bfd36b1d4"
version = "1.3.0"

[[UUIDs]]
deps = ["Random", "SHA"]
uuid = "cf7118a7-6976-5b1a-9a39-7adc72f591a4"

[[Unicode]]
uuid = "4ec0a83e-493e-50e2-b9ac-8f72acf5a8f5"

[[Wayland_jll]]
deps = ["Artifacts", "Expat_jll", "JLLWrappers", "Libdl", "Libffi_jll", "Pkg", "XML2_jll"]
git-tree-sha1 = "3e61f0b86f90dacb0bc0e73a0c5a83f6a8636e23"
uuid = "a2964d1f-97da-50d4-b82a-358c7fce9d89"
version = "1.19.0+0"

[[Wayland_protocols_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Wayland_jll"]
git-tree-sha1 = "2839f1c1296940218e35df0bbb220f2a79686670"
uuid = "2381bf8a-dfd0-557d-9999-79630e7b1b91"
version = "1.18.0+4"

[[XML2_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Libiconv_jll", "Pkg", "Zlib_jll"]
git-tree-sha1 = "1acf5bdf07aa0907e0a37d3718bb88d4b687b74a"
uuid = "02c8fc9c-b97f-50b9-bbe4-9be30ff0a78a"
version = "2.9.12+0"

[[XSLT_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Libgcrypt_jll", "Libgpg_error_jll", "Libiconv_jll", "Pkg", "XML2_jll", "Zlib_jll"]
git-tree-sha1 = "91844873c4085240b95e795f692c4cec4d805f8a"
uuid = "aed1982a-8fda-507f-9586-7b0439959a61"
version = "1.1.34+0"

[[Xorg_libX11_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libxcb_jll", "Xorg_xtrans_jll"]
git-tree-sha1 = "5be649d550f3f4b95308bf0183b82e2582876527"
uuid = "4f6342f7-b3d2-589e-9d20-edeb45f2b2bc"
version = "1.6.9+4"

[[Xorg_libXau_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "4e490d5c960c314f33885790ed410ff3a94ce67e"
uuid = "0c0b7dd1-d40b-584c-a123-a41640f87eec"
version = "1.0.9+4"

[[Xorg_libXcursor_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libXfixes_jll", "Xorg_libXrender_jll"]
git-tree-sha1 = "12e0eb3bc634fa2080c1c37fccf56f7c22989afd"
uuid = "935fb764-8cf2-53bf-bb30-45bb1f8bf724"
version = "1.2.0+4"

[[Xorg_libXdmcp_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "4fe47bd2247248125c428978740e18a681372dd4"
uuid = "a3789734-cfe1-5b06-b2d0-1dd0d9d62d05"
version = "1.1.3+4"

[[Xorg_libXext_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll"]
git-tree-sha1 = "b7c0aa8c376b31e4852b360222848637f481f8c3"
uuid = "1082639a-0dae-5f34-9b06-72781eeb8cb3"
version = "1.3.4+4"

[[Xorg_libXfixes_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll"]
git-tree-sha1 = "0e0dc7431e7a0587559f9294aeec269471c991a4"
uuid = "d091e8ba-531a-589c-9de9-94069b037ed8"
version = "5.0.3+4"

[[Xorg_libXi_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libXext_jll", "Xorg_libXfixes_jll"]
git-tree-sha1 = "89b52bc2160aadc84d707093930ef0bffa641246"
uuid = "a51aa0fd-4e3c-5386-b890-e753decda492"
version = "1.7.10+4"

[[Xorg_libXinerama_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libXext_jll"]
git-tree-sha1 = "26be8b1c342929259317d8b9f7b53bf2bb73b123"
uuid = "d1454406-59df-5ea1-beac-c340f2130bc3"
version = "1.1.4+4"

[[Xorg_libXrandr_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libXext_jll", "Xorg_libXrender_jll"]
git-tree-sha1 = "34cea83cb726fb58f325887bf0612c6b3fb17631"
uuid = "ec84b674-ba8e-5d96-8ba1-2a689ba10484"
version = "1.5.2+4"

[[Xorg_libXrender_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll"]
git-tree-sha1 = "19560f30fd49f4d4efbe7002a1037f8c43d43b96"
uuid = "ea2f1a96-1ddc-540d-b46f-429655e07cfa"
version = "0.9.10+4"

[[Xorg_libpthread_stubs_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "6783737e45d3c59a4a4c4091f5f88cdcf0908cbb"
uuid = "14d82f49-176c-5ed1-bb49-ad3f5cbd8c74"
version = "0.1.0+3"

[[Xorg_libxcb_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "XSLT_jll", "Xorg_libXau_jll", "Xorg_libXdmcp_jll", "Xorg_libpthread_stubs_jll"]
git-tree-sha1 = "daf17f441228e7a3833846cd048892861cff16d6"
uuid = "c7cfdc94-dc32-55de-ac96-5a1b8d977c5b"
version = "1.13.0+3"

[[Xorg_libxkbfile_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libX11_jll"]
git-tree-sha1 = "926af861744212db0eb001d9e40b5d16292080b2"
uuid = "cc61e674-0454-545c-8b26-ed2c68acab7a"
version = "1.1.0+4"

[[Xorg_xcb_util_image_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xcb_util_jll"]
git-tree-sha1 = "0fab0a40349ba1cba2c1da699243396ff8e94b97"
uuid = "12413925-8142-5f55-bb0e-6d7ca50bb09b"
version = "0.4.0+1"

[[Xorg_xcb_util_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libxcb_jll"]
git-tree-sha1 = "e7fd7b2881fa2eaa72717420894d3938177862d1"
uuid = "2def613f-5ad1-5310-b15b-b15d46f528f5"
version = "0.4.0+1"

[[Xorg_xcb_util_keysyms_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xcb_util_jll"]
git-tree-sha1 = "d1151e2c45a544f32441a567d1690e701ec89b00"
uuid = "975044d2-76e6-5fbe-bf08-97ce7c6574c7"
version = "0.4.0+1"

[[Xorg_xcb_util_renderutil_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xcb_util_jll"]
git-tree-sha1 = "dfd7a8f38d4613b6a575253b3174dd991ca6183e"
uuid = "0d47668e-0667-5a69-a72c-f761630bfb7e"
version = "0.3.9+1"

[[Xorg_xcb_util_wm_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xcb_util_jll"]
git-tree-sha1 = "e78d10aab01a4a154142c5006ed44fd9e8e31b67"
uuid = "c22f9ab0-d5fe-5066-847c-f4bb1cd4e361"
version = "0.4.1+1"

[[Xorg_xkbcomp_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_libxkbfile_jll"]
git-tree-sha1 = "4bcbf660f6c2e714f87e960a171b119d06ee163b"
uuid = "35661453-b289-5fab-8a00-3d9160c6a3a4"
version = "1.4.2+4"

[[Xorg_xkeyboard_config_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Xorg_xkbcomp_jll"]
git-tree-sha1 = "5c8424f8a67c3f2209646d4425f3d415fee5931d"
uuid = "33bec58e-1273-512f-9401-5d533626f822"
version = "2.27.0+4"

[[Xorg_xtrans_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "79c31e7844f6ecf779705fbc12146eb190b7d845"
uuid = "c5fb5394-a638-5e4d-96e5-b29de1b5cf10"
version = "1.4.0+3"

[[Zlib_jll]]
deps = ["Libdl"]
uuid = "83775a58-1f1d-513f-b197-d71354ab007a"

[[Zstd_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "cc4bf3fdde8b7e3e9fa0351bdeedba1cf3b7f6e6"
uuid = "3161d3a3-bdf6-5164-811a-617609db77b4"
version = "1.5.0+0"

[[libass_jll]]
deps = ["Artifacts", "Bzip2_jll", "FreeType2_jll", "FriBidi_jll", "HarfBuzz_jll", "JLLWrappers", "Libdl", "Pkg", "Zlib_jll"]
git-tree-sha1 = "5982a94fcba20f02f42ace44b9894ee2b140fe47"
uuid = "0ac62f75-1d6f-5e53-bd7c-93b484bb37c0"
version = "0.15.1+0"

[[libfdk_aac_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "daacc84a041563f965be61859a36e17c4e4fcd55"
uuid = "f638f0a6-7fb0-5443-88ba-1cc74229b280"
version = "2.0.2+0"

[[libpng_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Zlib_jll"]
git-tree-sha1 = "94d180a6d2b5e55e447e2d27a29ed04fe79eb30c"
uuid = "b53b4c65-9356-5827-b1ea-8c7a1a84506f"
version = "1.6.38+0"

[[libvorbis_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Ogg_jll", "Pkg"]
git-tree-sha1 = "c45f4e40e7aafe9d086379e5578947ec8b95a8fb"
uuid = "f27f6e37-5d2b-51aa-960f-b287f2bc3b7a"
version = "1.3.7+0"

[[nghttp2_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "8e850ede-7688-5339-a07c-302acd2aaf8d"

[[p7zip_jll]]
deps = ["Artifacts", "Libdl"]
uuid = "3f19e933-33d8-53b3-aaab-bd5110c3b7a0"

[[x264_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "4fea590b89e6ec504593146bf8b988b2c00922b2"
uuid = "1270edf5-f2f9-52d2-97e9-ab00b5d0237a"
version = "2021.5.5+0"

[[x265_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg"]
git-tree-sha1 = "ee567a171cce03570d77ad3a43e90218e38937a9"
uuid = "dfaa095f-4041-5dcd-9319-2fabd8486b76"
version = "3.5.0+0"

[[xkbcommon_jll]]
deps = ["Artifacts", "JLLWrappers", "Libdl", "Pkg", "Wayland_jll", "Wayland_protocols_jll", "Xorg_libxcb_jll", "Xorg_xkeyboard_config_jll"]
git-tree-sha1 = "ece2350174195bb31de1a63bea3a41ae1aa593b6"
uuid = "d8fb68d0-12a3-5cfd-a85a-d49703b185fd"
version = "0.9.1+5"
"""

# ╔═╡ Cell order:
# ╠═94dde840-54f6-4fe4-846b-bc15f8fca9fa
# ╠═c9cf879e-0b01-4e0a-b31c-2ca5c6f03e63
# ╟─81efb137-7e14-4091-a7f0-c6b72e2d77f7
# ╟─75cd6187-4c51-426c-8a3c-d7b6c922ae0b
# ╟─639758a5-413d-408a-ace9-3741322c3dc2
# ╠═f05bae5c-8d1c-4f68-a299-fab3af2432ae
# ╠═d367f447-16e1-4cbc-b05f-b807d4ef955b
# ╠═9438ace8-4290-4caa-bb34-24c1c8f4f66a
# ╠═357b8af9-700a-4a2d-9703-575af5b9ab13
# ╠═085b49b4-08a2-4e6e-8cbe-6a011a93b551
# ╠═280049be-261e-49d7-a6fc-2211afe94e06
# ╠═64730ce5-61b4-405d-9a41-81d0253a4713
# ╠═692cbb97-2a5f-42c9-b829-e08d5e7479a8
# ╟─662b7b01-883f-4d51-b696-26f7559e0211
# ╠═55d217d5-c31a-431d-bd46-f9f09280cf5b
# ╠═3f815c3e-850d-4ca7-af1c-a2ff14e429db
# ╠═967b8e40-1f95-11eb-0aa1-8f4592054357
# ╠═708a16c5-f755-490b-abcb-89788813b7d0
# ╠═c298ccfe-f15e-4652-baa7-c122cb22f22f
# ╠═7c72773d-0915-4ef0-aa7e-7f0474426bfa
# ╠═9d8aef37-9640-4d67-9c33-bb6513938ae1
# ╟─00000000-0000-0000-0000-000000000001
# ╟─00000000-0000-0000-0000-000000000002

max_stars_repo_path: Lectures/C3 Spectral Graph K-partitioning.jl


text:
using Catlab
using Catlab.Theories

export crand

# How do you give semantics to a stochastic map? You call it.
function crand(f::FreeCartesianCategory.Hom{:generator}, args...)
    f.args[1](args...)
end

# Compositional structure
crand(f::FreeCartesianCategory.Hom{:id}, args...) = (args)
function crand(f::FreeCartesianCategory.Hom{:compose}, args...)
    if length(f.args) > 2
        return crand(f.args[end], crand(compose(f.args[1:end-1]...), args...)...)
    end
    return crand(f.args[end], crand(f.args[1], args...)...)
end

# Monoidal Structure
function crand(f::FreeCartesianCategory.Hom{:otimes}, args...)
    dims = cumsum(map(ndims∘dom, f.args))
    map(1:length(f.args)) do i
        if i == 1
            crand(f.args[i], args[1:dims[1]]...)
        else
            crand(f.args[i], args[dims[i-1]+1:dims[i]]...)
        end
    end |> xs->filter(xs) do x # handle the () you get from deletes
        x != ()
    end
end
function crand(f::FreeCartesianCategory.Hom{:braid}, args...)
    y = args[1:ndims(f.args[1])]
    x = args[(ndims(f.args[1])+1):end]
    return (x...,y...)
end

# Diagonal Comonoid
crand(f::FreeCartesianCategory.Hom{:mcopy}, args...) = (args..., args...)
crand(f::FreeCartesianCategory.Hom{:delete}, args...) = ()


text:
s = open("input.txt") do file
    readlines(file);
end

function RunProgramUntilRepeat(program)
    seen = Set()

    i = 1;
    acc = 0;
    while !in(i, seen)
        push!(seen, i);
        parts = split(program[i], " ");

        cmd = parts[1];
        num = parse(Int, parts[2]);

        if cmd == "nop"
            i += 1;
        elseif cmd == "acc"
            acc += num;
            i += 1;
        elseif cmd == "jmp"
            i += num
        end
    end

    return acc
end

RunProgramUntilRepeat(s)


text:
using Conv
using Test
using BenchmarkTools
using Calculus
using LinearAlgebra

np=1000
n=777
n2=100
x = randn(n,n2); xa = similar(x)
z = zeros(np,n2);

# cover all lags for serial mode
for i in [0, 2, 4, n-1]
	Conv.pad!(x, z, n-i-1,i,np)
	Conv.truncate!(xa, z, n-i-1,i,np)
	@test x ≈ xa
end
i=4
println("testing memory for pad truncates...")
@btime Conv.pad!(x, z, n-i-1,i,np)
@btime Conv.truncate!(xa, z, n-i-1,i,np)
println("...")

np=1000
n=777
x = randn(n); xa = similar(x)
z = zeros(np);
for i in [0, 2, 4, n-1]
	@time Conv.pad!(x, z, n-i-1,i,np)
	@time Conv.truncate!(xa, z, n-i-1,i,np)
	@test x ≈ xa
end
i=4
println("testing memory for pad truncates...")
@btime Conv.pad!(x, z, n-i-1,i,np)
@btime Conv.truncate!(xa, z, n-i-1,i,np)
println("...")

# fast_filt
# note that this test works for only some delta functions
for nw in [7, 8], nr in [20, 10], ns in [11, 10]

	r = zeros(nr); w = zeros(nw); s = zeros(ns);
	ra = similar(r); wa = similar(w); sa = similar(s);

	r[5]=1.; w[3]=1.;

	Conv.conv!(s,r,w,Conv.D())
	Conv.conv!(s,r,wa,Conv.S())
	@test w ≈ wa

	Conv.conv!(s,ra,w,Conv.G())
	@test ra ≈ r

	Conv.conv!(sa,ra,wa,Conv.D())
	@test sa ≈ s
end

## dot product test for fast filt

function filt_loop(func, n2; )
	nwvec=[101, 100]
	nrvec=[1000, 1001]
	nsvec=[1500, 901]
	np2=2024;
	for nw in nwvec, nr in nrvec, ns in nsvec

		r=randn(nr, n2...)
		s=randn(ns, n2...)
		w=randn(nw, n2...)
		func(s,r,w,Conv.D())

		sa=randn(ns, n2...);
		ra=similar(r)
		func(sa,ra,w,Conv.G())

		# dot product test
		@test dot(s, sa) ≈ dot(ra, r)

		r=randn(nr, n2...)
		s=randn(ns, n2...)
		w=zeros(nw, n2...)
		func(s,r,w,Conv.S())

		wa=randn(nw, n2...);
		ra=similar(r);
		func(s,ra,wa,Conv.G())

		# dot product test
		@test dot(r, ra) ≈ dot(wa, w)
	end
end

n2=128
@time filt_loop(Conv.conv!, n2)
@time filt_loop(Conv.conv!, n2)

# check if mod! will not have any allocations
n=10000
nr=1
println("====================")
d=randn(n,nr)
g=randn(n,nr)
s=randn(n,nr)
pa=Conv.P_conv(d=d,g=g,s=s, gsize=[n,nr], dsize=[n,nr], ssize=[n,nr]);

@btime Conv.mod!(pa, Conv.D());
@btime Conv.mod!(pa, Conv.D(), d=d, g=g);
@btime Conv.mod!(pa, Conv.G());
@btime Conv.mod!(pa, Conv.S());

n=1000
nr=100
println("====================")
d=randn(n,nr)
g=randn(n,nr)
s=randn(n)
pa=Conv.P_conv(d=d,g=g,s=s, gsize=[n,nr], dsize=[n,nr], ssize=[n]);

@btime Conv.mod!(pa, Conv.D());
@btime Conv.mod!(pa, Conv.D(), d=d, g=g);
@btime Conv.mod!(pa, Conv.G());
@btime Conv.mod!(pa, Conv.S());

println("====================")
d=randn(n,nr)
g=randn(n,nr)
s=randn(n,nr)
pa=Conv.P_conv(d=d,g=g,s=s, gsize=[n,nr], dsize=[n,nr], ssize=[n,nr]);

@btime Conv.mod!(pa, Conv.D());
@btime Conv.mod!(pa, Conv.D(), d=d, g=g);
@btime Conv.mod!(pa, Conv.G());
@btime Conv.mod!(pa, Conv.S());

# =================================================
# weighted norm after auto-correlation
# =================================================
n1=100
n2=10

x=randn(n1,n2);
w=randn(n1,n2);
dfdx1=similar(x);
pa=Conv.P_misfit_weighted_acorr(n1,n2)

@btime Conv.func_grad!(dfdx1,x,pa)
function func(x)
	xx=reshape(x,n1,n2)
	return	Conv.func_grad!(nothing,xx,pa)
end
dfdx2=Calculus.gradient(func,vec(x));

@test dfdx1 ≈ reshape(dfdx2,n1,n2)

# =================================================
# squared euclidean after after xcorr
# =================================================
n1=50
n2=4

x=randn(n1,n2);
y=randn(n1,n2);
dfdx1=similar(x);
pa=Conv.P_misfit_xcorr(n1,n2, y=y)

@btime Conv.func_grad!(dfdx1,x,pa)
function func(x)
	xx=reshape(x,n1,n2)
	return	Conv.func_grad!(nothing,xx,pa)
end
dfdx2=Calculus.gradient(func,vec(x));

@test dfdx1 ≈ reshape(dfdx2,n1,n2)


text:
module NIPALS_PCA

using DataFrames, JLD2, FileIO

include("structs.jl")
include("pca.jl")
include("pls.jl")
include("pls_norm.jl")
include("precompiler/sysimagegen.jl")

function loadIrisData()::DataFrame
    moduleisdefined = @isdefined NIPALS_PCA

    irisdir = @pipe pathof(NIPALS_PCA) |> splitpath |> _[1:end-2] |> joinpath(_...,"test","data","iris")

    CSV.File(joinpath(irisdir,"iris.csv"), header=false) |> DataFrame
end
export loadIrisData

function loadDataFrame(file::String,valuekey::String="df")
    df=load(file,valuekey);
end
export loadDataFrame

export sysimagegen

#structs
export Dataset, PCA, PLS

export calcPCA, calcPLS, Dataset, parseDataFrame, parseMatrix, normalize, normalize!, savemodel,loadmodel,predictY
export crossvalidate, selectNumerical, selectColumns,onehot,predictLevel,calcVariances
export filterDataset

# pls norm
export correct,calibrate_model,predict_xres

end # module


text:
export
    StraightRoadway,
    State1D,
    LaneFollowingAccel,
    Vehicle1D,
    Scene1D,
    AgentClass,
    VehicleDef,

    DEFAULT_VEHICLE_DEF,
    NULL_VEHICLEDEF,

    mod_position_to_roadway,
    get_neighbor_fore,
    get_neighbor_rear,
    get_headway

include("straight_roadway.jl")
include("definitions.jl")
include("states.jl")
include("vehicles.jl")
include("actions.jl")
include("drivers/main.jl")


text:
module KilliFeeder

using Dates, StatsBase, SQLite, DelimitedFiles, IterableTables, Plots, DataStructures, Compose, Pkg

#println("including scripts")

include("esp8266flash.jl")
include("serverfxns.jl")
include("guifxns.jl")
include("watchmanfxns.jl")

#println("loading config")

global conf = load_config()

end


text:
export fast_αscheme
function fast_αscheme(
    m::Int64, n::Int64, h::Float64,
    M::Union{SparseTensor, SparseMatrixCSC},
    C::Union{SparseTensor, SparseMatrixCSC},
    K::Union{SparseTensor, SparseMatrixCSC},
    body_force::Union{Array{Float64}, PyObject},
    d0::Union{Array{Float64, 1}, PyObject},
    v0::Union{Array{Float64, 1}, PyObject},
    a0::Union{Array{Float64, 1}, PyObject},
    Δt::Float64,
    bdnode::Union{Array{Int64, 1}, PyObject, Missing} = missing,
    bd_d::Union{Array{Float64, 2}, PyObject, Missing} = missing,
    bd_v::Union{Array{Float64, 2}, PyObject, Missing} = missing,
    bd_a::Union{Array{Float64, 2}, PyObject, Missing} = missing;
    ρ::Float64 = 1.0)
    nt = size(body_force, 1)
    if !ismissing(bdnode)
        if ismissing(bd_a)
            error("Boundary acceleration at Dirichlet nodes must be provided.")
        end
        for v in [bd_d, bd_v, bd_a]
            if !ismissing(v) && (size(v,1)!= nt || size(v,2)!= 2length(bdnode))
                error("Invalid shape for $v. Expected $(nt)×$(2length(bdnode)) but got $(size(v,1))×$(size(v,2))")
            end
        end
    end
    !ismissing(bd_d) && (bd_d = convert_to_tensor(bd_d, dtype=Float64))
    !ismissing(bd_v) && (bd_v = convert_to_tensor(bd_v, dtype=Float64))
    !ismissing(bd_a) && (bd_a = convert_to_tensor(bd_a, dtype=Float64))

    αm = (2ρ-1)/(ρ+1)
    αf = ρ/(1+ρ)
    γ = 1/2-αm+αf
    β = 0.25*(1-αm+αf)^2
    d = length(d0)

    M = isa(M, SparseMatrixCSC) ? constant(M) : M
    C = isa(C, SparseMatrixCSC) ? constant(C) : C
    K = isa(K, SparseMatrixCSC) ? constant(K) : K
    body_force, d0, v0, a0, Δt = convert_to_tensor([body_force, d0, v0, a0, Δt], [Float64, Float64, Float64, Float64, Float64])

    A = (1-αm)*M + (1-αf)*C*Δt*γ + (1-αf)*K*β*Δt^2
    if !ismissing(bdnode)
        A, Abd = fem_impose_Dirichlet_boundary_condition(A, bdnode, m, n, h)
    else
        Abd = missing
    end
    A = factorize(A)

    function equ(dc, vc, ac, dt, body_force, i)
        dn = dc + dt*vc + dt^2/2*(1-2β)*ac
        vn = vc + dt*((1-γ)*ac)

        df = (1-αf)*dn + αf*dc
        vf = (1-αf)*vn + αf*vc
        am = αm*ac

        rhs = body_force - (M*am + C*vf + K*df)
        if !ismissing(Abd)
            rhs -= Abd * bd_a[i]
            rhs = scatter_update(rhs, [bdnode; bdnode .+ (m+1)*(n+1)], bd_a[i])
        end

        A\rhs
    end

    function condition(i, tas...)
        return i<=nt
    end
    function body(i, tas...)
        dc_arr, vc_arr, ac_arr = tas
        dc = read(dc_arr, i)
        vc = read(vc_arr, i)
        ac = read(ac_arr, i)
        y = equ(dc, vc, ac, Δt, body_force[i], i)
        dn = dc + Δt*vc + Δt^2/2*((1-2β)*ac+2β*y)
        vn = vc + Δt*((1-γ)*ac+γ*y)

        if !ismissing(bd_v)
            vn = scatter_update(vn, [bdnode; bdnode .+ (m+1)*(n+1)], bd_v[i])
        end

        if !ismissing(bd_d)
            dn = scatter_update(dn, [bdnode; bdnode .+ (m+1)*(n+1)], bd_d[i])
        end

        i+1, write(dc_arr, i+1, dn), write(vc_arr, i+1, vn), write(ac_arr, i+1, y)
    end

    dM = TensorArray(nt+1); vM = TensorArray(nt+1); aM = TensorArray(nt+1)
    dM = write(dM, 1, d0)
    vM = write(vM, 1, v0)
    aM = write(aM, 1, a0)
    i = constant(1, dtype=Int32)
    _, d, v, a = while_loop(condition, body, [i,dM, vM, aM])
    set_shape(stack(d), (nt+1, length(d0))), set_shape(stack(v), (nt+1, length(v0))), set_shape(stack(a), (nt+1, length(a0)))
end


text:
# Counter
struct Counter
    counts::Dict{Any, Any}
end

Counter(xs::AbstractVector) = begin
    counts = Dict()
    for x in xs
        counts[x] = 1 + get(counts, x, 0)
    end
    Counter(counts)
end

Base.getindex(cnt::Counter, i) = get(cnt.counts, i, 0)
Base.setindex!(cnt::Counter, v, i) = begin cnt.counts[i] = v end

Base.keys(cnt::Counter)   = Base.keys(cnt.counts)
Base.values(cnt::Counter) = Base.values(cnt.counts)
total(cnt::Counter)  = sum(Base.values(cnt))

# Helpers
weightedsum(xs, ws) = foldl(((s,(x,w)) -> s + w*x), zip(xs, ws); init = 0)

findmajority(xs::AbstractVector) = findmajority(Counter(xs))

findmajority(cnt::Counter) = begin
    reduce((x, y) -> cnt[x] >= cnt[y] ? x : y, keys(cnt))
end

traintestsplit(df::DataFrame, testfraction = 0.3) = begin
    df = DataFrame(shuffle(eachrow(df)))
    k = Int(ceil(testfraction * nrow(df)))
    df[k:end, :], df[1:k, :]
end

# Impurity Measures
gini(xs::AbstractVector) = gini(Counter(xs))

gini(cnt::Counter) = begin
    n = total(cnt)
    1 - sum((c/n)^2 for c in values(cnt))
end

entropy(xs::AbstractArray) = entropy(Counter(xs))

entropy(cnt::Counter) = begin
    n = total(cnt)
    -sum((c/n)*log(2, (c/n)) for c in values(cnt))
end

confusionmatrix(clf, df, topredict, trueclass) = begin
    ytrue = map(x -> x == trueclass, df[:,topredict])
    ypred = map(x -> x == trueclass, predict(clf, df))

    cm = Counter(collect(zip(ytrue, ypred)))
    cm[(true, true)], cm[(true, false)], cm[(false, true)], cm[(false, false)]
end

precisionscore(confusionmatrix) = begin
    tp, fn, fp, tn = confusionmatrix
    tp/(tp+fp)
end

recallscore(confusionmatrix) = begin
    tp, fn, fp, tn = confusionmatrix
    tp/(tp+fn)
end

accuracyscore(confusionmatrix) = begin
    tp, fn, fp, tn = confusionmatrix
    (tp+tn)/(tp+fn+fp+tn)
end

accuracyscore(ytrue, ypred) = begin
    sum(a == b for (a,b) in zip(ytrue, ypred))/length(ytrue)
end

f1score(confusionmatrix) = begin
    tp, fn, fp, tn = confusionmatrix
    tp/(tp + 0.5*(fp + fn))
end


text:
const Q = [
[16 11 10 16 24 40 51 61];
[12 12 14 19 26 58 60 55];
[14 13 16 24 40 57 69 56];
[14 17 22 29 51 87 80 62];
[18 22 37 56 68 109 103 77];
[24 35 55 64 81 104 113 92];
[49 64 78 87 103 121 120 101];
[72 92 95 98 112 100 103 99];
]

function quantize(x::Matrix{Float32})::Matrix{Int}
    return round.(x ./ Q)
end

function unquantize(x::Matrix{Int})::Matrix{Float32}
    return x .* Q
end

function unquantize(x::Matrix{Float64})::Matrix{Float32}
    return unquantize(Int.(round.(x)))
end