text:
module PufferIndicatorFrostHelper

using ..Ahorn, Maple

@mapdef Entity "FrostHelper/PufferIndicator" PufferIndicator(x::Integer, y::Integer, spritePath::String="objects/FrostHelper/pufferIndicator", color::String="ffffff", outlineColor::String="000000")

const placements = Ahorn.PlacementDict(
	"Puffer Indicator (Frost Helper)" => Ahorn.EntityPlacement(
		PufferIndicator
	)
)

function Ahorn.selection(entity::PufferIndicator)
    x, y = Ahorn.position(entity)

	return Ahorn.getSpriteRectangle(get(entity.data, "spritePath", "objects/FrostHelper/pufferIndicator"), x, y)
end

function Ahorn.render(ctx::Ahorn.Cairo.CairoContext, entity::PufferIndicator, room::Maple.Room)
	texture = get(entity.data, "spritePath", "objects/FrostHelper/pufferIndicator")

	rawTint = Ahorn.argb32ToRGBATuple(parse(Int, lstrip(get(entity.data, "color", "ffffff"), [ '#' ]), base=16))[1:3] ./ 255
	realTint = (rawTint..., 1.0)
    Ahorn.drawSprite(ctx, texture, 0, 0, tint = realTint)
end

end

max_stars_repo_name: JaThePlayer/FrostHelper

max_issues_repo_name: JaThePlayer/FrostHelper

max_forks_repo_name: JaThePlayer/FrostHelper


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

mutable struct ApplicationGatewayFrontendPortPropertiesFormat <: SwaggerModel
    port::Any # spec type: Union{ Nothing, Int32 } # spec name: port
    provisioningState::Any # spec type: Union{ Nothing, ProvisioningState } # spec name: provisioningState

    function ApplicationGatewayFrontendPortPropertiesFormat(;port=nothing, provisioningState=nothing)
        o = new()
        validate_property(ApplicationGatewayFrontendPortPropertiesFormat, Symbol("port"), port)
        setfield!(o, Symbol("port"), port)
        validate_property(ApplicationGatewayFrontendPortPropertiesFormat, Symbol("provisioningState"), provisioningState)
        setfield!(o, Symbol("provisioningState"), provisioningState)
        o
    end
end # type ApplicationGatewayFrontendPortPropertiesFormat

const _property_map_ApplicationGatewayFrontendPortPropertiesFormat = Dict{Symbol,Symbol}(Symbol("port")=>Symbol("port"), Symbol("provisioningState")=>Symbol("provisioningState"))
const _property_types_ApplicationGatewayFrontendPortPropertiesFormat = Dict{Symbol,String}(Symbol("port")=>"Int32", Symbol("provisioningState")=>"ProvisioningState")
Base.propertynames(::Type{ ApplicationGatewayFrontendPortPropertiesFormat }) = collect(keys(_property_map_ApplicationGatewayFrontendPortPropertiesFormat))
Swagger.property_type(::Type{ ApplicationGatewayFrontendPortPropertiesFormat }, name::Symbol) = Union{Nothing,eval(Base.Meta.parse(_property_types_ApplicationGatewayFrontendPortPropertiesFormat[name]))}
Swagger.field_name(::Type{ ApplicationGatewayFrontendPortPropertiesFormat }, property_name::Symbol) =  _property_map_ApplicationGatewayFrontendPortPropertiesFormat[property_name]

function check_required(o::ApplicationGatewayFrontendPortPropertiesFormat)
    true
end

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

ext: jl


text:
################################################################################
#  Copyright 2020, Tom Van Acker                                               #
################################################################################
# MultiStateSystems.jl                                                         #
# A Julia package to solve multi-state system models.                          #
# See http://github.com/timmyfaraday/MultiStateSystems.jl                      #
################################################################################

## State-Transition Diagram
# structs
struct STD{I<:Int} <: AbstractSTD{I}
    graph::_LG.DiGraph{I}

    props::PropDict
    sprops::Dict{I,PropDict}
    tprops::Dict{_LG.Edge{I},PropDict}
end

# constructors
function STD(Ns::Int)
    graph = _LG.DiGraph(Ns)

    props = PropDict(:info => STDInfo())
    sprops = Dict{Int,PropDict}(ns => PropDict() for ns in 1:Ns)
    tprops = Dict{_LG.Edge{Int},PropDict}()

    return STD(graph, props, sprops, tprops)
end

"""
    STD(ugf::MultiStateSystems.UGF)

An state-transition diagram constructor based on an universal generating
function `ugf`.

Sets `solved` of the STDInfo to true.

# Example
```julia-repl
julia> ugfᵍᵉⁿ = UGF(:power, [0.0u"MW",0.0u"MW",2.0u"MW"], [0.1,0.2,0.7])
julia> stdᵍᵉⁿ = STD(ugfᵍᵉⁿ)
```
"""
function STD(ugf::AbstractUGF)
    msr, val, prb = ugf.msr, ugf.val, ugf.prb
    msr = Expr(:kw, msr, val)

    return eval(:(solvedSTD(prob = $(prb), $msr)))
end

"""
    solvedSTD(;prob::Vector, kwargs...)

An state-transition diagram constructor with given state probabilities `prob`
and any number of other arguments `kwargs`.

Sets `solved` of the STDInfo to true.

# Example
```julia-repl
julia> stdᵍᵉⁿ = solvedSTD(prob  = [0.1,0.2,0.7],
                          power = [0.0u"MW",0.0u"MW",2.0u"MW"])
```
"""
function solvedSTD(;prob::Vector, kwargs...)
    isapprox(1.0, sum(prob), rtol=1e-6) || return false

    std = STD(length(prob))
    set_info!(std,:solved,true)
    set_prop!(std,:msr,collect(intersect(MsrSet,keys(kwargs)))[1])
    set_prop!(std,states(std),:prob,prob)
    for ns in states(std) set_props!(std, ns, reduce(kwargs,ns)) end

    return std
end

################################################################################
# WARNING:  The empty constructor needs to be last in order to overwrite the   #
#           empty constructor created by other contructors, see: discourse -   #
#           keyword argument contructor breaks incomplete constructor.         #                                               #
################################################################################
"""
    STD()

An empty state-transition diagram constructor.

# Example
```julia-repl
julia> stdᵍᵉⁿ = STD()
```
"""
function STD()
    graph = _LG.DiGraph()

    props = PropDict(:info => STDInfo())
    sprops = Dict{Int,PropDict}()
    tprops = Dict{_LG.Edge{Int},PropDict}()

    return STD(graph, props, sprops, tprops)
end

# functions
is_directed(::Type{STD}) = true
is_directed(::Type{STD{I}}) where I = true
is_directed(std::STD) = true

props(std::AbstractSTD) = std.props
props(std::AbstractSTD, s::Int) = get(std.sprops, s, PropDict())
props(std::AbstractSTD, t::_LG.Edge) = get(std.tprops, t, PropDict())

get_prop(std::AbstractSTD, prop::Symbol) =
    haskey(props(std), prop) ? props(std)[prop] : ~ ;
has_prop(std::AbstractSTD, prop::Symbol) = haskey(std.props, prop)
set_prop!(std::AbstractSTD, prop::Symbol, value) =
    set_props!(std, Dict(prop => value))
set_props!(std::AbstractSTD, dict::Dict) = merge!(std.props, dict)

## Info
# structs
mutable struct STDInfo{B<:Bool} <: AbstractInfo
    solved::B
    renewal::B
    markovian::B
    time_homogeneous::B

    # constructor
    STDInfo() = new{Bool}(false,true,true,true)
end
mutable struct StateInfo{B<:Bool} <: AbstractInfo
    renewal::B
    trapping::B

    # constructor
    StateInfo() = new{Bool}(true,false)
end
mutable struct TransInfo{B<:Bool} <: AbstractInfo
    renewal::B
    markovian::B
    time_homogeneous::B

    # constructor
    TransInfo() = new{Bool}(true,true,true)
end

# functions
get_info(std::AbstractSTD, info::Symbol) = getproperty(std.props[:info],info)
set_info!(std::AbstractSTD, info::Symbol, value::Bool) =
    setproperty!(std.props[:info],info,value)
get_info(std::AbstractSTD, ns::Int, info::Symbol) =
    getproperty(std.sprops[ns][:info],info)
set_info!(std::AbstractSTD, ns::Int, info::Symbol, value::Bool) =
    setproperty!(std.sprops[ns][:info],info,value)
get_info(std::AbstractSTD, nt::_LG.Edge, info::Symbol) =
    getproperty(std.tprops[nt][:info],info)
set_info!(std::AbstractSTD, nt::_LG.Edge, info::Symbol, value::Bool) =
    setproperty!(std.tprops[nt][:info],info,value)

## State
# functions
ns(std::AbstractSTD) = _LG.nv(std.graph)
states(std::AbstractSTD) = _LG.vertices(std.graph)
add_vertex!(std::AbstractSTD) = _LG.add_vertex!(std.graph)
has_vertex(std::AbstractSTD, x...) = _LG.has_vertex(std.graph, x...)

get_sprop(std::AbstractSTD, prop::Symbol) =
    [get_prop(std, ns, prop) for ns in states(std)]
get_prop(std::AbstractSTD, ns::Int, prop::Symbol) = props(std, ns)[prop]
has_prop(std::AbstractSTD, ns::Int, prop::Symbol) = haskey(props(std,ns), prop)
set_prop!(std::AbstractSTD, ns::Int, prop::Symbol, value::Any) =
    set_props!(std,ns,Dict{Symbol,Any}(prop => value))
set_prop!(std::AbstractSTD, states::Base.OneTo{Int}, prop::Symbol, value::Any) =
    for ns in states set_props!(std,ns,Dict{Symbol,Any}(prop => value[ns])) end
set_props!(std::AbstractSTD, ns::Int, prop_dict::Dict) =
    haskey(std.sprops,ns) ? merge!(std.sprops[ns],prop_dict) :
                            std.sprops[ns] = prop_dict ;

"""
    add_state!(std::MultiStateSystems.AbstractSTD; kwargs...)

Adds a single state to the state-transition diagram `std` and fills its
corresponding `PropDict` with the named arguments `kwargs`.

# Example
```julia-repl
julia> stdᵍᵉⁿ = STD()
julia> add_state!(stdᵍᵉⁿ, name  = "normal operation state",
                          power = 100u"MW",
                          init  = 1.0)
```
"""
function add_state!(std::AbstractSTD; kwargs...)
    test(kwargs) || return false
    add_vertex!(std) || return false
    set_prop!(std, ns(std), :info, StateInfo())
    set_props!(std, ns(std), Dict(kwargs...))
    return true
end
function add_state!(std::AbstractSTD, prop_dict::Dict)
    add_vertex!(std) || return false
    set_prop!(std, ns(std), :info, StateInfo())                                 # TODO auto capture info prop
    set_props!(std, ns(std), prop_dict)
    return true
end

"""
    add_states!(std::MultiStateSystems.AbstractSTD; kwargs...)

Adds multiple states to the state-transition diagram `std` and fills their
corresponding `PropDict` with the named arguments `kwargs`. Either an uniform
argument is given which holds for all states or an array is given with the
specific argument for each state.

# Example
```julia-repl
julia> stdᵍᵉⁿ = STD()
julia> add_states!(stdᵍᵉⁿ, name  = ["normal operation state","failed state"],
                           power = [100.0u"MW",0.0u"MW"],
                           init  = [1.0,0.0],
                           markovian = true)
```
"""
function add_states!(std::AbstractSTD; kwargs...)
    test(kwargs) || return false
    if has_msr(kwargs) set_prop!(std, :msr, get_msr(kwargs)) end                        # TODO auto capture info prop
    for ni in indices_of(kwargs) add_state!(std,reduce(kwargs,ni)) end
    return true
end

## Transition
# functions
nt(std::AbstractSTD) = _LG.ne(std.graph)
transitions(std::AbstractSTD) = _LG.edges(std.graph)
has_edge(std::AbstractSTD, x...) = _LG.has_edge(std.graph, x...)
add_edge!(std::AbstractSTD, x...) = _LG.add_edge!(std.graph, x...)

get_tprop(std::AbstractSTD, prop::Symbol) =
    Dict(nt => get_prop(std,nt,prop) for nt in transitions(std))
get_prop(std::AbstractSTD, nt::_LG.Edge, prop::Symbol) = props(std,nt)[prop]
has_prop(std::AbstractSTD, nt::_LG.Edge, prop::Symbol) =
    haskey(props(std,nt), prop)
set_prop!(std::AbstractSTD, nt::_LG.Edge, prop::Symbol, value::Any) =
    set_props!(std,nt,Dict{Symbol,Any}(prop => value))
set_props!(std::AbstractSTD, nt::_LG.Edge, prop_dict::Dict) =
    haskey(std.tprops,nt) ? merge!(std.tprops[nt],prop_dict) :
                            std.tprops[nt] = prop_dict ;

"""
    add_transition!(std::MultiStateSystems.AbstractSTD; kwargs...)

Adds a single transitions to the state-transition diagram `std` and fills its
corresponding `PropDict` with the named arguments `kwargs`. One obligatory named
argument is `:states`, describing the tuple (fr,to) of the from- and to-state.

# Example
```julia-repl
julia> stdᵍᵉⁿ = STD()
julia> add_states!(stdᵍᵉⁿ, name  = ["normal operation state","failed state"],
                           power = [100.0u"MW",0.0u"MW"],
                           init  = [1.0,0.0],
                           markovian = true)
julia> add_transition!(stdᵍᵉⁿ, rate = 0.001u"1/hr",
                               states = (1,2))
```
"""
function add_transition!(std::AbstractSTD; kwargs...)
    test(kwargs) || return false
    haskey(kwargs,:states) || return false
    edge = _LG.Edge(kwargs[:states])
    add_edge!(std, edge) || return false
    set_prop!(std, edge, :info, TransInfo())                                    # TODO auto capture info prop
    set_props!(std, edge, Dict(kwargs...))
    return true
end
function add_transition!(std::AbstractSTD, crd::Tuple{Int,Int}, prop_dict::Dict)
    edge = _LG.Edge(crd)
    add_edge!(std, edge) || return false
    set_prop!(std, edge, :info, TransInfo())                                    # TODO auto capture info prop
    set_props!(std, edge, prop_dict)
    # update_info!(std, edge)
    return true
end
"""
    add_transitions!(std::MultiStateSystems.AbstractSTD; kwargs...)

Adds multiple transitions to the state-transition diagram `std` and fills their
corresponding `PropDict` with the named arguments `kwargs`. Either an uniform
argument is given which holds for all transitions or an array is given with the
specific argument for each transition.

# Example
```julia-repl
julia> stdᵍᵉⁿ = STD()
julia> add_states!(stdᵍᵉⁿ, name  = ["normal operation state","failed state"],
                           power = [100.0u"MW",0.0u"MW"],
                           init  = [1.0,0.0],
                           markovian = true)
julia> add_transitions!(stdᵍᵉⁿ, rate = [0.001u"1/hr",0.01u"1/hr"],
                                states = [(1,2),(2,1)])
```
!!! note
    If the `:states` argument is not provided in the `add_transitions!`
    function, the from- and to-states will be determined based on the other
    arguments.
# Example (Alternative)
```julia-repl
julia> add_transitions!(stdᵍᵉⁿ, rate = [0.000u"1/hr" 0.010u"1/hr"
                                        0.001u"1/hr" 0.000u"1/hr"])
```
"""
function add_transitions!(std::AbstractSTD; kwargs...)
    test(kwargs) || return false
    for ni in indices_of(kwargs)
        crd = haskey(kwargs,:states) ? kwargs[:states][ni] : (ni[1],ni[2]) ;
        add_transition!(std,crd,reduce(kwargs, ni, excl=[:states]))             # TODO auto capture info prop
    end
    return true
end


text:
LG.ne(g::VStaticGraph) = g.ne

LG.nv(::VStaticGraph{T,N}) where {T,N} = N

LG.vertices(::VStaticGraph{T,N}) where {T,N} = Base.OneTo(N)

LG.is_directed(::Type{<:VStaticGraph{T,N,D}}) where {T,N,D} = D

LG.edgetype(::VStaticGraph{T}) where {T} = LG.SimpleEdge{T}

Base.eltype(::VStaticGraph{T}) where {T} = T

function LG.has_edge(g::VStaticGraph, e::LG.AbstractEdge)
    LG.has_edge(g, LG.src(e), LG.dst(e))
end

function LG.has_edge(g::VStaticGraph{T,N,false}, s, d) where {T,N}
    verts = LG.vertices(g)
    (s in verts && d in verts) || return false # edge out of bounds
    @inbounds list_s = g.fadjlist[s]
    @inbounds list_d = g.fadjlist[d]
    if length(list_s) > length(list_d)
        d = s
        list_s = list_d
    end
    return LG.insorted(d, list_s)
end

function LG.has_edge(g::VStaticGraph{T,N,true}, s, d) where {T,N}
    verts = LG.vertices(g)
    (s in verts && d in verts) || return false  # edge out of bounds
    @inbounds list = g.fadjlist[s]
    return LG.insorted(d, list)
end

function LG.outneighbors(g::VStaticGraph{T,N}, v::Integer) where {T,N}
    @boundscheck v in LG.vertices(g) || return T[]
    flist = fadj(g)
    @inbounds list = flist[v]
    return list
end

function LG.inneighbors(g::VStaticGraph{T,N}, v::Integer) where {T,N}
    @boundscheck v in LG.vertices(g) || return T[]
    blist = badj(g)
    @inbounds list = blist[v]
    return list
end

function Base.zero(::Type{VStaticGraph{T,N,D}}) where {T,N,D}
    return VStaticGraph{T,0,D}()
end


text:
import Pluto
import Pluto: PlutoRunner, Notebook, WorkspaceManager, Cell, ServerSession, ClientSession, update_run!

🍭 = ServerSession()
🍭.options.evaluation.workspace_use_distributed = false

fakeclient = ClientSession(:fake, nothing)
🍭.connected_clients[fakeclient.id] = fakeclient

@testset "Use ref" begin
    @testset "Implicit & explicit runs" begin
        notebook = Notebook(Cell.([
            "using PlutoHooks",
            "x = 1",
            """
            begin
                x;
                ref = @use_ref(1)

                ref[] += 1
            end
            """,
        ]))
        cell(idx) = notebook.cells[idx]

        update_run!(🍭, notebook, notebook.cells)

        @test cell(1) |> noerror
        @test cell(2) |> noerror
        @test cell(3) |> noerror
        @test cell(3).output.body == "2"

        update_run!(🍭, notebook, cell(2))

        @test cell(3).output.body == "3"

        for _ in 1:3
            update_run!(🍭, notebook, cell(2))
        end

        @test cell(3).output.body == "6"

        update_run!(🍭, notebook, cell(3))

        @test cell(3).output.body == "2"
    end
end

@testset "Use Effect" begin
    @testset "Implicit runs with dependencies" begin
        notebook = Notebook(Cell.([
            "using PlutoHooks",
            "x = 1",
            "y = 1",
            """
            begin
                y
                ref = @use_ref(1)
                @use_effect([x]) do
                    ref[] += 1
                end
                ref[]
            end
            """,
        ]))
        cell(idx) = notebook.cells[idx]
        update_run!(🍭, notebook, notebook.cells)

        @test cell(4) |> noerror
        @test cell(4).output.body == "2"

        update_run!(🍭, notebook, cell(3))
        @test cell(4).output.body == "2"

        update_run!(🍭, notebook, cell(2)) # Not changing the value of x
        @test cell(4).output.body == "2"

        setcode(cell(2), "x = 2")
        update_run!(🍭, notebook, cell(2)) # Changing the value of x
        @test cell(4).output.body == "3"
    end

    @testset "Cleanups" begin
        notebook = Notebook(Cell.([
            "using PlutoHooks",
            "cleanup_ref = @use_ref(1)",
            "ref = @use_ref(1)",
            "x = 1",
            """
            begin
                @use_effect([x]) do
                    ref[] += 1
                    () -> (cleanup_ref[] += 1)
                end
            end
            """,
            "cleanup_ref[]",
        ]))
        cell(idx) = notebook.cells[idx]
        update_run!(🍭, notebook, notebook.cells)

        @test all(noerror, notebook.cells)
        @test cell(6).output.body == "1"

        update_run!(🍭, notebook, [cell(4), cell(6)])
        @test cell(6).output.body == "1"

        setcode(cell(4), "x = 2")
        update_run!(🍭, notebook, [cell(4), cell(6)])
        @test cell(6).output.body == "2"

        update_run!(🍭, notebook, [cell(5), cell(6)])
        @test cell(6).output.body == "3"
    end
end

@testset "Use state" begin
    @testset "Trigger reactive run" begin
        # Use state tests are distributed because the self run relaying is not closed for non-distributed notebooks
        🍭.options.evaluation.workspace_use_distributed = true

        notebook = Notebook(Cell.([
            "using PlutoHooks",
            "state, setstate = @use_state(1)",
            "trigger = false",
            """
            if trigger
                setstate(10)
            end
            """,
            with_test_env(),
            "state",
        ]))
        cell(idx) = notebook.cells[idx]

        update_run!(🍭, notebook, notebook.cells)

        @test all(noerror, notebook.cells)
        @test notebook.cells[end].output.body == "1"

        setcode(cell(3), "trigger = true")
        update_run!(🍭, notebook, cell(3))

        sleep(.3) # Reactive run is async

        @test notebook.cells[end].output.body == "10"

        setcode(cell(3), "trigger = false")
        update_run!(🍭, notebook, cell(3))
        update_run!(🍭, notebook, cell(2))

        @test notebook.cells[end].output.body == "1"

        WorkspaceManager.unmake_workspace((🍭, notebook))
        🍭.options.evaluation.workspace_use_distributed = false
    end

    @testset "use state with ref" begin
        🍭.options.evaluation.workspace_use_distributed = true
        notebook = Notebook(Cell.([
            "using PlutoHooks",
            """
            begin
                state, setstate = @use_state(1)
                ref = @use_ref(1)
            end
            """,
            "ref[] += 1",
            "state",
            "setstate",
            with_test_env(),
        ]))
        cell(idx) = notebook.cells[idx]

        update_run!(🍭, notebook, notebook.cells)
        @test all(noerror, notebook.cells)

        update_run!(🍭, notebook, cell(3))
        update_run!(🍭, notebook, cell(3))
        update_run!(🍭, notebook, cell(3))

        @test cell(3).output.body == "5"

        setcode(cell(5), """
        if state == 1
            setstate(2)
        end
        """)
        update_run!(🍭, notebook, cell(5))

        sleep(2.)

        @test cell(3).output.body == "6"

        WorkspaceManager.unmake_workspace((🍭, notebook))
        🍭.options.evaluation.workspace_use_distributed = false
    end
end

@testset "Use deps" begin
    notebook = Notebook(Cell.([
        "using PlutoHooks",
        "x = 1",
        """
        @use_deps([x]) do
            ref = @use_ref(1)

            ref[] += 1
        end
        """,
    ]))
    cell(idx) = notebook.cells[idx]
    update_run!(🍭, notebook, notebook.cells)

    @test all(noerror, notebook.cells)
    @test cell(3).output.body == "2"

    update_run!(🍭, notebook, cell(2))
    @test cell(3).output.body == "3"

    setcode(cell(2), "x = 2")
    update_run!(🍭, notebook, cell(2))
    @test cell(3).output.body == "2"
end


text:
export PointCloud, npoints

"""
    PointCloud

Initialize PointCloud representation.

`points` should be Array of size `(D, N, B)` where `N` is the number of points, `D` is
dimensionality of each points (i.e. `D`=2 or `D`=3) and `B` is the batch size of PointCloud.
`normals` is optional field, if given should be Array of size `(D, N, B)` where `N` and `B`
should match with the `N` and `B` of `points` and `D`=2 or `D`=3
(i.e. normals for 2D and 3D PointCloud respectively).

### Fields:

- `points`      - Points that makes up whole PointCloud.
- `normals`     - Normals of each points in PointCloud.

### Available Contructor:

- `PointCloud(points, normals=nothing)`
- `PointCloud(;points, normals=nothing)`
- `PointCloud(pcloud::PointCloud)`
"""
mutable struct PointCloud{T<:Float32} <: AbstractObject
    points::AbstractArray{T,3}
    normals::Union{AbstractArray{T,3},Nothing}
end

function PointCloud(
    points::AbstractArray{Float32,2},
    normals::Union{AbstractArray{Float32,2},Nothing} = nothing,
)
    points = reshape(points, size(points)..., 1)

    if !(normals isa Nothing)
        size(points, 2) == size(normals, 2) ||
            error("number of points and normals must match in PointCloud.")
        normals = reshape(normals, size(normals)..., 1)
    end

    return PointCloud(points, normals)
end

function PointCloud(points::AbstractArray, normals::Union{AbstractArray,Nothing} = nothing)
    points = Float32.(points)
    if normals !== nothing
        normals = Float32.(normals)
    end
    return PointCloud(points, normals)
end

PointCloud(; points, normals = nothing) = PointCloud(points, normals)

PointCloud(pcloud::PointCloud) = PointCloud(pcloud.points, pcloud.normals)

@functor PointCloud

# deepcopy generate error when using on PointCloud with parent field of points not Nothing
Base.deepcopy_internal(x::PointCloud, dict::IdDict) =
    PointCloud(copy(x.points), (x.normals === nothing ? nothing : copy(x.normals)))

Base.getindex(p::PointCloud, index::Number) = p.points[:, :, index]

function Base.show(io::IO, m::PointCloud{T}) where {T}
    print(
        io,
        "PointCloud{$(T)} Structure:\n    Batch size: ",
        size(m.points, 3),
        "\n    Points: ",
        size(m.points, 2),
        "\n    Normals ",
        (m.normals === nothing ? 0 : size(m.normals, 2)),
        "\n    Storage type: ",
        typeof(m.points),
    )
end

"""
    npoints(p::PointCloud)

Returns the size of PointCloud.
"""
npoints(p::PointCloud) = size(p.points, 2)


text:
using Test
using SafeTestsets

@safetestset "ExactDiagonalization" begin
    include("ExactDiagonalization.jl")
end


text:
import QuadGK: quadgk

### NIntegrate

@mkapprule NIntegrate

@sjdoc NIntegrate """
    NIntegrate( expr, [x,x0,xf])

Integrate the Symata expression `expr` numerically  between `x0` and `xf`.

    NIntegrate( expr , [x,x0,x1,...,xf])

Specify singular points between the limitx `x0` and `xf`.

    NIntegrate( f, [x0,xf])
    NIntegrate( f , [x0,x1,...,xf])

Integrate the compiled function `f` numerically.

NIntegrate returns `[result, err]`.

!!! note
    Giving an uncompiled expression is slower than giving a compiled function. But, for
    many purposes, the difference in efficiency is not important.
    `f = Compile(expr)` compiles `expr` to the function `f`.
"""

quadgklist(f,args) = mxprcf(:List, quadgk(f, map( x -> float(doeval(x)), args)...)...)

@doap function NIntegrate(expr, range::Mxpr{:List})
    r = margs(range)
    (sym,x0,x1) = length(r) == 3 ? (r...,) : length(r) == 2 ? (:x,r...,) : symerror(range, " is not a valid integration ranges")
    f = doeval(expr)
    isa(f,Function) && return quadgklist(f,(x0,x1))
    quadgklist(wrap_symata(expr,sym), (x0,x1))
end


text:
# This file is a part of Julia. License is MIT: https://julialang.org/license

module Sort

import ..@__MODULE__, ..parentmodule
const Base = parentmodule(@__MODULE__)
using .Base.Order
using .Base: copymutable, LinearIndices, length, (:), iterate,
    eachindex, axes, first, last, similar, zip, OrdinalRange,
    AbstractVector, @inbounds, AbstractRange, @eval, @inline, Vector, @noinline,
    AbstractMatrix, AbstractUnitRange, isless, identity, eltype, >, <, <=, >=, |, +, -, *, !,
    extrema, sub_with_overflow, add_with_overflow, oneunit, div, getindex, setindex!,
    length, resize!, fill, Missing, require_one_based_indexing, keytype, UnitRange,
    min, max, reinterpret, signed, unsigned, Signed, Unsigned, typemin, xor, Type, BitSigned

using .Base: >>>, !==

import .Base:
    sort,
    sort!,
    issorted,
    sortperm,
    to_indices

export # also exported by Base
    # order-only:
    issorted,
    searchsorted,
    searchsortedfirst,
    searchsortedlast,
    insorted,
    # order & algorithm:
    sort,
    sort!,
    sortperm,
    sortperm!,
    partialsort,
    partialsort!,
    partialsortperm,
    partialsortperm!,
    # algorithms:
    InsertionSort,
    QuickSort,
    MergeSort,
    PartialQuickSort

export # not exported by Base
    Algorithm,
    DEFAULT_UNSTABLE,
    DEFAULT_STABLE,
    SMALL_ALGORITHM,
    SMALL_THRESHOLD

## functions requiring only ordering ##

function issorted(itr, order::Ordering)
    y = iterate(itr)
    y === nothing && return true
    prev, state = y
    y = iterate(itr, state)
    while y !== nothing
        this, state = y
        lt(order, this, prev) && return false
        prev = this
        y = iterate(itr, state)
    end
    return true
end

"""
    issorted(v, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Test whether a vector is in sorted order. The `lt`, `by` and `rev` keywords modify what
order is considered to be sorted just as they do for [`sort`](@ref).

# Examples
```jldoctest
julia> issorted([1, 2, 3])
true

julia> issorted([(1, "b"), (2, "a")], by = x -> x[1])
true

julia> issorted([(1, "b"), (2, "a")], by = x -> x[2])
false

julia> issorted([(1, "b"), (2, "a")], by = x -> x[2], rev=true)
true
```
"""
issorted(itr;
    lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) =
    issorted(itr, ord(lt,by,rev,order))

function partialsort!(v::AbstractVector, k::Union{Integer,OrdinalRange}, o::Ordering)
    inds = axes(v, 1)
    sort!(v, first(inds), last(inds), PartialQuickSort(k), o)
    maybeview(v, k)
end

maybeview(v, k) = view(v, k)
maybeview(v, k::Integer) = v[k]

"""
    partialsort!(v, k; by=<transform>, lt=<comparison>, rev=false)

Partially sort the vector `v` in place, according to the order specified by `by`, `lt` and
`rev` so that the value at index `k` (or range of adjacent values if `k` is a range) occurs
at the position where it would appear if the array were fully sorted via a non-stable
algorithm. If `k` is a single index, that value is returned; if `k` is a range, an array of
values at those indices is returned. Note that `partialsort!` does not fully sort the input
array.

# Examples
```jldoctest
julia> a = [1, 2, 4, 3, 4]
5-element Vector{Int64}:
 1
 2
 4
 3
 4

julia> partialsort!(a, 4)
4

julia> a
5-element Vector{Int64}:
 1
 2
 3
 4
 4

julia> a = [1, 2, 4, 3, 4]
5-element Vector{Int64}:
 1
 2
 4
 3
 4

julia> partialsort!(a, 4, rev=true)
2

julia> a
5-element Vector{Int64}:
 4
 4
 3
 2
 1
```
"""
partialsort!(v::AbstractVector, k::Union{Integer,OrdinalRange};
             lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) =
    partialsort!(v, k, ord(lt,by,rev,order))

"""
    partialsort(v, k, by=<transform>, lt=<comparison>, rev=false)

Variant of [`partialsort!`](@ref) which copies `v` before partially sorting it, thereby returning the
same thing as `partialsort!` but leaving `v` unmodified.
"""
partialsort(v::AbstractVector, k::Union{Integer,OrdinalRange}; kws...) =
    partialsort!(copymutable(v), k; kws...)

# This implementation of `midpoint` is performance-optimized but safe
# only if `lo <= hi`.
midpoint(lo::T, hi::T) where T<:Integer = lo + ((hi - lo) >>> 0x01)
midpoint(lo::Integer, hi::Integer) = midpoint(promote(lo, hi)...)

# reference on sorted binary search:
#   http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary

# index of the first value of vector a that is greater than or equal to x;
# returns length(v)+1 if x is greater than all values in v.
function searchsortedfirst(v::AbstractVector, x, lo::T, hi::T, o::Ordering)::keytype(v) where T<:Integer
    u = T(1)
    lo = lo - u
    hi = hi + u
    @inbounds while lo < hi - u
        m = midpoint(lo, hi)
        if lt(o, v[m], x)
            lo = m
        else
            hi = m
        end
    end
    return hi
end

# index of the last value of vector a that is less than or equal to x;
# returns 0 if x is less than all values of v.
function searchsortedlast(v::AbstractVector, x, lo::T, hi::T, o::Ordering)::keytype(v) where T<:Integer
    u = T(1)
    lo = lo - u
    hi = hi + u
    @inbounds while lo < hi - u
        m = midpoint(lo, hi)
        if lt(o, x, v[m])
            hi = m
        else
            lo = m
        end
    end
    return lo
end

# returns the range of indices of v equal to x
# if v does not contain x, returns a 0-length range
# indicating the insertion point of x
function searchsorted(v::AbstractVector, x, ilo::T, ihi::T, o::Ordering)::UnitRange{keytype(v)} where T<:Integer
    u = T(1)
    lo = ilo - u
    hi = ihi + u
    @inbounds while lo < hi - u
        m = midpoint(lo, hi)
        if lt(o, v[m], x)
            lo = m
        elseif lt(o, x, v[m])
            hi = m
        else
            a = searchsortedfirst(v, x, max(lo,ilo), m, o)
            b = searchsortedlast(v, x, m, min(hi,ihi), o)
            return a : b
        end
    end
    return (lo + 1) : (hi - 1)
end

function searchsortedlast(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering)::keytype(a)
    require_one_based_indexing(a)
    f, h, l = first(a), step(a), last(a)
    if lt(o, x, f)
        0
    elseif h == 0 || !lt(o, x, l)
        length(a)
    else
        n = round(Integer, (x - f) / h + 1)
        lt(o, x, a[n]) ? n - 1 : n
    end
end

function searchsortedfirst(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering)::keytype(a)
    require_one_based_indexing(a)
    f, h, l = first(a), step(a), last(a)
    if !lt(o, f, x)
        1
    elseif h == 0 || lt(o, l, x)
        length(a) + 1
    else
        n = round(Integer, (x - f) / h + 1)
        lt(o, a[n], x) ? n + 1 : n
    end
end

function searchsortedlast(a::AbstractRange{<:Integer}, x::Real, o::DirectOrdering)::keytype(a)
    require_one_based_indexing(a)
    f, h, l = first(a), step(a), last(a)
    if lt(o, x, f)
        0
    elseif h == 0 || !lt(o, x, l)
        length(a)
    else
        if o isa ForwardOrdering
            fld(floor(Integer, x) - f, h) + 1
        else
            fld(ceil(Integer, x) - f, h) + 1
        end
    end
end

function searchsortedfirst(a::AbstractRange{<:Integer}, x::Real, o::DirectOrdering)::keytype(a)
    require_one_based_indexing(a)
    f, h, l = first(a), step(a), last(a)
    if !lt(o, f, x)
        1
    elseif h == 0 || lt(o, l, x)
        length(a) + 1
    else
        if o isa ForwardOrdering
            cld(ceil(Integer, x) - f, h) + 1
        else
            cld(floor(Integer, x) - f, h) + 1
        end
    end
end

searchsorted(a::AbstractRange{<:Real}, x::Real, o::DirectOrdering) =
    searchsortedfirst(a, x, o) : searchsortedlast(a, x, o)

for s in [:searchsortedfirst, :searchsortedlast, :searchsorted]
    @eval begin
        $s(v::AbstractVector, x, o::Ordering) = (inds = axes(v, 1); $s(v,x,first(inds),last(inds),o))
        $s(v::AbstractVector, x;
           lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward) =
            $s(v,x,ord(lt,by,rev,order))
    end
end

"""
    searchsorted(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the range of indices of `a` which compare as equal to `x` (using binary search)
according to the order specified by the `by`, `lt` and `rev` keywords, assuming that `a`
is already sorted in that order. Return an empty range located at the insertion point
if `a` does not contain values equal to `x`.

See also: [`insorted`](@ref), [`searchsortedfirst`](@ref), [`sort`](@ref), [`findall`](@ref).

# Examples
```jldoctest
julia> searchsorted([1, 2, 4, 5, 5, 7], 4) # single match
3:3

julia> searchsorted([1, 2, 4, 5, 5, 7], 5) # multiple matches
4:5

julia> searchsorted([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3:2

julia> searchsorted([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7:6

julia> searchsorted([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1:0
```
""" searchsorted

"""
    searchsortedfirst(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the index of the first value in `a` greater than or equal to `x`, according to the
specified order. Return `lastindex(a) + 1` if `x` is greater than all values in `a`.
`a` is assumed to be sorted.

See also: [`searchsortedlast`](@ref), [`searchsorted`](@ref), [`findfirst`](@ref).

# Examples
```jldoctest
julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 4) # single match
3

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 5) # multiple matches
4

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
3

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
7

julia> searchsortedfirst([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
1
```
""" searchsortedfirst

"""
    searchsortedlast(a, x; by=<transform>, lt=<comparison>, rev=false)

Return the index of the last value in `a` less than or equal to `x`, according to the
specified order. Return `firstindex(a) - 1` if `x` is less than all values in `a`. `a` is
assumed to be sorted.

# Examples
```jldoctest
julia> searchsortedlast([1, 2, 4, 5, 5, 7], 4) # single match
3

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 5) # multiple matches
5

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 3) # no match, insert in the middle
2

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 9) # no match, insert at end
6

julia> searchsortedlast([1, 2, 4, 5, 5, 7], 0) # no match, insert at start
0
```
""" searchsortedlast

"""
    insorted(a, x; by=<transform>, lt=<comparison>, rev=false) -> Bool

Determine whether an item is in the given sorted collection, in the sense that
it is [`==`](@ref) to one of the values of the collection according to the order
specified by the `by`, `lt` and `rev` keywords, assuming that `a` is already
sorted in that order, see [`sort`](@ref) for the keywords.

See also [`in`](@ref).

# Examples
```jldoctest
julia> insorted(4, [1, 2, 4, 5, 5, 7]) # single match
true

julia> insorted(5, [1, 2, 4, 5, 5, 7]) # multiple matches
true

julia> insorted(3, [1, 2, 4, 5, 5, 7]) # no match
false

julia> insorted(9, [1, 2, 4, 5, 5, 7]) # no match
false

julia> insorted(0, [1, 2, 4, 5, 5, 7]) # no match
false
```

!!! compat "Julia 1.6"
     `insorted` was added in Julia 1.6.
"""
function insorted end
insorted(x, v::AbstractVector; kw...) = !isempty(searchsorted(v, x; kw...))
insorted(x, r::AbstractRange) = in(x, r)

## sorting algorithms ##

abstract type Algorithm end

struct InsertionSortAlg <: Algorithm end
struct QuickSortAlg     <: Algorithm end
struct MergeSortAlg     <: Algorithm end

"""
    AdaptiveSort(fallback)

Indicate that a sorting function should use the fastest available algorithm.

Adaptive sort will use the algorithm specified by `fallback` for types and orders that are
not [`UIntMappable`](@ref). Otherwise, it will typically use:
  * Insertion sort for short vectors
  * Radix sort for long vectors
  * Counting sort for vectors of integers spanning a short range

Adaptive sort is guaranteed to be stable if the fallback algorithm is stable.
"""
struct AdaptiveSort{Fallback <: Algorithm} <: Algorithm
    fallback::Fallback
end
"""
    PartialQuickSort{T <: Union{Integer,OrdinalRange}}

Indicate that a sorting function should use the partial quick sort
algorithm. Partial quick sort returns the smallest `k` elements sorted from smallest
to largest, finding them and sorting them using [`QuickSort`](@ref).

Characteristics:
  * *not stable*: does not preserve the ordering of elements which
    compare equal (e.g. "a" and "A" in a sort of letters which
    ignores case).
  * *in-place* in memory.
  * *divide-and-conquer*: sort strategy similar to [`MergeSort`](@ref).
"""
struct PartialQuickSort{T <: Union{Integer,OrdinalRange}} <: Algorithm
    k::T
end

"""
    InsertionSort

Indicate that a sorting function should use the insertion sort
algorithm. Insertion sort traverses the collection one element
at a time, inserting each element into its correct, sorted position in
the output vector.

Characteristics:
  * *stable*: preserves the ordering of elements which
    compare equal (e.g. "a" and "A" in a sort of letters
    which ignores case).
  * *in-place* in memory.
  * *quadratic performance* in the number of elements to be sorted:
    it is well-suited to small collections but should not be used for large ones.
"""
const InsertionSort = InsertionSortAlg()
"""
    QuickSort

Indicate that a sorting function should use the quick sort
algorithm, which is *not* stable.

Characteristics:
  * *not stable*: does not preserve the ordering of elements which
    compare equal (e.g. "a" and "A" in a sort of letters which
    ignores case).
  * *in-place* in memory.
  * *divide-and-conquer*: sort strategy similar to [`MergeSort`](@ref).
  * *good performance* for large collections.
"""
const QuickSort     = QuickSortAlg()
"""
    MergeSort

Indicate that a sorting function should use the merge sort
algorithm. Merge sort divides the collection into
subcollections and repeatedly merges them, sorting each
subcollection at each step, until the entire
collection has been recombined in sorted form.

Characteristics:
  * *stable*: preserves the ordering of elements which compare
    equal (e.g. "a" and "A" in a sort of letters which ignores
    case).
  * *not in-place* in memory.
  * *divide-and-conquer* sort strategy.
"""
const MergeSort     = MergeSortAlg()

const DEFAULT_UNSTABLE = AdaptiveSort(QuickSort)
const DEFAULT_STABLE   = AdaptiveSort(MergeSort)
const SMALL_ALGORITHM  = InsertionSort
const SMALL_THRESHOLD  = 20

function sort!(v::AbstractVector, lo::Integer, hi::Integer, ::InsertionSortAlg, o::Ordering)
    @inbounds for i = lo+1:hi
        j = i
        x = v[i]
        while j > lo && lt(o, x, v[j-1])
            v[j] = v[j-1]
            j -= 1
        end
        v[j] = x
    end
    return v
end

# selectpivot!
#
# Given 3 locations in an array (lo, mi, and hi), sort v[lo], v[mi], v[hi]) and
# choose the middle value as a pivot
#
# Upon return, the pivot is in v[lo], and v[hi] is guaranteed to be
# greater than the pivot

@inline function selectpivot!(v::AbstractVector, lo::Integer, hi::Integer, o::Ordering)
    @inbounds begin
        mi = midpoint(lo, hi)

        # sort v[mi] <= v[lo] <= v[hi] such that the pivot is immediately in place
        if lt(o, v[lo], v[mi])
            v[mi], v[lo] = v[lo], v[mi]
        end

        if lt(o, v[hi], v[lo])
            if lt(o, v[hi], v[mi])
                v[hi], v[lo], v[mi] = v[lo], v[mi], v[hi]
            else
                v[hi], v[lo] = v[lo], v[hi]
            end
        end

        # return the pivot
        return v[lo]
    end
end

# partition!
#
# select a pivot, and partition v according to the pivot

function partition!(v::AbstractVector, lo::Integer, hi::Integer, o::Ordering)
    pivot = selectpivot!(v, lo, hi, o)
    # pivot == v[lo], v[hi] > pivot
    i, j = lo, hi
    @inbounds while true
        i += 1; j -= 1
        while lt(o, v[i], pivot); i += 1; end;
        while lt(o, pivot, v[j]); j -= 1; end;
        i >= j && break
        v[i], v[j] = v[j], v[i]
    end
    v[j], v[lo] = pivot, v[j]

    # v[j] == pivot
    # v[k] >= pivot for k > j
    # v[i] <= pivot for i < j
    return j
end

function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::QuickSortAlg, o::Ordering)
    @inbounds while lo < hi
        hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)
        j = partition!(v, lo, hi, o)
        if j-lo < hi-j
            # recurse on the smaller chunk
            # this is necessary to preserve O(log(n))
            # stack space in the worst case (rather than O(n))
            lo < (j-1) && sort!(v, lo, j-1, a, o)
            lo = j+1
        else
            j+1 < hi && sort!(v, j+1, hi, a, o)
            hi = j-1
        end
    end
    return v
end

function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::MergeSortAlg, o::Ordering, t=similar(v,0))
    @inbounds if lo < hi
        hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)

        m = midpoint(lo, hi)
        (length(t) < m-lo+1) && resize!(t, m-lo+1)

        sort!(v, lo,  m,  a, o, t)
        sort!(v, m+1, hi, a, o, t)

        i, j = 1, lo
        while j <= m
            t[i] = v[j]
            i += 1
            j += 1
        end

        i, k = 1, lo
        while k < j <= hi
            if lt(o, v[j], t[i])
                v[k] = v[j]
                j += 1
            else
                v[k] = t[i]
                i += 1
            end
            k += 1
        end
        while k < j
            v[k] = t[i]
            k += 1
            i += 1
        end
    end

    return v
end

function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::PartialQuickSort,
               o::Ordering)
    @inbounds while lo < hi
        hi-lo <= SMALL_THRESHOLD && return sort!(v, lo, hi, SMALL_ALGORITHM, o)
        j = partition!(v, lo, hi, o)

        if j <= first(a.k)
            lo = j+1
        elseif j >= last(a.k)
            hi = j-1
        else
            # recurse on the smaller chunk
            # this is necessary to preserve O(log(n))
            # stack space in the worst case (rather than O(n))
            if j-lo < hi-j
                lo < (j-1) && sort!(v, lo, j-1, a, o)
                lo = j+1
            else
                hi > (j+1) && sort!(v, j+1, hi, a, o)
                hi = j-1
            end
        end
    end
    return v
end

# This is a stable least significant bit first radix sort.
#
# That is, it first sorts the entire vector by the last chunk_size bits, then by the second
# to last chunk_size bits, and so on. Stability means that it will not reorder two elements
# that compare equal. This is essential so that the order introduced by earlier,
# less significant passes is preserved by later passes.
#
# Each pass divides the input into 2^chunk_size == mask+1 buckets. To do this, it
#  * counts the number of entries that fall into each bucket
#  * uses those counts to compute the indices to move elements of those buckets into
#  * moves elements into the computed indices in the swap array
#  * switches the swap and working array
#
# In the case of an odd number of passes, the returned vector will === the input vector t,
# not v. This is one of the many reasons radix_sort! is not exported.
function radix_sort!(v::AbstractVector{U}, lo::Integer, hi::Integer, bits::Unsigned,
                     t::AbstractVector{U}, chunk_size=radix_chunk_size_heuristic(lo, hi, bits)) where U <: Unsigned
    # bits is unsigned for performance reasons.
    mask = UInt(1) << chunk_size - 0x1
    counts = Vector{UInt}(undef, mask+2)

    @inbounds for shift in 0:chunk_size:bits-1

        # counts[2:mask+2] will store the number of elements that fall into each bucket.
        # if chunk_size = 8, counts[2] is bucket 0x00 and counts[257] is bucket 0xff.
        counts .= 0
        for k in lo:hi
            x = v[k]                  # lookup the element
            i = (x >> shift)&mask + 2 # compute its bucket's index for this pass
            counts[i] += 1            # increment that bucket's count
        end

        counts[1] = lo                # set target index for the first bucket
        cumsum!(counts, counts)       # set target indices for subsequent buckets
        # counts[1:mask+1] now stores indices where the first member of each bucket
        # belongs, not the number of elements in each bucket. We will put the first element
        # of bucket 0x00 in t[counts[1]], the next element of bucket 0x00 in t[counts[1]+1],
        # and the last element of bucket 0x00 in t[counts[2]-1].

        for k in lo:hi
            x = v[k]                  # lookup the element
            i = (x >> shift)&mask + 1 # compute its bucket's index for this pass
            j = counts[i]             # lookup the target index
            t[j] = x                  # put the element where it belongs
            counts[i] = j + 1         # increment the target index for the next
        end                           #  ↳ element in this bucket

        v, t = t, v # swap the now sorted destination vector t back into primary vector v

    end

    v
end
function radix_chunk_size_heuristic(lo::Integer, hi::Integer, bits::Unsigned)
    # chunk_size is the number of bits to radix over at once.
    # We need to allocate an array of size 2^chunk size, and on the other hand the higher
    # the chunk size the fewer passes we need. Theoretically, chunk size should be based on
    # the Lambert W function applied to length. Empirically, we use this heuristic:
    guess = min(10, log(maybe_unsigned(hi-lo))*3/4+3)
    # TODO the maximum chunk size should be based on archetecture cache size.

    # We need iterations * chunk size ≥ bits, and these cld's
    # make an effort to get iterations * chunk size ≈ bits
    UInt8(cld(bits, cld(bits, guess)))
end

# For AbstractVector{Bool}, counting sort is always best.
# This is an implementation of counting sort specialized for Bools.
function sort!(v::AbstractVector{<:Bool}, lo::Integer, hi::Integer, a::AdaptiveSort, o::Ordering)
    first = lt(o, false, true) ? false : lt(o, true, false) ? true : return v
    count = 0
    @inbounds for i in lo:hi
        if v[i] == first
            count += 1
        end
    end
    @inbounds v[lo:lo+count-1] .= first
    @inbounds v[lo+count:hi] .= !first
    v
end

maybe_unsigned(x::Integer) = x # this is necessary to avoid calling unsigned on BigInt
maybe_unsigned(x::BitSigned) = unsigned(x)
function _extrema(v::AbstractArray, lo::Integer, hi::Integer, o::Ordering)
    mn = mx = v[lo]
    @inbounds for i in (lo+1):hi
        vi = v[i]
        lt(o, vi, mn) && (mn = vi)
        lt(o, mx, vi) && (mx = vi)
    end
    mn, mx
end
function sort!(v::AbstractVector, lo::Integer, hi::Integer, a::AdaptiveSort, o::Ordering)
    # if the sorting task is not UIntMappable, then we can't radix sort or sort_int_range!
    # so we skip straight to the fallback algorithm which is comparison based.
    U = UIntMappable(eltype(v), o)
    U === nothing && return sort!(v, lo, hi, a.fallback, o)

    # to avoid introducing excessive detection costs for the trivial sorting problem
    # and to avoid overflow, we check for small inputs before any other runtime checks
    hi <= lo && return v
    lenm1 = maybe_unsigned(hi-lo) # adding 1 would risk overflow
    # only count sort on a short range can compete with insertion sort when lenm1 < 40
    # and the optimization is not worth the detection cost, so we use insertion sort.
    lenm1 < 40 && return sort!(v, lo, hi, SMALL_ALGORITHM, o)

    # For most arrays, a presorted check is cheap (overhead < 5%) and for most large
    # arrays it is essentially free (<1%). Insertion sort runs in a fast O(n) on presorted
    # input and this guarantees presorted input will always be efficiently handled
    issorted(view(v, lo:hi), o) && return v

    # For large arrays, a reverse-sorted check is essentially free (overhead < 1%)
    if lenm1 >= 500 && issorted(view(v, lo:hi), ReverseOrdering(o))
        reverse!(view(v, lo:hi))
        return v
    end

    # UInt128 does not support fast bit shifting so we never
    # dispatch to radix sort but we may still perform count sort
    if sizeof(U) > 8
        if eltype(v) <: Integer && o isa DirectOrdering
            v_min, v_max = _extrema(v, lo, hi, Forward)
            v_range = maybe_unsigned(v_max-v_min)
            v_range == 0 && return v # all same

            # we know lenm1 ≥ 40, so this will never underflow.
            # if lenm1 > 3.7e18 (59 exabytes), then this may incorrectly dispatch to fallback
            if v_range < 5lenm1-100 # count sort will outperform comparison sort if v's range is small
                return sort_int_range!(v, Int(v_range+1), v_min, o === Forward ? identity : reverse, lo, hi)
            end
        end
        return sort!(v, lo, hi, a.fallback, o)
    end

    v_min, v_max = _extrema(v, lo, hi, o)
    lt(o, v_min, v_max) || return v # all same
    if eltype(v) <: Integer && o isa DirectOrdering
        R = o === Reverse
        v_range = maybe_unsigned(R ? v_min-v_max : v_max-v_min)
        if v_range < div(lenm1, 2) # count sort will be superior if v's range is very small
            return sort_int_range!(v, Int(v_range+1), R ? v_max : v_min, R ? reverse : identity, lo, hi)
        end
    end

    u_min, u_max = uint_map(v_min, o), uint_map(v_max, o)
    u_range = maybe_unsigned(u_max-u_min)
    if u_range < div(lenm1, 2) # count sort will be superior if u's range is very small
        u = uint_map!(v, lo, hi, o)
        sort_int_range!(u, Int(u_range+1), u_min, identity, lo, hi)
        return uint_unmap!(v, u, lo, hi, o)
    end

    # if u's range is small, then once we subtract out v_min, we'll get a vector like
    # UInt16[0x001a, 0x0015, 0x0006, 0x001b, 0x0008, 0x000c, 0x0001, 0x000e, 0x001c, 0x0009]
    # where we only need to radix over the last few bits (5, in the example).
    bits = unsigned(8sizeof(u_range) - leading_zeros(u_range))

    # radix sort runs in O(bits * lenm1), insertion sort runs in O(lenm1^2). Radix sort
    # has a constant factor that is three times higher, so radix runtime is 3bits * lenm1
    # and insertion runtime is lenm1^2. Empirically, insertion is faster than radix iff
    # lenm1 < 3bits.
    # Insertion < Radix
    #   lenm1^2 < 3 * bits * lenm1
    #     lenm1 < 3bits
    if lenm1 < 3bits
        # at lenm1 = 64*3-1, QuickSort is about 20% faster than InsertionSort.
        alg = a.fallback === QuickSort && lenm1 > 120 ? QuickSort : SMALL_ALGORITHM
        return sort!(v, lo, hi, alg, o)
    end

    # At this point, we are committed to radix sort.
    u = uint_map!(v, lo, hi, o)

    # we subtract u_min to avoid radixing over unnecessary bits. For example,
    # Int32[3, -1, 2] uint_maps to UInt32[0x80000003, 0x7fffffff, 0x80000002]
    # which uses all 32 bits, but once we subtract u_min = 0x7fffffff, we are left with
    # UInt32[0x00000004, 0x00000000, 0x00000003] which uses only 3 bits, and
    # Float32[2.012, 400.0, 12.345] uint_maps to UInt32[0x3fff3b63, 0x3c37ffff, 0x414570a4]
    # which is reduced to UInt32[0x03c73b64, 0x00000000, 0x050d70a5] using only 26 bits.
    # the overhead for this subtraction is small enough that it is worthwhile in many cases.

    # this is faster than u[lo:hi] .-= u_min as of v1.9.0-DEV.100
    @inbounds for i in lo:hi
        u[i] -= u_min
    end

    u2 = radix_sort!(u, lo, hi, bits, similar(u))
    uint_unmap!(v, u2, lo, hi, o, u_min)
end

## generic sorting methods ##

defalg(v::AbstractArray) = DEFAULT_STABLE
defalg(v::AbstractArray{<:Union{Number, Missing}}) = DEFAULT_UNSTABLE
defalg(v::AbstractArray{Missing}) = DEFAULT_UNSTABLE # for method disambiguation
defalg(v::AbstractArray{Union{}}) = DEFAULT_UNSTABLE # for method disambiguation

function sort!(v::AbstractVector, alg::Algorithm, order::Ordering)
    inds = axes(v,1)
    sort!(v,first(inds),last(inds),alg,order)
end

"""
    sort!(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Sort the vector `v` in place. [`QuickSort`](@ref) is used by default for numeric arrays while
[`MergeSort`](@ref) is used for other arrays. You can specify an algorithm to use via the `alg`
keyword (see [Sorting Algorithms](@ref) for available algorithms). The `by` keyword lets you provide
a function that will be applied to each element before comparison; the `lt` keyword allows
providing a custom "less than" function (note that for every `x` and `y`, only one of `lt(x,y)`
and `lt(y,x)` can return `true`); use `rev=true` to reverse the sorting order. These
options are independent and can be used together in all possible combinations: if both `by`
and `lt` are specified, the `lt` function is applied to the result of the `by` function;
`rev=true` reverses whatever ordering specified via the `by` and `lt` keywords.

# Examples
```jldoctest
julia> v = [3, 1, 2]; sort!(v); v
3-element Vector{Int64}:
 1
 2
 3

julia> v = [3, 1, 2]; sort!(v, rev = true); v
3-element Vector{Int64}:
 3
 2
 1

julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[1]); v
3-element Vector{Tuple{Int64, String}}:
 (1, "c")
 (2, "b")
 (3, "a")

julia> v = [(1, "c"), (3, "a"), (2, "b")]; sort!(v, by = x -> x[2]); v
3-element Vector{Tuple{Int64, String}}:
 (3, "a")
 (2, "b")
 (1, "c")
```
"""
function sort!(v::AbstractVector;
               alg::Algorithm=defalg(v),
               lt=isless,
               by=identity,
               rev::Union{Bool,Nothing}=nothing,
               order::Ordering=Forward)
    sort!(v, alg, ord(lt,by,rev,order))
end

# sort! for vectors of few unique integers
function sort_int_range!(x::AbstractVector{<:Integer}, rangelen, minval, maybereverse,
                         lo=firstindex(x), hi=lastindex(x))
    offs = 1 - minval

    counts = fill(0, rangelen)
    @inbounds for i = lo:hi
        counts[x[i] + offs] += 1
    end

    idx = lo
    @inbounds for i = maybereverse(1:rangelen)
        lastidx = idx + counts[i] - 1
        val = i-offs
        for j = idx:lastidx
            x[j] = val
        end
        idx = lastidx + 1
    end

    return x
end

"""
    sort(v; alg::Algorithm=defalg(v), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Variant of [`sort!`](@ref) that returns a sorted copy of `v` leaving `v` itself unmodified.

# Examples
```jldoctest
julia> v = [3, 1, 2];

julia> sort(v)
3-element Vector{Int64}:
 1
 2
 3

julia> v
3-element Vector{Int64}:
 3
 1
 2
```
"""
sort(v::AbstractVector; kws...) = sort!(copymutable(v); kws...)

## partialsortperm: the permutation to sort the first k elements of an array ##

"""
    partialsortperm(v, k; by=<transform>, lt=<comparison>, rev=false)

Return a partial permutation `I` of the vector `v`, so that `v[I]` returns values of a fully
sorted version of `v` at index `k`. If `k` is a range, a vector of indices is returned; if
`k` is an integer, a single index is returned. The order is specified using the same
keywords as `sort!`. The permutation is stable, meaning that indices of equal elements
appear in ascending order.

Note that this function is equivalent to, but more efficient than, calling `sortperm(...)[k]`.

# Examples
```jldoctest
julia> v = [3, 1, 2, 1];

julia> v[partialsortperm(v, 1)]
1

julia> p = partialsortperm(v, 1:3)
3-element view(::Vector{Int64}, 1:3) with eltype Int64:
 2
 4
 3

julia> v[p]
3-element Vector{Int64}:
 1
 1
 2
```
"""
partialsortperm(v::AbstractVector, k::Union{Integer,OrdinalRange}; kwargs...) =
    partialsortperm!(similar(Vector{eltype(k)}, axes(v,1)), v, k; kwargs..., initialized=false)

"""
    partialsortperm!(ix, v, k; by=<transform>, lt=<comparison>, rev=false, initialized=false)

Like [`partialsortperm`](@ref), but accepts a preallocated index vector `ix` the same size as
`v`, which is used to store (a permutation of) the indices of `v`.

If the index vector `ix` is initialized with the indices of `v` (or a permutation thereof), `initialized` should be set to
`true`.

If `initialized` is `false` (the default), then `ix` is initialized to contain the indices of `v`.

If `initialized` is `true`, but `ix` does not contain (a permutation of) the indices of `v`, the behavior of
`partialsortperm!` is undefined.

(Typically, the indices of `v` will be `1:length(v)`, although if `v` has an alternative array type
with non-one-based indices, such as an `OffsetArray`, `ix` must also be an `OffsetArray` with the same
indices, and must contain as values (a permutation of) these same indices.)

Upon return, `ix` is guaranteed to have the indices `k` in their sorted positions, such that

```julia
partialsortperm!(ix, v, k);
v[ix[k]] == partialsort(v, k)
```

The return value is the `k`th element of `ix` if `k` is an integer, or view into `ix` if `k` is
a range.

# Examples
```jldoctest
julia> v = [3, 1, 2, 1];

julia> ix = Vector{Int}(undef, 4);

julia> partialsortperm!(ix, v, 1)
2

julia> ix = [1:4;];

julia> partialsortperm!(ix, v, 2:3, initialized=true)
2-element view(::Vector{Int64}, 2:3) with eltype Int64:
 4
 3
```
 """
function partialsortperm!(ix::AbstractVector{<:Integer}, v::AbstractVector,
                          k::Union{Integer, OrdinalRange};
                          lt::Function=isless,
                          by::Function=identity,
                          rev::Union{Bool,Nothing}=nothing,
                          order::Ordering=Forward,
                          initialized::Bool=false)
    if axes(ix,1) != axes(v,1)
        throw(ArgumentError("The index vector is used as a workspace and must have the " *
                            "same length/indices as the source vector, $(axes(ix,1)) != $(axes(v,1))"))
    end
    if !initialized
        @inbounds for i = axes(ix,1)
            ix[i] = i
        end
    end

    # do partial quicksort
    sort!(ix, PartialQuickSort(k), Perm(ord(lt, by, rev, order), v))

    maybeview(ix, k)
end

## sortperm: the permutation to sort an array ##

"""
    sortperm(v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Return a permutation vector `I` that puts `v[I]` in sorted order. The order is specified
using the same keywords as [`sort!`](@ref). The permutation is guaranteed to be stable even
if the sorting algorithm is unstable, meaning that indices of equal elements appear in
ascending order.

See also [`sortperm!`](@ref), [`partialsortperm`](@ref), [`invperm`](@ref), [`indexin`](@ref).

# Examples
```jldoctest
julia> v = [3, 1, 2];

julia> p = sortperm(v)
3-element Vector{Int64}:
 2
 3
 1

julia> v[p]
3-element Vector{Int64}:
 1
 2
 3
```
"""
function sortperm(v::AbstractVector;
                  alg::Algorithm=DEFAULT_UNSTABLE,
                  lt=isless,
                  by=identity,
                  rev::Union{Bool,Nothing}=nothing,
                  order::Ordering=Forward)
    ordr = ord(lt,by,rev,order)
    if ordr === Forward && isa(v,Vector) && eltype(v)<:Integer
        n = length(v)
        if n > 1
            min, max = extrema(v)
            (diff, o1) = sub_with_overflow(max, min)
            (rangelen, o2) = add_with_overflow(diff, oneunit(diff))
            if !o1 && !o2 && rangelen < div(n,2)
                return sortperm_int_range(v, rangelen, min)
            end
        end
    end
    ax = axes(v, 1)
    p = similar(Vector{eltype(ax)}, ax)
    for (i,ind) in zip(eachindex(p), ax)
        p[i] = ind
    end
    sort!(p, alg, Perm(ordr,v))
end

"""
    sortperm!(ix, v; alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward, initialized::Bool=false)

Like [`sortperm`](@ref), but accepts a preallocated index vector `ix`.  If `initialized` is `false`
(the default), `ix` is initialized to contain the values `1:length(v)`.

# Examples
```jldoctest
julia> v = [3, 1, 2]; p = zeros(Int, 3);

julia> sortperm!(p, v); p
3-element Vector{Int64}:
 2
 3
 1

julia> v[p]
3-element Vector{Int64}:
 1
 2
 3
```
"""
function sortperm!(x::AbstractVector{<:Integer}, v::AbstractVector;
                   alg::Algorithm=DEFAULT_UNSTABLE,
                   lt=isless,
                   by=identity,
                   rev::Union{Bool,Nothing}=nothing,
                   order::Ordering=Forward,
                   initialized::Bool=false)
    if axes(x,1) != axes(v,1)
        throw(ArgumentError("index vector must have the same length/indices as the source vector, $(axes(x,1)) != $(axes(v,1))"))
    end
    if !initialized
        @inbounds for i = axes(v,1)
            x[i] = i
        end
    end
    sort!(x, alg, Perm(ord(lt,by,rev,order),v))
end

# sortperm for vectors of few unique integers
function sortperm_int_range(x::Vector{<:Integer}, rangelen, minval)
    offs = 1 - minval
    n = length(x)

    counts = fill(0, rangelen+1)
    counts[1] = 1
    @inbounds for i = 1:n
        counts[x[i] + offs + 1] += 1
    end

    #cumsum!(counts, counts)
    @inbounds for i = 2:length(counts)
        counts[i] += counts[i-1]
    end

    P = Vector{Int}(undef, n)
    @inbounds for i = 1:n
        label = x[i] + offs
        P[counts[label]] = i
        counts[label] += 1
    end

    return P
end

## sorting multi-dimensional arrays ##

"""
    sort(A; dims::Integer, alg::Algorithm=DEFAULT_UNSTABLE, lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Sort a multidimensional array `A` along the given dimension.
See [`sort!`](@ref) for a description of possible
keyword arguments.

To sort slices of an array, refer to [`sortslices`](@ref).

# Examples
```jldoctest
julia> A = [4 3; 1 2]
2×2 Matrix{Int64}:
 4  3
 1  2

julia> sort(A, dims = 1)
2×2 Matrix{Int64}:
 1  2
 4  3

julia> sort(A, dims = 2)
2×2 Matrix{Int64}:
 3  4
 1  2
```
"""
function sort(A::AbstractArray;
              dims::Integer,
              alg::Algorithm=DEFAULT_UNSTABLE,
              lt=isless,
              by=identity,
              rev::Union{Bool,Nothing}=nothing,
              order::Ordering=Forward)
    dim = dims
    order = ord(lt,by,rev,order)
    n = length(axes(A, dim))
    if dim != 1
        pdims = (dim, setdiff(1:ndims(A), dim)...)  # put the selected dimension first
        Ap = permutedims(A, pdims)
        Av = vec(Ap)
        sort_chunks!(Av, n, alg, order)
        permutedims(Ap, invperm(pdims))
    else
        Av = A[:]
        sort_chunks!(Av, n, alg, order)
        reshape(Av, axes(A))
    end
end

@noinline function sort_chunks!(Av, n, alg, order)
    inds = LinearIndices(Av)
    for s = first(inds):n:last(inds)
        sort!(Av, s, s+n-1, alg, order)
    end
    Av
end

"""
    sort!(A; dims::Integer, alg::Algorithm=defalg(A), lt=isless, by=identity, rev::Bool=false, order::Ordering=Forward)

Sort the multidimensional array `A` along dimension `dims`.
See [`sort!`](@ref) for a description of possible keyword arguments.

To sort slices of an array, refer to [`sortslices`](@ref).

!!! compat "Julia 1.1"
    This function requires at least Julia 1.1.

# Examples
```jldoctest
julia> A = [4 3; 1 2]
2×2 Matrix{Int64}:
 4  3
 1  2

julia> sort!(A, dims = 1); A
2×2 Matrix{Int64}:
 1  2
 4  3

julia> sort!(A, dims = 2); A
2×2 Matrix{Int64}:
 1  2
 3  4
```
"""
function sort!(A::AbstractArray;
               dims::Integer,
               alg::Algorithm=defalg(A),
               lt=isless,
               by=identity,
               rev::Union{Bool,Nothing}=nothing,
               order::Ordering=Forward)
    ordr = ord(lt, by, rev, order)
    nd = ndims(A)
    k = dims

    1 <= k <= nd || throw(ArgumentError("dimension out of range"))

    remdims = ntuple(i -> i == k ? 1 : axes(A, i), nd)
    for idx in CartesianIndices(remdims)
        Av = view(A, ntuple(i -> i == k ? Colon() : idx[i], nd)...)
        sort!(Av, alg, ordr)
    end
    A
end

## uint mapping to allow radix sorting primitives other than UInts ##

"""
    UIntMappable(T::Type, order::Ordering)

Return `typeof(uint_map(x::T, order))` if [`uint_map`](@ref) and
[`uint_unmap`](@ref) are implemented.

If either is not implemented, return `nothing`.
"""
UIntMappable(T::Type, order::Ordering) = nothing

"""
    uint_map(x, order::Ordering)::Unsigned

Map `x` to an un unsigned integer, maintaining sort order.

The map should be reversible with [`uint_unmap`](@ref), so `isless(order, a, b)` must be
a linear ordering for `a, b <: typeof(x)`. Satisfies
`isless(order, a, b) === (uint_map(a, order) < uint_map(b, order))`
and `x === uint_unmap(typeof(x), uint_map(x, order), order)`

See also: [`UIntMappable`](@ref) [`uint_unmap`](@ref)
"""
function uint_map end

"""
    uint_unmap(T::Type, u::Unsigned, order::Ordering)

Reconstruct the unique value `x::T` that uint_maps to `u`. Satisfies
`x === uint_unmap(T, uint_map(x::T, order), order)` for all `x <: T`.

See also: [`uint_map`](@ref) [`UIntMappable`](@ref)
"""
function uint_unmap end

### Primitive Types

# Integers
uint_map(x::Unsigned, ::ForwardOrdering) = x
uint_unmap(::Type{T}, u::T, ::ForwardOrdering) where T <: Unsigned = u

uint_map(x::Signed, ::ForwardOrdering) =
    unsigned(xor(x, typemin(x)))
uint_unmap(::Type{T}, u::Unsigned, ::ForwardOrdering) where T <: Signed =
    xor(signed(u), typemin(T))

# unsigned(Int) is not available during bootstrapping.
for (U, S) in [(UInt8, Int8), (UInt16, Int16), (UInt32, Int32), (UInt64, Int64), (UInt128, Int128)]
    @eval UIntMappable(::Type{<:Union{$U, $S}}, ::ForwardOrdering) = $U
end

# Floats are not UIntMappable under regular orderings because they fail on NaN edge cases.
# uint mappings for floats are defined in Float, where the Left and Right orderings
# guarantee that there are no NaN values

# Chars
uint_map(x::Char, ::ForwardOrdering) = reinterpret(UInt32, x)
uint_unmap(::Type{Char}, u::UInt32, ::ForwardOrdering) = reinterpret(Char, u)
UIntMappable(::Type{Char}, ::ForwardOrdering) = UInt32

### Reverse orderings
uint_map(x, rev::ReverseOrdering) = ~uint_map(x, rev.fwd)
uint_unmap(T::Type, u::Unsigned, rev::ReverseOrdering) = uint_unmap(T, ~u, rev.fwd)
UIntMappable(T::Type, order::ReverseOrdering) = UIntMappable(T, order.fwd)

### Vectors

# Convert v to unsigned integers in place, maintaining sort order.
function uint_map!(v::AbstractVector, lo::Integer, hi::Integer, order::Ordering)
    u = reinterpret(UIntMappable(eltype(v), order), v)
    @inbounds for i in lo:hi
        u[i] = uint_map(v[i], order)
    end
    u
end

function uint_unmap!(v::AbstractVector, u::AbstractVector{U}, lo::Integer, hi::Integer,
                     order::Ordering, offset::U=zero(U)) where U <: Unsigned
    @inbounds for i in lo:hi
        v[i] = uint_unmap(eltype(v), u[i]+offset, order)
    end
    v
end

## fast clever sorting for floats ##

module Float
using ..Sort
using ...Order
using ..Base: @inbounds, AbstractVector, Vector, last, axes, Missing, Type, reinterpret

import Core.Intrinsics: slt_int
import ..Sort: sort!, UIntMappable, uint_map, uint_unmap
import ...Order: lt, DirectOrdering

const Floats = Union{Float32,Float64}
const FPSortable = Union{ # Mixed Float32 and Float64 are not allowed.
    AbstractVector{Union{Float32, Missing}},
    AbstractVector{Union{Float64, Missing}},
    AbstractVector{Float32},
    AbstractVector{Float64},
    AbstractVector{Missing}}

struct Left <: Ordering end
struct Right <: Ordering end

left(::DirectOrdering) = Left()
right(::DirectOrdering) = Right()

left(o::Perm) = Perm(left(o.order), o.data)
right(o::Perm) = Perm(right(o.order), o.data)

lt(::Left, x::T, y::T) where {T<:Floats} = slt_int(y, x)
lt(::Right, x::T, y::T) where {T<:Floats} = slt_int(x, y)

uint_map(x::Float32, ::Left) = ~reinterpret(UInt32, x)
uint_unmap(::Type{Float32}, u::UInt32, ::Left) = reinterpret(Float32, ~u)
uint_map(x::Float32, ::Right) = reinterpret(UInt32, x)
uint_unmap(::Type{Float32}, u::UInt32, ::Right) = reinterpret(Float32, u)
UIntMappable(::Type{Float32}, ::Union{Left, Right}) = UInt32

uint_map(x::Float64, ::Left) = ~reinterpret(UInt64, x)
uint_unmap(::Type{Float64}, u::UInt64, ::Left) = reinterpret(Float64, ~u)
uint_map(x::Float64, ::Right) = reinterpret(UInt64, x)
uint_unmap(::Type{Float64}, u::UInt64, ::Right) = reinterpret(Float64, u)
UIntMappable(::Type{Float64}, ::Union{Left, Right}) = UInt64

isnan(o::DirectOrdering, x::Floats) = (x!=x)
isnan(o::DirectOrdering, x::Missing) = false
isnan(o::Perm, i::Integer) = isnan(o.order,o.data[i])

ismissing(o::DirectOrdering, x::Floats) = false
ismissing(o::DirectOrdering, x::Missing) = true
ismissing(o::Perm, i::Integer) = ismissing(o.order,o.data[i])

allowsmissing(::AbstractVector{T}, ::DirectOrdering) where {T} = T >: Missing
allowsmissing(::AbstractVector{<:Integer},
              ::Perm{<:DirectOrdering,<:AbstractVector{T}}) where {T} =
    T >: Missing

function specials2left!(testf::Function, v::AbstractVector, o::Ordering,
                        lo::Integer=first(axes(v,1)), hi::Integer=last(axes(v,1)))
    i = lo
    @inbounds while i <= hi && testf(o,v[i])
        i += 1
    end
    j = i + 1
    @inbounds while j <= hi
        if testf(o,v[j])
            v[i], v[j] = v[j], v[i]
            i += 1
        end
        j += 1
    end
    return i, hi
end
function specials2right!(testf::Function, v::AbstractVector, o::Ordering,
                         lo::Integer=first(axes(v,1)), hi::Integer=last(axes(v,1)))
    i = hi
    @inbounds while lo <= i && testf(o,v[i])
        i -= 1
    end
    j = i - 1
    @inbounds while lo <= j
        if testf(o,v[j])
            v[i], v[j] = v[j], v[i]
            i -= 1
        end
        j -= 1
    end
    return lo, i
end

function specials2left!(v::AbstractVector, a::Algorithm, o::Ordering)
    lo, hi = first(axes(v,1)), last(axes(v,1))
    if allowsmissing(v, o)
        i, _ = specials2left!((v, o) -> ismissing(v, o) || isnan(v, o), v, o, lo, hi)
        sort!(v, lo, i-1, a, o)
        return i, hi
    else
        return specials2left!(isnan, v, o, lo, hi)
    end
end
function specials2right!(v::AbstractVector, a::Algorithm, o::Ordering)
    lo, hi = first(axes(v,1)), last(axes(v,1))
    if allowsmissing(v, o)
        _, i = specials2right!((v, o) -> ismissing(v, o) || isnan(v, o), v, o, lo, hi)
        sort!(v, i+1, hi, a, o)
        return lo, i
    else
        return specials2right!(isnan, v, o, lo, hi)
    end
end

specials2end!(v::AbstractVector, a::Algorithm, o::ForwardOrdering) =
    specials2right!(v, a, o)
specials2end!(v::AbstractVector, a::Algorithm, o::ReverseOrdering) =
    specials2left!(v, a, o)
specials2end!(v::AbstractVector{<:Integer}, a::Algorithm, o::Perm{<:ForwardOrdering}) =
    specials2right!(v, a, o)
specials2end!(v::AbstractVector{<:Integer}, a::Algorithm, o::Perm{<:ReverseOrdering}) =
    specials2left!(v, a, o)

issignleft(o::ForwardOrdering, x::Floats) = lt(o, x, zero(x))
issignleft(o::ReverseOrdering, x::Floats) = lt(o, x, -zero(x))
issignleft(o::Perm, i::Integer) = issignleft(o.order, o.data[i])

function fpsort!(v::AbstractVector, a::Algorithm, o::Ordering)
    # fpsort!'s optimizations speed up comparisons, of which there are O(nlogn).
    # The overhead is O(n). For n < 10, it's not worth it.
    length(v) < 10 && return sort!(v, first(axes(v,1)), last(axes(v,1)), SMALL_ALGORITHM, o)

    i, j = lo, hi = specials2end!(v,a,o)
    @inbounds while true
        while i <= j &&  issignleft(o,v[i]); i += 1; end
        while i <= j && !issignleft(o,v[j]); j -= 1; end
        i <= j || break
        v[i], v[j] = v[j], v[i]
        i += 1; j -= 1
    end
    sort!(v, lo, j,  a, left(o))
    sort!(v, i,  hi, a, right(o))
    return v
end

fpsort!(v::AbstractVector, a::Sort.PartialQuickSort, o::Ordering) =
    sort!(v, first(axes(v,1)), last(axes(v,1)), a, o)

sort!(v::FPSortable, a::Algorithm, o::DirectOrdering) =
    fpsort!(v, a, o)
sort!(v::AbstractVector{<:Union{Signed, Unsigned}}, a::Algorithm, o::Perm{<:DirectOrdering,<:FPSortable}) =
    fpsort!(v, a, o)

end # module Sort.Float

end # module Sort

max_stars_repo_name: SmiteWindows/julia

max_issues_repo_name: SmiteWindows/julia

max_forks_repo_name: SmiteWindows/julia


text:
using BandedMatrices, ArrayLayouts, LinearAlgebra, FillArrays, Test
import Base.Broadcast: materialize, broadcasted
import BandedMatrices: BandedColumns, _BandedMatrix

@testset "Linear Algebra" begin
    @testset "Matrix types" begin
        A = brand(5,5,1,2)
        x = randn(5)

        @test A*x ≈ Matrix(A)*x

        @test A*A == A^2 ≈ Matrix(A)^2
        @test A*A isa BandedMatrix
        @test A^2 isa BandedMatrix
        @test bandwidths(A^2) == (2,4)

        @test A*A' isa BandedMatrix
        @test A*A' ≈ Matrix(A)*Matrix(A)'
        @test bandwidths(A*A') == (3,3)

        @test A'*A isa BandedMatrix
        @test A'*A ≈ Matrix(A)'*Matrix(A)
        @test bandwidths(A'*A) == (3,3)

        @test MemoryLayout(typeof(Symmetric(A))) == SymmetricLayout{BandedColumns{DenseColumnMajor}}()
        @test Symmetric(A)*A isa BandedMatrix
        @test Symmetric(A)*A ≈ Symmetric(Matrix(A))*Matrix(A)
        @test bandwidths(Symmetric(A)*A) == (3,4)

        @test Hermitian(A)*A isa BandedMatrix
        @test Hermitian(A)*A ≈ Hermitian(Matrix(A))*Matrix(A)
        @test bandwidths(Hermitian(A)*A) == (3,4)

        B = A+im*A
        @test Hermitian(B)*A isa BandedMatrix
        @test Hermitian(B)*A ≈ Hermitian(Matrix(B))*Matrix(A)
        @test bandwidths(Hermitian(B)*A) == (3,4)

        @test UpperTriangular(A)*A isa BandedMatrix
        @test UpperTriangular(A)*A ≈ UpperTriangular(Matrix(A))*Matrix(A)
        @test bandwidths(UpperTriangular(A)*A) == (1,4)
    end

    @testset "gbmm!" begin
        @testset "gbmm! subpieces step by step and column by column" begin
            for n in (1,5,50), ν in (1,5,50), m in (1,5,50),
                            Al in (0,1,2,30), Au in (0,1,2,30),
                            Bl in (0,1,2,30), Bu in (0,1,2,30)
                A=brand(n,ν,Al,Au)
                B=brand(ν,m,Bl,Bu)
                α,β,T=0.123,0.456,Float64
                C=brand(Float64,n,m,A.l+B.l,A.u+B.u)
                a=pointer(A.data)
                b=pointer(B.data)
                c=pointer(C.data)
                sta=max(1,stride(A.data,2))
                stb=max(1,stride(B.data,2))
                stc=max(1,stride(C.data,2))

                sz=sizeof(T)

                mr=1:min(m,1+B.u)
                exC=(β*Matrix(C)+α*Matrix(A)*Matrix(B))
                for j=mr
                    BandedMatrices.A11_Btop_Ctop_gbmv!(α,β,
                                                    n,ν,m,j,
                                                    sz,
                                                    a,A.l,A.u,sta,
                                                    b,B.l,B.u,stb,
                                                    c,C.l,C.u,stc)
                end
                @test C[:,mr] ≈ exC[:,mr]

                mr=1+B.u:min(1+C.u,ν+B.u,m)
                exC=(β*Matrix(C)+α*Matrix(A)*Matrix(B))
                for j=mr
                    BandedMatrices.Atop_Bmid_Ctop_gbmv!(α,β,
                                                    n,ν,m,j,
                                                    sz,
                                                    a,A.l,A.u,sta,
                                                    b,B.l,B.u,stb,
                                                    c,C.l,C.u,stc)
                end
                if !isempty(mr)
                    @test C[:,mr] ≈ exC[:,mr]
                end

                mr=1+C.u:min(m,ν+B.u,n+C.u)
                exC=(β*Matrix(C)+α*Matrix(A)*Matrix(B))
                for j=mr
                    BandedMatrices.Amid_Bmid_Cmid_gbmv!(α,β,
                                                    n,ν,m,j,
                                                    sz,
                                                    a,A.l,A.u,sta,
                                                    b,B.l,B.u,stb,
                                                    c,C.l,C.u,stc)
                end
                if !isempty(mr)
                    @test C[:,mr] ≈ exC[:,mr]
                end

                mr=ν+B.u+1:min(m,n+C.u)
                exC=(β*Matrix(C)+α*Matrix(A)*Matrix(B))
                for j=mr
                    BandedMatrices.Anon_Bnon_C_gbmv!(α,β,
                                                    n,ν,m,j,
                                                    sz,
                                                    a,A.l,A.u,sta,
                                                    b,B.l,B.u,stb,
                                                    c,C.l,C.u,stc)
                end
                if !isempty(mr)
                    @test C[:,mr] ≈ exC[:,mr]
                end
            end
        end

        for n in (1,5,50), ν in (1,5,50), m in (1,5,50), Al in (0,1,2,30), Au in (0,1,2,30), Bl in (0,1,2,30), Bu in (0,1,2,30)
            A=brand(n,ν,Al,Au)
            B=brand(ν,m,Bl,Bu)
            α,β,T=0.123,0.456,Float64
            C=brand(Float64,n,m,A.l+B.l,A.u+B.u)
            Cold = deepcopy(C)
            exC=α*Matrix(A)*Matrix(B)+β*Matrix(C)
            BandedMatrices.gbmm!('N','N', α,A,B,β,C)

            @test Matrix(exC) ≈ Matrix(C)
        end
    end

    @testset "Negative bands fills with zero" begin
        A = brand(10,10,2,2)
        B = brand(10,10,-2,2)
        C = BandedMatrix(Fill(NaN,10,10),(0,4))
        mul!(C,A,B)
        @test C ≈ Matrix(A)*Matrix(B)

        A = brand(10,10,-2,2)
        B = brand(10,10,-2,2)
        C = BandedMatrix(Fill(NaN,10,10),(-4,4))
        mul!(C,A,B)
        @test C ≈ Matrix(A)*Matrix(B)

        A = brand(10,10,-2,2)
        B = brand(10,10,2,2)
        C = BandedMatrix(Fill(NaN,10,10),(0,4))
        mul!(C,A,B)
        @test C ≈ Matrix(A)*Matrix(B)

        A = brand(10,10,2,2)
        B = brand(10,10,2,-2)
        C = BandedMatrix(Fill(NaN,10,10),(4,0))
        mul!(C,A,B)
        @test C ≈ Matrix(A)*Matrix(B)

        A = brand(10,10,2,-2)
        B = brand(10,10,2,-2)
        C = BandedMatrix(Fill(NaN,10,10),(4,-4))
        mul!(C,A,B)
        @test C ≈ Matrix(A)*Matrix(B)

        A = brand(10,10,2,-2)
        B = brand(10,10,2,2)
        C = BandedMatrix(Fill(NaN,10,10),(4,0))
        mul!(C,A,B)
        @test C ≈ Matrix(A)*Matrix(B)

        A = brand(30,1,0,0)
        B = brand(1,30,17,17)
        C = BandedMatrix(Fill(NaN, 30,30), (17,17))
        mul!(C,A,B)
        @test C ≈ Matrix(A)*Matrix(B)
    end

    @testset "Not enough bands" begin
        A = BandedMatrix(Zeros(10,10), (1,1))
        A[band(0)] .= randn(10)
        B = BandedMatrix(randn(10,10), (1,1))
        C = BandedMatrix(Zeros(10,10), (1,1))

        mul!(C,A,B)

        @test all(C .=== A*B)

        A[band(1)] .= randn(9)
        @test_throws BandError mul!(C,A,B)

        A = BandedMatrix(randn(2,1), (2,0))
        A[1,1] = 0
        B = BandedMatrix(randn(1,1), (1,1))
        C = BandedMatrix(randn(2,1), (2,0))
        D = A * B + C
        @test BandedMatrices.gbmm!('N','N', 1.0 , A, B, 1.0, C) ≈ D
    end

    @testset "BandedMatrix{Int} * Vector{Vector{Int}}" begin
        A, x =  [1 2; 3 4] , [[1,2],[3,4]]
        @test BandedMatrix(A)*x == A*x
    end

    @testset "Sym * Banded bug" begin
        A = SymTridiagonal(randn(10),randn(9))
        B = BandedMatrix((-1 => Ones{Int}(8),), (10,8))

        M = MulAdd(A,B)
        C = Matrix{Float64}(undef,10,8)
        fill!(C,NaN)
        C .= M
        @test C == A*B == Matrix(A)*Matrix(B)
        @test A*B isa BandedMatrix
    end

    @testset "Overwrite NaN" begin
        B = BandedMatrix{Float64}(undef,(2,2),(-1,-1))
        @test copyto!(fill(NaN,2), MulAdd(B,ones(2))) == [0.0,0.0]
    end

    @testset "NaN Bug" begin
        C = BandedMatrix{Float64}(undef, (1,2), (0,2)); C.data .= NaN;
        A = brand(1,1,0,1)
        B = brand(1,2,0,2)
        muladd!(1.0,A,B,0.0,C)
        @test C == A*B
    end

    @testset "x' ambiguity (#102)" begin
        x = randn(10)
        A = brand(10,10,1,1)
        @test x'A ≈ x'Matrix(A) ≈ transpose(x)A
    end

    @testset "mismatched dimensions (#118)" begin
        m = BandedMatrix(Eye(3), (0,0))
        @test_throws DimensionMismatch m * [1,2]
        @test_throws DimensionMismatch m * [1, 2, 3, 4]
        @test_throws DimensionMismatch m \ [1, 2]
    end

    @testset "Banded*Diagonal*Banded" begin
        A = brand(4,4,1,1)
        D= Diagonal(randn(4))
        @test A*D*A isa BandedMatrix
        @test Matrix(A)*D*Matrix(A) ≈ A*D*A
        @test D*A' isa BandedMatrix
        @test A'D isa BandedMatrix
        @test A'*D*A isa BandedMatrix
        @test  A'*D*A ≈ Matrix(A)'*D*Matrix(A)
    end

    @testset "muladd! throws error" begin
        A = _BandedMatrix(Ones(3,10), 10, 1, 1)
        @test_throws ArgumentError muladd!(1.0, A, A, 1.0, Zeros(10,10))
    end

    @testset "Diagonal issue (#188)" begin
        W = diagm(0=>-(1:10.0))
        B = brand(Float64, 10, 10, 0, 2)
        @test W\B == W\Matrix(B)
    end
end