text:
"""
    to_univariate_finite(scores::Scores)

Convert normalized scores to a vector of univariate finite distributions.

Parameters
----------
    scores::[`Scores`](@ref)

Returns
----------
    fit::UnivariateFiniteVector{OrderedFactor{2}}
The learned model of the given detector, which contains all the necessary information for later prediction and the
achieved outlier scores of the given input data `X`.
"""
function to_univariate_finite(scores::Scores)
    MLJ.UnivariateFinite([CLASS_NORMAL, CLASS_OUTLIER], scores; augment=true, pool=missing, ordered=true)
end
to_univariate_finite(scores::MLJ.AbstractNode) = MLJ.node(to_univariate_finite, scores)

"""
    to_categorical(classes::Labels)

Convert a vector of classes (with possible missing values) to a categorical vector.

Parameters
----------
    classes::[`Labels`](@ref)
A vector of classes.

Returns
----------
    fit::CategoricalVector{Union{Missing, String},UInt32}
The learned model of the given detector, which contains all the necessary information for later prediction and the
achieved outlier scores of the given input data `X`.
"""
function to_categorical(classes::Labels)
    # explicit cast to Vector{Union{String, Missing}} in case only missing values are passed
    c = Vector{Union{String, Missing}}(classes)
    # we cast to string if no missing values are present
    MLJ.categorical(try Vector{String}(c) catch c end, ordered=true, levels=[CLASS_NORMAL, CLASS_OUTLIER])
end
to_categorical(classes::MLJ.AbstractNode) = MLJ.node(to_categorical, classes)

"""
    raw_scores(scores)

Extract the raw scores from a vector of univariate finite distributions.

Parameters
----------
    scores::MLJ.UnivariateFiniteVector
A vector of univariate finite distributions.

Returns
----------
    scores::[`Scores`](@ref)
A vector of raw scores.
"""
from_univariate_finite(scores) = MLJ.pdf.(scores, CLASS_OUTLIER)
from_univariate_finite(scores::MLJ.Node) = MLJ.node(from_univariate_finite, scores)

"""
    raw_scores(scores)

Extract the raw classes from categorical arrays.

Parameters
----------
    scores::MLJ.CategoricalVector
A vector of categorical values.

Returns
----------
    scores::[`Labels`](@ref)
A vector of raw classes.
"""
from_categorical(categorical) = MLJ.unwrap.(categorical)
from_categorical(categorical::MLJ.Node) = MLJ.node(from_categorical, categorical)

# transform a fitresult (containing only the model) back to a Fit containing the model and training scores
to_fitresult(mach::MLJ.Machine{<:OD.Detector})::Fit = (mach.fitresult, mach.report.scores)

# this includes all composites defined in mlj_wrappers.jl
const DetectorComposites = Union{
    MLJ.Machine{<:MLJ.SupervisedDetectorComposite},
    MLJ.Machine{<:MLJ.UnsupervisedDetectorComposite},
    MLJ.Machine{<:MLJ.ProbabilisticUnsupervisedDetectorComposite},
    MLJ.Machine{<:MLJ.DeterministicUnsupervisedDetectorComposite},
    MLJ.Machine{<:MLJ.ProbabilisticSupervisedDetectorComposite},
    MLJ.Machine{<:MLJ.DeterministicSupervisedDetectorComposite}
}

function check_mach(mach)
    # catch deserialized machine with no data:
    isempty(mach.args) && MLJ._err_serialized(augmented_transform)
    # catch not-yet-trained machine:
    mach.state > 0 || error("$mach has not been trained.")
end

function _augmented_transform(detector::Detector, fitresult::Fit, X)
    model, scores_train = fitresult
    scores_test = MLJ.transform(detector, model, X)
    return scores_train, scores_test
end

# 0. augmented_transform given rows:
"""
    augmented_transform(mach; rows=:)

Extends `transform` by additionally returning the training scores from detectors as a train/test score tuple.

Parameters
----------
    mach::MLJ.Machine{<:OD.Detector}
A fitted machine with a detector model.

    rows
Test data specified as rows machine-bound data (as in `transform`), but could also provide new test data `X`.

Returns
----------
    augmented_scores::Tuple{AbstractVector{<:Real}, AbstractVector{<:Real}}
A tuple of raw training and test scores.
"""
function augmented_transform(mach::MLJ.Machine{<:OD.Detector}; rows=:)
    check_mach(mach)
    return _augmented_transform(mach.model, to_fitresult(mach), selectrows(mach.model, rows, mach.data[1])...)
end

function augmented_transform(mach::DetectorComposites; rows=:)
    check_mach(mach)
    scores_train = mach.report.scores
    scores_test = mach.fitresult.transform(selectrows(mach.model, rows, mach.data[1])...)
    return scores_train, scores_test
end

# 1. augmented_transform on machines, given *concrete* data:
function augmented_transform(mach::MLJ.Machine{<:OD.Detector}, X)
    check_mach(mach)
    return _augmented_transform(mach.model, to_fitresult(mach), reformat(mach.model, X)...)
end

function augmented_transform(mach::DetectorComposites, X)
    check_mach(mach)
    scores_train = mach.report.scores
    scores_test = mach.fitresult.transform(X)
    return scores_train, scores_test
end

# 2. operations on machines, given *dynamic* data (nodes):
function augmented_transform(mach::MLJ.Machine{<:OD.Detector}, X::MLJ.AbstractNode)
    MLJ.node(augmented_transform, mach, X)
end


text:
#
# The nominal type of database entities.
#

immutable Entity{C}
    val::Int
end

show{C}(io::IO, ::Type{Entity{C}}) =
    print(io, C)
Base.print{C}(io::IO, ::Type{Entity{C}}) =
    print(io, C)

show{C}(io::IO, e::Entity{C}) =
    print(io, "$(string(C))($(e.val))")

classname{C}(::Type{Entity{C}}) = C
classname{C}(::Entity{C}) = C

get(e::Entity) = e.val

convert{T<:Entity}(::Type{T}, val::Int) = T(val)

immutable EntityVector{C,V<:AbstractVector{Int}} <: AbstractVector{Entity{C}}
    vals::V
end

classname{C,T}(::Type{EntityVector{C,T}}) = C
classname{C,T}(::EntityVector{C,T}) = C

size(ev::EntityVector) = size(ev.vals)

length(ev::EntityVector) = length(ev.vals)

getindex{C}(ev::EntityVector{C}, i::Int) = Entity{C}(ev.vals[i])

getindex{C}(ev::EntityVector{C}, idxs::AbstractVector{Int}) =
    let vals = ev.vals[idxs]
        EntityVector{C,eltype(vals)}(vals)
    end

Base.array_eltype_show_how(::EntityVector) = (true, "")

convert{C,V<:AbstractVector{Int}}(::Type{EntityVector{C}}, vals::V) =
    EntityVector{C,V}(vals)

convert{C,V<:AbstractVector{Int}}(::Type{EntityVector{C,V}}, vals::V) =
    EntityVector{C,V}(vals)

ext: jl

max_stars_repo_name: rbt-lang/rbt-proto

max_issues_repo_name: rbt-lang/rbt-proto

max_forks_repo_name: rbt-lang/rbt-proto


text:
"""
UInt12Arrays supports the use of 12-bit unsigned integers.

The current design is based on reading 12-bit integers from a vector of
byte-multiple unsigned integers (Vector{UInt8}, Vector{UInt16}, Vector{UInt24}).

The default element type is a UInt16 to which provides best usability and
performance. However, a UInt12 type is also provided and can be used via a
parameter.

Note: The use of UInt16 as the default element may change as the UInt12 type
matures and lower level LLVM support emerges.
"""
module UInt12Arrays

using SIMD
using Mmap

const default_eltype = UInt16

# UInt24 is useful since UInt24 represents three bytes and two 12-bit integers
# also widen(::UInt12)
include("UInt24s.jl")
# UInt12 type
include("UInt12s.jl")
# Base array type, may be split off into a discrete package in the future
include("UInt12ArraysBase.jl")
# Accelerated conversion
include("UnpackUInt12s.jl")

import .UInt12ArraysBase: UInt12Array, UInt12Vector
using .UInt12s, .UInt24s
using .UnpackUInt12s

export UInt12Array, UInt12Vector, UInt12, UInt24

end


text:
# SPDX-License-Identifier: X11
# 2020-08-31
# One Quadrillion and One Dalmatians (300pt)

const BASE = 26

function main()
  N = parse(Int64, readline())

  exp = 1
  upper = BASE
  while upper < N
    exp += 1
    upper += BASE^exp
  end
  N -= upper - BASE^exp + 1

  name = Vector{Char}(undef, exp)

  for i ∈ exp:-1:1
    N, c = divrem(N, BASE)
    name[i] = 'a' + c
  end

  println(string(name...))
end

main()

max_stars_repo_name: jthvai/competitive-programming

max_issues_repo_name: jthvai/competitive-programming

max_forks_repo_name: jthvai/competitive-programming


text:
export exhaust_map

import Base: show

"""
    exhaust_map(::Type{R}, mappingFn::F = identity) where { R, F <: Function }

Creates a `exhaust_map` operator, which returns an Observable containing projected Observables of each
item of the source, ignoring projected Observables that start before their preceding Observable has completed.
Essentially it projects each source value to an Observable which is merged in the output Observable only
if the previous projected Observable has completed.

# Arguments
- `::Type{R}`: the type of data of output Observables after projection with `mappingFn`
- `mappingFn::F`: projection function with `(data) -> Observable{R}` signature

# Producing

Stream of type `<: Subscribable{R}`

# Examples
```julia
using Rocket

source = from([ 0, 0 ]) |> async() |> exhaust_map(Int, d -> from([ 1, 2 ]) |> async())
subscribe!(source, logger())
;

# output

[LogActor] Data: 1
[LogActor] Data: 2
[LogActor] Completed
```

See also: [`AbstractOperator`](@ref), [`RightTypedOperator`](@ref), [`ProxyObservable`](@ref), [`logger`](@ref)
"""
exhaust_map(::Type{R}, mappingFn::F = identity) where { R, F <: Function } = ExhaustMapOperator{R, F}(mappingFn)

struct ExhaustMapOperator{R, F} <: RightTypedOperator{R}
    mappingFn :: F
end

function on_call!(::Type{L}, ::Type{R}, operator::ExhaustMapOperator{R, F}, source) where { L, R, F }
    return proxy(R, source, ExhaustMapProxy{L, R, F}(operator.mappingFn))
end

struct ExhaustMapProxy{L, R, F} <: ActorSourceProxy
    mappingFn :: F
end

actor_proxy!(::Type{R}, proxy::ExhaustMapProxy{L, R, F}, actor::A) where { L, R, F, A } = ExhaustMapActor{L, R, F, A}(proxy.mappingFn, actor)

# m - main
# i - inner
mutable struct ExhaustMapActorProps
    msubscription :: Teardown
    isubscription :: Teardown
    ismcompleted  :: Bool
    isicompleted  :: Bool
    isdisposed    :: Bool

    ExhaustMapActorProps() = new(voidTeardown, voidTeardown, false, true, false)
end

struct ExhaustMapActor{L, R, F, A} <: Actor{L}
    mappingFn :: F
    actor     :: A
    props     :: ExhaustMapActorProps

    ExhaustMapActor{L, R, F, A}(mappingFn::F, actor::A) where { L, R, F, A } = new(mappingFn, actor, ExhaustMapActorProps())
end

ismcompleted(actor::ExhaustMapActor) = actor.props.ismcompleted
isicompleted(actor::ExhaustMapActor) = actor.props.isicompleted

setmcompleted!(actor::ExhaustMapActor, value::Bool) = actor.props.ismcompleted = value
seticompleted!(actor::ExhaustMapActor, value::Bool) = actor.props.isicompleted = value

isdisposed(actor::ExhaustMapActor)   = actor.props.isdisposed

struct ExhaustMapInnerActor{R, S} <: Actor{R}
    main :: S
end

on_next!(actor::ExhaustMapInnerActor{R}, data::R) where R = next!(actor.main.actor, data)
on_error!(actor::ExhaustMapInnerActor,   err)             = error!(actor.main, err)
on_complete!(actor::ExhaustMapInnerActor)                 = begin
    actor.main.props.isubscription = voidTeardown
    seticompleted!(actor.main, true)
    if ismcompleted(actor.main)
        complete!(actor.main)
    end
end

function on_next!(actor::S, data::L) where { L, R, S <: ExhaustMapActor{L, R} }
    if !isdisposed(actor)
        if isicompleted(actor)
            unsubscribe!(actor.props.isubscription)
            seticompleted!(actor, false)
            actor.props.isubscription = subscribe!(actor.mappingFn(data), ExhaustMapInnerActor{R, S}(actor))
        end
    end
end

function on_error!(actor::ExhaustMapActor, err)
    if !isdisposed(actor)
        dispose!(actor)
        error!(actor.actor, err)
    end
end

function on_complete!(actor::ExhaustMapActor)
    setmcompleted!(actor, true)
    if !isdisposed(actor) && isicompleted(actor)
        dispose!(actor)
        complete!(actor.actor)
    end
end

function dispose!(actor::ExhaustMapActor)
    actor.props.isdisposed = true
    unsubscribe!(actor.props.msubscription)
    unsubscribe!(actor.props.isubscription)
end

struct ExhaustMapSource{L, S} <: Subscribable{L}
    source :: S
end

source_proxy!(::Type{R}, proxy::ExhaustMapProxy{L, R, F}, source::S) where { L, R, F, S } = ExhaustMapSource{L, S}(source)

function on_subscribe!(source::ExhaustMapSource, actor::ExhaustMapActor)
    actor.props.msubscription = subscribe!(source.source, actor)
    return ExhaustMapSubscription(actor)
end

struct ExhaustMapSubscription{A} <: Teardown
    actor :: A
end

as_teardown(::Type{ <: ExhaustMapSubscription }) = UnsubscribableTeardownLogic()

function on_unsubscribe!(subscription::ExhaustMapSubscription)
    dispose!(subscription.actor)
    return nothing
end

Base.show(io::IO, ::ExhaustMapOperator{R})   where {    R } = print(io, "ExhaustMapOperator($R)")
Base.show(io::IO, ::ExhaustMapProxy{L, R})   where { L, R } = print(io, "ExhaustMapProxy($L, $R)")
Base.show(io::IO, ::ExhaustMapActor{L, R})   where { L, R } = print(io, "ExhaustMapActor($L -> $R)")
Base.show(io::IO, ::ExhaustMapInnerActor{R}) where {    R } = print(io, "ExhaustMapInnerActor($R)")
Base.show(io::IO, ::ExhaustMapSource{S})     where S        = print(io, "ExhaustMapSource($S)")
Base.show(io::IO, ::ExhaustMapSubscription)                 = print(io, "ExhaustMapSubscription()")


text:
using TimeZones.TZData: DEFAULT_TZDATA_VERSION, tzdata_version

"""
    build(version="$DEFAULT_TZDATA_VERSION"; force=false) -> Nothing

Builds the TimeZones package with the specified tzdata `version` and `regions`. The
`version` is typically a 4-digit year followed by a lowercase ASCII letter
(e.g. "$DEFAULT_TZDATA_VERSION"). The `force` flag is used to re-download tzdata archives.
"""
function build(version::AbstractString=tzdata_version(); force::Bool=false)
    TimeZones.TZData.build(version)

    if Sys.iswindows()
        TimeZones.WindowsTimeZoneIDs.build(force=force)
    end

    # Reset cached information
    empty!(TIME_ZONE_CACHE)

    @info "Successfully built TimeZones"
end


text:
# ------------------------------------------------------------------
# Licensed under the MIT License. See LICENSE in the project root.
# ------------------------------------------------------------------

"""
    Segment(p1, p2)

An oriented line segment with end points `p1`, `p2`.
The segment can be called as `s(t)` with `t` between
`0` and `1` to interpolate linearly between its endpoints.

See also [`Line`](@ref).
"""
struct Segment{Dim,T,V<:AbstractVector{Point{Dim,T}}} <: Polytope{1,Dim,T}
  vertices::V
end

isconvex(::Type{<:Segment}) = true

nvertices(::Type{<:Segment}) = 2
nvertices(s::Segment) = nvertices(typeof(s))

Base.minimum(s::Segment) = s.vertices[1]
Base.maximum(s::Segment) = s.vertices[2]
Base.extrema(s::Segment) = s.vertices[1], s.vertices[2]
measure(s::Segment) = norm(s.vertices[2] - s.vertices[1])

function (s::Segment)(t)
  if t < 0 || t > 1
    throw(DomainError(t, "s(t) is not defined for t outside [0, 1]."))
  end
  p1, p2 = s.vertices
  p1 + t * (p2 - p1)
end


text:
"""
    parse_comment(text::AbstractString) -> (String, Dict{Symbol, String})

Parse a trigger comment with keyword arguments, and return (`name`, `keywords`).
Positional arguments are ignored.

If the input is invalid `(nothing, nothing)` is returned.

Valid input would look like this:

```
<action> key1=val1 key2=val2
--- anything here and below ---
```

The old syntax `action(key1=val1)` is supported for backwards compatibility.
"""
function parse_comment(text::AbstractString)
    # Handling leading ( is easy, but not capturing the closing one is a bit harder.
    text = replace(text, r"[\)\s]+$"m => "")

    captures = match(r"(\w+)\(?\s*(.*)", text)
    if captures === nothing
        @debug "Invalid trigger" text
        return nothing, nothing
    end

    # The first capture is the action.
    action = string(captures[1])

    # The second capture is keyword arguments.
    kwargs = Dict{Symbol, String}()
    foreach(eachmatch(r"([a-zA-Z_]\w*)\s*=\s*([^\s,]+)", captures[2])) do c
        # If the value is a literal string, remove the quotes.
        key = Symbol(c[1])
        val = strip(c[2], [' ', '"'])
        kwargs[key] = val
    end

    # Check that there are no duplicates or other oddities.
    if length(kwargs) != count(isequal('='), captures[2])
        @debug "Invalid trigger arguments" text args=captures[2]
        return nothing, nothing
    end

    return action, kwargs
end


text:
###############################################################################
################################## Conflicts ###################################
################################################################################
export
    Conflict,
    state_conflict,
    action_conflict,
    conflict_type,
    agent1_id,
    agent2_id,
    node1,
    node2,
    is_state_conflict,
    is_action_conflict

@with_kw struct Conflict{P1 <: PathNode,P2 <: PathNode}
    conflict_type   ::Symbol    = :NullConflict
    agent1_id       ::Int       = -1
    agent2_id       ::Int       = -1
    node1           ::P1        = P1()
    node2           ::P2        = P2()
    t               ::Int       = -1
end
state_conflict(args...) = Conflict(:StateConflict,args...)
action_conflict(args...) = Conflict(:ActionConflict,args...)
conflict_type(c::Conflict)   = c.conflict_type
is_state_conflict(c::Conflict) = conflict_type(c) == :StateConflict
is_action_conflict(c::Conflict) = conflict_type(c) == :ActionConflict
agent1_id(c::Conflict)       = c.agent1_id
agent2_id(c::Conflict)       = c.agent2_id
node1(c::Conflict)           = c.node1
node2(c::Conflict)           = c.node2
state1(c::Conflict)          = get_s(node1(c))
state2(c::Conflict)          = get_s(node2(c))
action1(c::Conflict)         = get_a(node1(c))
action2(c::Conflict)         = get_a(node2(c))
next_state1(c::Conflict)     = get_sp(node1(c))
next_state2(c::Conflict)     = get_sp(node2(c))
time_of(c::Conflict)         = c.t
Base.string(c::Conflict) = string(
    "conflict type: ",conflict_type(c),
    ": agent1=",agent1_id(c),
    ", agent2=", agent2_id(c),
    ", v1=(",get_s(node1(c)).vtx,",",get_sp(node1(c)).vtx,")",
    ", v2=(",get_s(node2(c)).vtx,",",get_sp(node2(c)).vtx,")",
    ", t=",get_s(node1(c)).t)

const SymmetricConflict{N} = Conflict{N,N}

Base.isless(c1::C,c2::C) where {C<:Conflict} = (
    [c1.t,c1.agent1_id,c1.agent2_id,is_state_conflict(c1)] < [c2.t,c2.agent1_id,c2.agent2_id,is_state_conflict(c2)]
)

""" Checks if a conflict is valid """
is_valid(c::C) where {C<:Conflict} = ((is_state_conflict(c) || is_action_conflict(c))
                                && (agent1_id(c) != agent2_id(c))
                                && (agent1_id(c) != -1)
                                && (agent2_id(c) != -1))

export
    detect_conflicts!,
    reset_conflict_table!,
    detect_conflicts

""" add detected conflicts to conflict table """
function detect_conflicts!(conflict_table,n1::P1,n2::P2,i::Int,j::Int,t::Int) where {P1<:PathNode,P2<:PathNode}
    error("detect_conflicts!(conflict_table,n1,n2,i,j,t) not yet implemented \n
        for conflict_table::",typeof(conflict_table),". \n
        Aborting Conflict Checking.")
    return conflict_table
end

"""
    detect conflicts between paths
"""
function detect_conflicts!(conflict_table,path1::P1,path2::P2,i::Int,j::Int,t0::Int=1) where {P1<:AbstractPath,P2<:AbstractPath}
    # print("detect_conflicts!(conflict_table,path1::Path,path2::Path,i::Int,j::Int)\n")
    if length(path1) > length(path2)
        path2 = extend_path(path2,length(path1))
    elseif length(path1) < length(path2)
        path1 = extend_path(path1,length(path2))
    end
    @assert(length(path1) == length(path2))
    reset_conflict_table!(conflict_table,i,j)
    for t in t0:length(path1)
        path_node1 = path1[t]
        path_node2 = path2[t]
        detect_conflicts!(conflict_table,path_node1,path_node2,i,j,t)
    end
    return conflict_table
end

"""
    Populates a `ConflictTable` with all conflicts that occur in a given vector
    of paths. Conflict checking is performed in a pairwise fashion between
    all paths.

    args:
    - conflict_table        a `ConflictTable` to store the detected conflicts
    - paths:                a list of `Path`s, one for each individual agent
    - idxs                  (optional) a list of agent ids for which to check
                            collisions against all other agents
"""
function detect_conflicts!(conflict_table, paths::Vector{P}, idxs=collect(1:length(paths)),args...) where {P<:AbstractPath}
    # print("detect_conflicts!(conflict_table, paths::LowLevelSolution, idxs=collect(1:length(paths)))\n")
    for (i,path1) in enumerate(paths)
        for (j,path2) in enumerate(paths)
            if j <= i
                continue
            end
            if (i in idxs) || (j in idxs) # save time by working only on the upper triangle
                detect_conflicts!(conflict_table,path1,path2,i,j,args...)
            end
        end
    end
    return conflict_table
end

function detect_conflicts!(conflict_table, solution::L, args...) where {L <: LowLevelSolution}
    detect_conflicts!(conflict_table,get_paths(solution),args...)
end

export
    detect_state_conflict

"""
    Detect a `StateConflict` between two path nodes. Must be overridden for each
    specific path class
"""
function detect_state_conflict(n1::P1,n2::P2) where {P1<:PathNode,P2<:PathNode}
    error("detect_state_conflict(n1,n2) Not Implemented for \nn1::",
        typeof(n1),",\nn2::",typeof(n2))
    return false
end

""" Checks for a `StateConflict` between two `Path`s at time t """
function detect_state_conflict(path1::P1, path2::P2, t::Int) where {P1<:AbstractPath,P2<:AbstractPath}
    if detect_state_conflict(get_path_node(path1,t),get_path_node(path2,t))
        return true
    end
    return false
end

export
    detect_action_conflict

"""
    Detect an `ActionConflict` between two path nodes. Must be overridden for
    each specific path class
"""
function detect_action_conflict(n1::P1,n2::P2) where {P1<:PathNode,P2<:PathNode}
    error("detect_action_conflict(n1,n2) Not Implemented for \nn1::",
        typeof(n1),",\nn2::",typeof(n2))
    return false
end

""" Checks for an `ActionConflict` between two `Path`s at time t """
function detect_action_conflict(path1::P1, path2::P2,t::Int) where {P1<:Path,P2<:Path}
    if detect_action_conflict(get_path_node(path1,t),get_path_node(path2,t))
        return true
    end
    return false
end

export
    ConflictTable,
    get_conflicts,
    count_conflicts,
    add_conflict!,
    get_next_conflict

"""
    A lookup table to store all conflicts that have been detected
"""
@with_kw struct ConflictTable{C<:Conflict}
    state_conflicts::Dict{Tuple{Int,Int},Vector{C}} = Dict{Tuple{Int,Int},Vector{C}}()
    action_conflicts::Dict{Tuple{Int,Int},Vector{C}} = Dict{Tuple{Int,Int},Vector{C}}()
    # TODO sorted_conflict_list
end
default_conflict(table::ConflictTable{C}) where {C} = C()

""" helper for retrieving conflicts associated with agents i and j """
function get_conflicts(conflict_table::ConflictTable,i::Int,j::Int)
    if i <= j
        state_conflicts = get(conflict_table.state_conflicts, (i,j), Vector{Conflict}())
        action_conflicts = get(conflict_table.action_conflicts, (i,j), Vector{Conflict}())
    else
        @assert !haskey(conflict_table.state_conflicts, (i,j))
        @assert !haskey(conflict_table.action_conflicts, (i,j))
        return get_conflicts(conflict_table,j,i)
    end
    return state_conflicts, action_conflicts
end

export
    get_all_state_conflicts,
    get_all_action_conflicts,
    get_all_conflicts

get_all_state_conflicts(ct) = Base.Iterators.flatten((v for (k,v) in ct.state_conflicts if !isempty(v)))
get_all_action_conflicts(ct) = Base.Iterators.flatten((v for (k,v) in ct.action_conflicts if !isempty(v)))
get_all_conflicts(ct) = Base.Iterators.flatten((get_all_state_conflicts(ct),get_all_action_conflicts(ct)))

"""
    `count_conflicts(conflict_table::ConflictTable,i::Int,j::Int)`

    helper for counting the number of conflicts between agent i and agent j
"""
function count_conflicts(conflict_table::ConflictTable,i::Int,j::Int)
    state_conflicts, action_conflicts = get_conflicts(conflict_table,i,j)
    return length(state_conflicts) + length(action_conflicts)
end
function count_conflicts(conflict_table::ConflictTable,idxs1::Vector{Int},idxs2::Vector{Int})
    N = 0
    n = max(maximum(idxs1),maximum(idxs2))
    mat = sparse(zeros(Int,n,n))
    for i in idxs1
        for j in idxs2
            if i != j
                n = count_conflicts(conflict_table,i,j)
                if i < j
                    mat[i,j] = n
                else
                    mat[j,i] = n
                end
            end
        end
    end
    return sum(mat)
end
function count_conflicts(conflict_table::ConflictTable)
    N = 0
    for (k,v) in conflict_table.state_conflicts
        N += length(v)
    end
    for (k,v) in conflict_table.action_conflicts
        N += length(v)
    end
    return N
end

"""
    helper to insert conflicts into ConflictTable
"""
function add_conflict!(conflict_table::ConflictTable,c)
    @assert is_valid(c)
    if !is_valid(c)
        return
    end
    i = agent1_id(c)
    j = agent2_id(c)
    @assert i < j
    if is_state_conflict(c)
        tab = conflict_table.state_conflicts
    else
        tab = conflict_table.action_conflicts
    end
    vec = get!(tab, (i,j), valtype(conflict_table.state_conflicts)())
    insert!(vec, searchsortedfirst(vec, c), c)
    @assert issorted(vec)
    # push!(vec, c)
    conflict_table
end

"""
    `get_next_conflict(conflict_table::ConflictTable)`

    Returns the next conflict (temporally) that occurs in a conflict table
"""
function get_next_conflict(table::ConflictTable)
    conflict = default_conflict(table)
    for (k,v) in table.state_conflicts
        if ~isempty(v)
            # sort!(v)
            candidate = v[1]
            if time_of(candidate) < time_of(conflict) || !is_valid(conflict)
                conflict = candidate
            end
        end
    end
    for (k,v) in table.action_conflicts
        if ~isempty(v)
            # sort!(v)
            candidate = v[1]
            if time_of(candidate) < time_of(conflict) || !is_valid(conflict)
                conflict = candidate
            end
        end
    end
    return conflict
end

function Base.copy(c::ConflictTable)
   c_new = ConflictTable()
   for (k,v) in c.state_conflicts
       c_new.state_conflicts[k] = copy(v)
   end
   for (k,v) in c.action_conflicts
       c_new.action_conflicts[k] = copy(v)
   end
   return c_new
end

function reset_conflict_table!(conflict_table::ConflictTable,i::Int,j::Int)
    if i <= j
        conflict_table.state_conflicts[(i,j)]   =  Vector{Conflict}()
        conflict_table.action_conflicts[(i,j)]  =  Vector{Conflict}()
    else
        return reset_conflict_table!(conflict_table,j,i)
    end
    return conflict_table
end

# """
#     Returns a `ConflictTable` of all conflicts that occur in a given solution
#
#     args:
#     - conflict_table        a `ConflictTable` to store the detected conflicts
#     - paths:                a list of `Path`s, one for each individual agent
#     - idxs                  (optional) a list of agent ids for which to check
#                             collisions against all other agents
# """
function detect_conflicts(paths::Vector{P}, idxs=collect(1:length(paths)),args...) where {P <: Path}
    conflict_table = ConflictTable{SymmetricConflict{node_type(P())}}()
    detect_conflicts!(conflict_table,paths,idxs,args...)
    conflict_table
end
function detect_conflicts(solution::L, idxs=collect(1:length(get_paths(solution))),args...) where {L<:LowLevelSolution}
    conflict_table = ConflictTable{SymmetricConflict{node_type(solution)}}()
    detect_conflicts!(conflict_table,solution,idxs,args...)
    conflict_table
end

""" add detected conflicts to conflict table """
function detect_conflicts!(conflicts::ConflictTable,n1::PathNode,n2::PathNode,i::Int,j::Int,t::Int)
    if detect_state_conflict(n1,n2)
        add_conflict!(conflicts,state_conflict(i,j,n1,n2,t))
    end
    if detect_action_conflict(n1,n2)
        add_conflict!(conflicts,action_conflict(i,j,n1,n2,t))
    end
end

################################################################################
################################# Constraints ##################################
################################################################################

export
    CBSConstraint,
    get_agent_id,
    get_time_of,
    state_constraint,
    action_constraint,
    is_state_constraint,
    is_action_constraint

struct CBSConstraint{N}
    type::Symbol
    a::Int # agent ID
    v::N   # PathNode
    interval::Tuple{Int,Int} # time ID
end
CBSConstraint(T::Symbol,a::Int,v::N,t1::Int,t2=t1) where {N} = CBSConstraint(T,a,v,(t1,t2))
get_agent_id(c::CBSConstraint) = c.a
get_time_of(c::CBSConstraint) = c.interval[1]
get_constraint_interval(c::CBSConstraint) = c.interval
get_path_node(c::CBSConstraint) = c.v
get_constraint_type(c::CBSConstraint) = c.type
for op in [:get_s,:get_a,:get_sp]
    @eval $op(c::CBSConstraint) = $op(get_path_node(c))
end
Base.isless(c1::CBSConstraint,c2::CBSConstraint) = get_time_of(c1) < get_time_of(c2)
function Base.string(c::CBSConstraint)
    p = get_path_node(c)
    string(
        "$(get_constraint_type(c)):",
        " agent_id=$(get_agent_id(c)), interval=$(get_constraint_interval(c)), ",
        "$(string(get_s(p))) -- $(string(get_a(p))) -- X$(string(get_sp(p)))X"
        )
end
state_constraint(args...) = CBSConstraint(:StateConstraint,args...)
action_constraint(args...) = CBSConstraint(:ActionConstraint,args...)
is_state_constraint(c::CBSConstraint) = get_constraint_type(c) == :StateConstraint
is_action_constraint(c::CBSConstraint) = get_constraint_type(c) == :ActionConstraint

################################################################################
############################## Constraint Tables ###############################
################################################################################
export
    serialize,
    serialize_jointly,
    deserialize,
    num_states,
    num_actions

"""
    serialize(env,state,t=-1)

Encodes a state or action as an integer
"""
function serialize end
serialize(mapf::MAPF,args...) = serialize(mapf.env,args...)

function serialize_jointly end
serialize_jointly(mapf::MAPF,args...) = serialize_jointly(mapf.env,args...)

"""
    deserialize(env,idx,t=-1)

Decodes an integer encoding of a state or action of type `state_type(env)` or
`action_type(env)`
"""
function deserialize end
deserialize(mapf::MAPF,args...) = deserialize(mapf.env,args...)

"""
    num_states(env)

Returns the cardinality of the single agent state space for an environment.
    If the state and action spaces are finite and discrete, a discrete
    constraint table may be used for fast lookup.
"""
function num_states end

"""
    num_actions(env)

Returns the cardinality of the single agent state space for an environment.
    If the state and action spaces are finite and discrete, a discrete
    constraint table may be used for fast lookup.
"""
function num_actions end

export
    SpaceTrait,
    DiscreteSpace,
    ContinuousSpace,
    state_space_trait,
    action_space_trait

abstract type SpaceTrait end
struct DiscreteSpace <: SpaceTrait end
struct ContinuousSpace <: SpaceTrait end

"""
    state_space_trait(env)

Defaults to `DiscreteSpace`
"""
state_space_trait(env) = DiscreteSpace()

"""
    action_space_trait(env)

Defaults to `DiscreteSpace`
"""
action_space_trait(env) = DiscreteSpace()

state_space_trait(mapf::MAPF) = state_space_trait(mapf.env)
action_space_trait(mapf::MAPF) = action_space_trait(mapf.env)
num_states(mapf::MAPF) = num_states(mapf.env)
num_actions(mapf::MAPF) = num_actions(mapf.env)

export
    DiscreteConstraintTable,
    discrete_constraint_table

# export OffsetSparseMatrix
#
# """
#     OffsetSparseMatrix{T}
#
# Represents a sparse matrix whose dimensions may begin at non-zero integer.
# example:
# ```
# table = OffsetSparseMatrix{Bool}(10,10,5,5)
#
# ```
# """
# struct OffsetSparseMatrix{T}
#     table::SparseMatrixCSC{T,Int}
#     offset::SVector{2,Int}
#     function OffsetSparseMatrix{T}(i::Int,j::Int,start_i::Int=0,start_j::Int=0) where {T}
#         new(spzeros(T,i,j),SVector{2,Int}(start_i,start_j))
#     end
# end
# Base.getindex(m::OffsetSparseMatrix,i,j) = m.table[i .- m.offset[1],j .- m.offset[2]]
# Base.setindex!(m::OffsetSparseMatrix,val,i,j) = setindex!(m.table,val,i - m.offset[1], j - m.offset[2])
# get_offset(m::OffsetSparseMatrix) = m.offset
# get_offset(m::OffsetSparseMatrix,d::Int) = m.offset[d]
# Base.size(m::OffsetSparseMatrix) = size(m.table) .+ get_offset(m)
# function SparseArrays.findnz(m::OffsetSparseMatrix)
#     row_idxs, col_idxs, vals = findnz(m.table)
#     di = get_offset(m,1)
#     dj = get_offset(m,2)
#     map(i->i+di,row_idxs), map(j->j+dj,col_idxs), vals
# end
# Base.checkbounds(m::OffsetSparseMatrix,i,j) = all(get_offset(m) .<= (i,j) .<= size(m))

"""
    DiscreteStateTable

Stores constraints for a discrete state space
"""
struct DiscreteConstraintTable
    state_constraints::SparseMatrixCSC{Bool,Int}
    action_constraints::SparseMatrixCSC{Bool,Int}
    agent_id::Int
end
function discrete_constraint_table(n_states::Int,n_actions::Int,agent_id::Int=-1,tf::Int=n_states*4)
    DiscreteConstraintTable(
        spzeros(Bool,n_states,tf),
        spzeros(Bool,n_actions,tf),
        agent_id
        )
end
function discrete_constraint_table(n_states::Int,n_actions::Int,agent_id::Int,tf::Float64)
    @assert abs(tf - Int(round(tf))) < 0.01
    discrete_constraint_table(n_states,n_actions,agent_id,Int(round(tf)))
end
function discrete_constraint_table(env,agent_id=-1,tf=num_states(env)*4)
    @assert isa(state_space_trait(env),DiscreteSpace)
    discrete_constraint_table(num_states(env),num_actions(env),agent_id,tf)
end

export
    get_agent_id,
    state_constraints,
    action_constraints,
    sorted_state_constraints,
    sorted_action_constraints,
    add_constraint!,
    remove_constraint!,
    has_constraint,
    search_constraints

get_agent_id(c::DiscreteConstraintTable)                = c.agent_id
state_constraints(c::DiscreteConstraintTable)           = c.state_constraints
action_constraints(c::DiscreteConstraintTable)          = c.action_constraints
function state_constraints(env,table::DiscreteConstraintTable)
    row_idxs, col_idxs, _ = findnz(table.state_constraints)
    s_constraints = Vector{CBSConstraint{node_type(env)}}()
    for (idx,t) in zip(row_idxs,col_idxs)
        sp,_ = deserialize(env,state_type(env)(),idx,t)
        n = node_type(env)(sp=sp)
        push!(s_constraints,state_constraint(get_agent_id(table),n,t))
    end
    return s_constraints
end
function action_constraints(env,table::DiscreteConstraintTable)
    row_idxs, col_idxs, _ = findnz(table.action_constraints)
    constraints = Vector{CBSConstraint{node_type(env)}}()
    for (idx,t) in zip(row_idxs,col_idxs)
        a,_ = deserialize(env,action_type(env)(),idx,t)
        n = node_type(env)(a=a)
        push!(constraints,action_constraint(get_agent_id(table),n,t))
    end
    return constraints
end
sorted_state_constraints(env,table::DiscreteConstraintTable) = state_constraints(env,table)
sorted_action_constraints(env,table::DiscreteConstraintTable) = action_constraints(env,table)
# function sorted_state_constraints(env,table::DiscreteConstraintTable)
#     row_idxs, col_idxs, _ = findnz(table.state_constraints)
#     s_constraints = Vector{CBSConstraint{node_type(env)}}()
#     for (idx,t) in zip(row_idxs,col_idxs)
#         sp,_ = deserialize(env,state_type(env)(),idx,t)
#         n = node_type(env)(sp=sp)
#         push!(s_constraints,state_constraint(get_agent_id(table),n,t))
#     end
#     return s_constraints
# end
# function sorted_action_constraints(env,table::DiscreteConstraintTable)
#     row_idxs, col_idxs, _ = findnz(table.action_constraints)
#     constraints = Vector{CBSConstraint{node_type(env)}}()
#     for (idx,t) in zip(row_idxs,col_idxs)
#         a,_ = deserialize(env,action_type(env)(),idx,t)
#         n = node_type(env)(a=a)
#         push!(constraints,action_constraint(get_agent_id(table),n,t))
#     end
#     return constraints
# end
"""
    search_constraints(env,table,n::PathNode)

    Returns all `CBSConstraint`s and `CBSConstraint`s that match `n`,
    regardless of time.
"""
function search_constraints(env,table::DiscreteConstraintTable,n::N) where {N<:PathNode}
    idx,_ = serialize(env,get_sp(n))
    row_idxs, col_idxs, _ = findnz(table.state_constraints)
    s_constraints = Vector{CBSConstraint{node_type(env)}}()
    for (i,(r,t)) in enumerate(zip(row_idxs,col_idxs))
        if r == idx
            push!(s_constraints,state_constraint(get_agent_id(table),n,t))
        end
    end
    idx,_ = serialize(env,get_a(n))
    row_idxs, col_idxs, _ = findnz(table.action_constraints)
    a_constraints = Vector{CBSConstraint{node_type(env)}}()
    for (i,(r,t)) in enumerate(zip(row_idxs,col_idxs))
        if r == idx
            push!(a_constraints,action_constraint(get_agent_id(table),n,t))
        end
    end
    return s_constraints, a_constraints
end

"""
    Sets a `CBSConstraint` value in a DiscreteConstraintTable
"""
function set_constraint!(env,table::DiscreteConstraintTable,c::CBSConstraint,val,check=false)
    @assert get_agent_id(table) == get_agent_id(c)
    t1,t2 = get_constraint_interval(c)
    if is_state_constraint(c)
        idx,t1 = serialize(env,get_sp(get_path_node(c)),t1)
        _,t2 = serialize(env,get_sp(get_path_node(c)),t2)
        if check
            @assert all(table.state_constraints[idx,t1:t2] .!= val) "constraint $(string(c)) is $val in table, but should be $(!val)"
        end
        table.state_constraints[idx,t1:t2] .= val
    else
        idx,t1 = serialize(env,get_a(get_path_node(c)),t1)
        _,t2 = serialize(env,get_a(get_path_node(c)),t2)
        if check
            @assert all(table.action_constraints[idx,t1:t2] .!= val) "constraint $(string(c)) is $val in table, but should be $(!val)"
        end
        table.action_constraints[idx,t1:t2] .= val
    end
    return table
end

""" Adds a `CBSConstraint` to a DiscreteConstraintTable """
add_constraint!(env,table,c,check=true) =  set_constraint!(env,table,c,true,check)

""" Removes a `CBSConstraint` to a DiscreteConstraintTable """
remove_constraint!(env,table,c,check=false) = set_constraint!(env,table,c,false,check)

function check_constraint_bounds(table,idx,t)
    if !checkbounds(Bool,table,idx,t)
        throw(SolverException("BoundsError: Trying to check constraint at $idx,$t, but size(table) = $(size(table))"))
    end
end

"""
    has_constraint(env,table,c::CBSConstraint)
"""
function has_constraint(env,table::DiscreteConstraintTable,c::CBSConstraint)
    @assert get_agent_id(table) == get_agent_id(c)
    if is_state_constraint(c)
        idx,t = serialize(env,get_sp(get_path_node(c)),get_time_of(c))
        check_constraint_bounds(table.state_constraints,idx,t)
        return table.state_constraints[idx,t]
    else
        idx,t = serialize(env,get_a(get_path_node(c)),get_time_of(c))
        check_constraint_bounds(table.action_constraints,idx,t)
        return table.action_constraints[idx,t]
    end
end

# """
#     constraint dictionary for fast constraint lookup within a_star!
# """
# @with_kw struct ConstraintTable{N}
#     # Sets
#     state_constraints::Set{CBSConstraint{N}} = Set{CBSConstraint{N}}()
#     action_constraints::Set{CBSConstraint{N}} = Set{CBSConstraint{N}}()
#     # Vectors
#     sorted_state_constraints::Vector{CBSConstraint{N}} = Vector{CBSConstraint{N}}()
#     sorted_action_constraints::Vector{CBSConstraint{N}} = Vector{CBSConstraint{N}}()
#     agent_id::Int = -1 # agent_id
# end
# get_agent_id(c::ConstraintTable) = c.agent_id
# state_constraints(c::ConstraintTable) = c.state_constraints
# state_constraints(env,c::ConstraintTable) = state_constraints(c)
# action_constraints(c::ConstraintTable) = c.action_constraints
# action_constraints(env,c::ConstraintTable) = action_constraints(c)
# sorted_state_constraints(env,c::ConstraintTable) = c.sorted_state_constraints
# sorted_action_constraints(env,c::ConstraintTable) = c.sorted_action_constraints
# function search_constraints(env,table::ConstraintTable,n::N) where {N<:PathNode}
#     idx,_ = serialize(env,get_sp(n))
#     s_constraints = Vector{CBSConstraint{node_type(env)}}()
#     for constraint in sorted_state_constraints(env,table)
#         sp = get_sp(get_path_node(constraint))
#         idxp, _ = serialize(env,sp)
#         if idxp == idx
#             push!(s_constraints,constraint)
#         end
#     end
#     idx,_ = serialize(env,get_a(n))
#     a_constraints = Vector{CBSConstraint{node_type(env)}}()
#     for constraint in sorted_action_constraints(env,table)
#         a = get_a(get_path_node(constraint))
#         idxp, _ = serialize(env,a)
#         if idxp == idx
#             push!(a_constraints,constraint)
#         end
#     end
#     return s_constraints, a_constraints
# end
#
# """
#     Adds a `CBSConstraint` to a ConstraintTable
# """
# function add_constraint!(env,table::ConstraintTable,c::CBSConstraint)
#     @assert get_agent_id(table) == get_agent_id(c)
#     if is_state_constraint(c)
#         push!(table.state_constraints, c)
#         insert_to_sorted_array!(table.sorted_state_constraints, c)
#     else
#         push!(table.action_constraints, c)
#         insert_to_sorted_array!(table.sorted_action_constraints, c)
#     end
# end
#
# function has_constraint(env,table::ConstraintTable,c::CBSConstraint)
#     @assert get_agent_id(table) == get_agent_id(c)
#     if is_state_constraint(c)
#         return (c in table.state_constraints)
#     else
#         return (c in table.action_constraints)
#     end
# end

export
    ConstraintTreeNode,
    solution_type,
    initialize_root_node,
    initialize_child_search_node,
    get_constraints,
    violates_constraints,
    generate_constraints_from_conflict

"""
    A node of a constraint tree. Each node has a set of constraints, a candidate
    solution (set of robot paths), and a cost
"""
@with_kw struct ConstraintTreeNode{S,C,D} #,E<:AbstractLowLevelEnv{S,A}} # CBS High Level Node
    solution        ::S = S()
    # maps agent_id to the set of constraints involving that agent
    constraints     ::C = Dict{Int,DiscreteConstraintTable}() #{node_type(solution)}}()
    # maintains a list of all conflicts
    conflict_table  ::D = ConflictTable{SymmetricConflict{node_type(solution)}}()
    # index of parent node
    parent          ::Int = -1
    # indices of two child nodes
    children        ::Tuple{Int,Int} = (-1,-1)
    # unique id
    id              ::Int = -1
    # trace
    trace           ::Vector{Int} = Int[]
end
for op in [
    :cost_type,:state_type,:action_type,:path_type,:get_cost,:get_paths,
    :get_path_costs,:set_cost!,:set_solution_path!,:set_path_cost!,
    ]
    @eval $op(node::ConstraintTreeNode,args...) = $op(node.solution,args...)
end
solution_type(node::ConstraintTreeNode{S,C,D}) where {S,C,D} = S
constraint_table_type(node::ConstraintTreeNode) = valtype(node.constraints)
function set_trace!(node::C,parent::C,i) where {C<:ConstraintTreeNode}
    append!(node.trace,parent.trace)
    push!(node.trace,i)
    node
end

"""
    `initialize_root_node`

    Construct an empty `ConstraintTreeNode` from a `AbstractMAPF` instance
"""
function initialize_root_node(mapf::AbstractMAPF,solution=get_initial_solution(mapf))
    ConstraintTreeNode(
        solution    = solution,
        constraints = Dict(
            i=>discrete_constraint_table(mapf,i) for i in 1:num_agents(mapf)
            ),
        id = 1)
end
function initialize_root_node(solver,mapf::AbstractMAPF,solution=get_initial_solution(mapf))
    initialize_root_node(mapf,solution)
end

"""
    `initialize_child_search_node(parent_node::ConstraintTreeNode)`

    Initialize a new `ConstraintTreeNode` with the same `solution` and
    `constraints` as the parent node
"""
function initialize_child_search_node(parent_node::N, solution=copy(parent_node.solution)) where {N<:ConstraintTreeNode}
    N(
        solution        = solution,
        constraints     = deepcopy(parent_node.constraints),
        conflict_table  = deepcopy(parent_node.conflict_table),
        parent          = parent_node.id
    )
end
function initialize_child_search_node(mapf::AbstractMAPF,parent_node::N, solution=copy(parent_node.solution)) where {N<:ConstraintTreeNode}
    initialize_child_search_node(parent_node, solution)
end
function initialize_child_search_node(solver, mapf::AbstractMAPF,parent_node::N, solution=copy(parent_node.solution)) where {N<:ConstraintTreeNode}
    initialize_child_search_node(mapf, parent_node, solution)
end

"""
    retrieve constraints corresponding to this node and this path
"""
function get_constraints(node::N, path_id::Int) where {N<:ConstraintTreeNode}
    @assert haskey(node.constraints,path_id) "path_id = $path_id"
    return node.constraints[path_id]
    # return get(node.constraints, path_id, valtype(node.constraints)())
end

"""
    adds a `CBSConstraint` to a ConstraintTreeNode
"""
function add_constraint!(env,node::N,c::CBSConstraint) where {N<:ConstraintTreeNode}
    add_constraint!(env, get_constraints(node, get_agent_id(c)), c)
    return true
end

function detect_conflicts!(node::ConstraintTreeNode, args...)
    detect_conflicts!(node.conflict_table,node.solution,args...)
end
for op in [:count_conflicts,:get_next_conflict,:reset_conflict_table!,:get_conflicts,
    :get_all_state_conflicts,:get_all_action_conflicts,:get_all_conflicts]
    @eval $op(node::ConstraintTreeNode,args...) = $op(node.conflict_table,args...)
end

for op in [:state_constraints, :action_constraints,:sorted_state_constraints, :sorted_action_constraints,]
    @eval $op(env,node::ConstraintTreeNode,idx) = $op(env,get_constraints(node,idx))
end
for op in [:state_constraints, :action_constraints,:sorted_state_constraints, :sorted_action_constraints,]
    @eval $op(env,node::ConstraintTreeNode) = begin
        vcat(
            map(k->collect($op(env,get_constraints(node,k))),
            collect(keys(node.constraints)))...
            )
    end
end

"""
    generates a Vector of (State or Action) Constraints from a conflict
"""
function generate_constraints_from_conflict(c::Conflict)
    constraints = Vector{CBSConstraint}()
    if is_state_conflict(c)
        push!(constraints, state_constraint(
            agent1_id(c),
            node1(c),
            time_of(c)
        ))
        push!(constraints, state_constraint(
            agent2_id(c),
            node2(c),
            time_of(c)
        ))
    else
        push!(constraints, action_constraint(
            agent1_id(c),
            node1(c),
            time_of(c)
        ))
        push!(constraints, action_constraint(
            agent2_id(c),
            node2(c),
            time_of(c)
        ))
    end
    return constraints
end

################################################################################
############################## Reservation Table ###############################
################################################################################
export ResourceReservation

"""
    ResourceReservation

`r::ResourceReservation` encodes a that resource `r.resource` is reserved by
agent `r.agent_id` over time interval `r.interval`.
"""
struct ResourceReservation{T<:Real}
    resource_id::Int
    agent_id::Int
    interval::Tuple{T,T}
end
resource_id(r::ResourceReservation)     = r.resource_id
agent_id(r::ResourceReservation)        = r.agent_id
interval(r::ResourceReservation)        = r.interval
start_time(interval::Tuple{T,T}) where {T} = interval[1]
finish_time(interval::Tuple{T,T}) where {T} = interval[2]
start_time(r::ResourceReservation)      = start_time(interval(r))
finish_time(r::ResourceReservation)     = finish_time(interval(r))
function assert_valid(r::ResourceReservation)
    @assert resource_id(r) > 0
    @assert agent_id(r) > 0
    @assert start_time(r) < finish_time(r)
end

export ReservationTable

"""
    ReservationTable

Data structure for reserving resources over a time interval. The table stores a
vector of reservations for each resource. When a new reservation is added to the
table, it is inserted into the reservation vector associated to the requested
resource.
"""
struct ReservationTable{T}
    reservations::SparseVector{Vector{ResourceReservation{T}},Int}
end
time_type(table::ReservationTable{T}) where {T} = T
SparseArrays.SparseVector{Tv,Ti}(n::Int) where {Tv,Ti} = SparseVector{Tv,Ti}(n,Ti[],Tv[])
Base.zero(::Type{Vector{R}}) where {R<:ResourceReservation} = Vector{R}()
Base.iszero(::Vector{R}) where {R<:ResourceReservation} = false
ReservationTable{T}(n::Int) where {T} = ReservationTable{T}(
    SparseVector{Vector{ResourceReservation{T}},Int}(n)
)
# ReservationTable{T}(env) where {T} = ReservationTable{T}(num_states(env)+num_actions(env))
function assert_valid(table::ReservationTable)
    idxs,vals = findnz(table.reservations)
    if length(idxs) > 0
        for (idx,vec) in zip(idxs,vals)
            t = time_type(table)(0)
            for reservation in vec
                @assert start_time(reservation) >= t
                @assert is_valid(reservation)
                # @assert resource_id(reservation) <= length(table.reservations)
                @assert resource_id(reservation) == idx
                t = finish_time(reservation)
            end
        end
    end
end

function spanning_range(vec::Vector{R},res::R) where {R<:ResourceReservation}
    start_idx = searchsorted(map(finish_time,vec),start_time(res))
    stop_idx = searchsorted(map(start_time,vec),finish_time(res))
    i = min(start_idx.start,start_idx.stop) + 1
    j = max(stop_idx.start,stop_idx.stop) - 1
    return i:j
end

export create_reservations

"""
    create_reservation(env,s,a,sp)

Must be overriden for environment env and the relevant state / action types.
"""
function create_reservations end

export
    reserve!,
    is_reserved

"""
    reserve!(table,reservation)

Attempts to add a reservation to the table. If the reservation conflicts with
an existing reservation, does nothing and returns false. If successful, returns
true.
"""
function reserve!(vec::Vector{R},res::R) where {R<:ResourceReservation}
    if length(vec) > 0
        idx = spanning_range(vec,res)
        if idx.start > idx.stop
            insert!(vec,idx.start,res)
        else
            return false # already reserved
        end
    else
        push!(vec,res)
    end
    return true
end
function reserve!(table::ReservationTable,res::ResourceReservation)
    @assert is_valid(res)
    @assert resource_id(res) <= length(table.reservations)
    vec = table.reservations[resource_id(res)]
    if reserve!(vec,res)
        table.reservations[resource_id(res)] = vec
        return true
    end
    return false
end
function reserve!(table::ReservationTable,env,s,a,sp,t=-1)
    valid = true
    for res in create_reservations(env,s,a,sp,t)
        valid &= reserve!(table,res)
    end
    return valid
end

function is_reserved(vec::Vector{R},res::R) where {R<:ResourceReservation}
    if length(vec) > 0
        idx = spanning_range(vec,res)
        if idx.start <= idx.stop
            return true # already reserved
        end
    end
    return false
end
function is_reserved(table::ReservationTable,res::ResourceReservation)
    @assert is_valid(res) string(res)
    @assert resource_id(res) <= length(table.reservations)
    is_reserved(table.reservations[resource_id(res)],res)
end
function is_reserved(table::ReservationTable,env,s,a,sp,t=-1)
    for res in create_reservations(env,s,a,sp,t)
        if is_reserved(table,res)
            return true
        end
    end
    return false
end

export reserved_by

"""
    reserved_by

Returns the IDs of agents who have reserved a resource within a specific time
window.
"""
function reserved_by(vec::Vector{R},res::R) where {R<:ResourceReservation}
    if length(vec) > 0
        idx = spanning_range(vec,res)
        if idx.start <= idx.stop
            # @show interval(res), idx, map(interval,vec)
            # @show map(interval,vec[idx])
            return Set{Int}(map(agent_id,vec[idx]))
        end
    end
    return Set{Int}()
end
function reserved_by(table::ReservationTable,res::ResourceReservation)
    @assert is_valid(res)
    @assert resource_id(res) <= length(table.reservations)
    reserved_by(table.reservations[resource_id(res)],res)
end
function reserved_by(table::ReservationTable,env,s,a,sp,t=-1)
    union(map(res->reserved_by(table,res),create_reservations(env,s,a,sp,t))...)
end

export is_available

"""
    is_available

Returns false if the proposed reservation is not available to any of the agent_ids
"""
function is_available(table::ReservationTable,env,s,a,sp)
    agents = reserved_by(table,env,s,a,sp)
    if isempty(setdiff(agents,get_agent_id(env)))
        return true
    end
    return false
end

function reset_reservations!(table::ReservationTable)
    empty!(table.reservations.nzind)
    empty!(table.reservations.nzval)
    table
end

################################################################################
################################ Fat Path Tools ################################
################################################################################

# """
#     `get_fat_path(G,D,start_vtx,goal_vtx)`
#
#     returns a fat path through `G` from `start_vtx` to `goal_vtx`. Each set
#     of vertices in the fat path contains all vertices with distance d1 from
#     start_vtx and distance d2 to goal_vtx, where d1+d2 == the length of the
#     shortest path(s) from `start_vtx` to `goal_vtx`
#
#     G is a graph, D is the distance matrix
# """
# function get_fat_path(G,D,start_vtx::Int,goal_vtx::Int)
#     fat_path = Vector{Set{Int}}([Set{Int}(start_vtx)])
#     for i in 1:D[start_vtx,goal_vtx]
#         next_set = Set{Int}()
#         for src_vtx in fat_path[end]
#             for dst_vtx in outneighbors(G,src_vtx)
#                 if D[dst_vtx,goal_vtx] <= D[src_vtx,goal_vtx] - 1
#                     push!(next_set, dst_vtx)
#                 end
#             end
#         end
#         push!(fat_path, next_set)
#     end
#     fat_path
# end
#
# """
#     `add_fat_path_to_table(CAT,fat_path)`
# """
# function add_fat_path_to_table!(CAT,fat_path,t0=0)
#     for t in 1:length(fat_path)
#         idxs = collect(fat_path[t])
#         if t+t0 > 0
#             CAT[idxs,t+t0] .+= 1.0/length(idxs)
#         end
#     end
# end
#
# """
#     `populate_soft_lookup_table!(CAT,start_times,start_vtxs,goal_vtxs)`
# """
# function populate_soft_lookup_table!(CAT,G,D,start_vtxs,goal_vtxs,start_times=zeros(Int,length(start_vtxs)))
#     for (s,t,g) in zip(start_vtxs,start_times,goal_vtxs)
#         fat_path = get_fat_path(G,D,s,g)
#         add_fat_path_to_table!(CAT,t0,fat_path)
#     end
#     CAT
# end

const FatPath{N} = Vector{Vector{N}}

export
    FatPathCostModel,
    FlatFPCost,
    NormalizedFPCost

abstract type FatPathCostModel end
struct FlatFPCost <: FatPathCostModel end
struct NormalizedFPCost <: FatPathCostModel end

"""
    get_fat_path_cost(model,nodes)

Returns a scalar cost value depending on `typeof(model)` and `length(nodes)`.

```
get_fat_path_cost(m::FlatFPCost,nodes) = 1.0
get_fat_path_cost(m::NormalizedFPCost,nodes) = 1.0/length(nodes)
```
"""
get_fat_path_cost(m::FlatFPCost,nodes) = 1.0
get_fat_path_cost(m::NormalizedFPCost,nodes) = 1.0/length(nodes)

export get_mdd_graph

"""
    get_mdd_graph(env,s,threshold,cost=get_initial_cost(env))

Construct a multi-level decision diagram (MDD) graph.
"""
function get_mdd_graph(env,s,threshold,cost=get_initial_cost(env))
    # nodes = Vector{node_type(env)}()
    fat_path = NEGraph{DiGraph,cost_type(env),action_type(env),state_type(env)}()
    add_node!(fat_path,cost,s)
    frontier = PriorityQueue{state_type(env),typeof(cost)}()
    explored = Set{state_type(env)}()
    enqueue!(frontier,s=>cost)
    while !isempty(frontier)
        s,cost = dequeue_pair!(frontier)
        push!(explored,s)
        for a in get_possible_actions(env,s)
            sp = get_next_state(env,s,a)
            if has_vertex(fat_path,sp)
                add_edge!(fat_path,s,sp,a)
                continue
            end
            if sp in explored || has_vertex(fat_path,sp)
                continue
            end
            c = accumulate_cost(env,cost,get_transition_cost(env,s,a,sp))
            h = compute_heuristic_cost(env,c,sp)
            if h <= threshold
                add_node!(fat_path,c,sp)
                add_edge!(fat_path,s,sp,a)
                enqueue!(frontier, sp=>c)
            end
        end
    end
    fat_path
end

"""
    get_level_set_nodes(env,s,threshold,cost=get_initial_cost(env))

Returns a vector of `PathNode`s, where the heuristic cost (according to `env`)
of each node falls below `threshold`.
"""
function get_level_set_nodes(env,s,threshold,cost=get_initial_cost(env))
    # nodes = Vector{node_type(env)}()
    fat_path = FatPath{node_type(env)}()
    # frontier = PriorityQueue{state_type(env),typeof(cost)}()
    next_frontier = PriorityQueue{state_type(env),typeof(cost)}()
    explored = Set{state_type(env)}()
    # enqueue!(frontier,s=>cost)
    enqueue!(next_frontier,s=>cost)
    while !isempty(next_frontier)
        push!(fat_path,Vector{node_type(env)}())
        frontier = next_frontier
        next_frontier = PriorityQueue{state_type(env),typeof(cost)}()
        while !isempty(frontier)
            s,cost = dequeue_pair!(frontier)
            push!(explored,s)
            for a in get_possible_actions(env,s)
                sp = get_next_state(env,s,a)
                if sp in explored || haskey(next_frontier,sp)
                    continue
                end
                c = accumulate_cost(env,cost,get_transition_cost(env,s,a,sp))
                h = compute_heuristic_cost(env,c,sp)
                if h <= threshold
                    # push!(nodes,PathNode(s,a,sp))
                    push!(fat_path[end],PathNode(s,a,sp))
                    # enqueue!(frontier, sp=>c)
                    enqueue!(next_frontier, sp=>c)
                end
            end
        end
    end
    # nodes
    fat_path
end
function Base.empty!(sparr::SparseMatrixCSC)
    empty!(sparr.nzval)
    empty!(sparr.rowval)
    sparr.colptr .= 1
    return sparr
end
function Base.empty!(table::SoftConflictTable)
    empty!(table.CAT)
    for p in table.paths
        empty!(p)
    end
    return table
end

"""
    update_conflict_table!(table,nodes)

Updates a conflict table with a set of nodes.
"""
function update_fat_path_conflict_table!(model::M,table::AbstractMatrix,env::E,fat_path) where {M<:FatPathCostModel,E}
# function update_fat_path_conflict_table!(table::AbstractMatrix,env::E,nodes::Vector{N}) where {E,N<:PathNode}
    for nodes in fat_path
        cost = get_fat_path_cost(model,nodes)
        for n in nodes
            idx, t = serialize_jointly(env,get_a(n),get_t(get_sp(n)))
            table[idx,t] += cost
            idx, t = serialize_jointly(env,get_sp(n))
            table[idx,t] += cost
        end
    end
    return table
end
function update_fat_path_conflict_table!(model::M,table::SoftConflictTable,idx::Int,env::E,fat_path) where {M<:FatPathCostModel,E}
    update_fat_path_conflict_table!(model,table.paths[idx],env,fat_path)
    table.CAT .+= table.paths[idx]
    return table
end
# function update_fat_path_conflict_table!(table::Union{SoftConflictTable,AbstractMatrix},args...)
#     update_fat_path_conflict_table!(FlatFPCost(),table,args...)
# end
function clear_fat_path!(table::SoftConflictTable,idx::Int)
    table.CAT .-= table.paths[idx]
    empty!(table.paths[idx])
    table
end
reset_path!(table::SoftConflictTable,idx::Int) = clear_fat_path!(table,idx)
function SoftConflictTable(mapf::AbstractMAPF)
    # sets up SoftConflictTable for use with Serialized states
    N = num_states(mapf)+num_actions(mapf)
    T = num_states(mapf)*4
    return SoftConflictTable(
        paths = map(i->spzeros(Float64,N,T),1:num_agents(mapf)),
        CAT = spzeros(Float64,N,T),
    )
end
get_fat_path_threshold_cost(env,s,cost=get_initial_cost(env)) = compute_heuristic_cost(env,cost,s)
function populate_fat_path_table!(table::SoftConflictTable,mapf::AbstractMAPF,model=FlatFPCost())
    node = initialize_root_node(mapf)
    for i in 1:num_agents(mapf)
        env = build_env(mapf,node,i)
        s = get_start(mapf,i)
        threshold = get_fat_path_threshold_cost(env,s)
        fat_path = get_level_set_nodes(env,s,threshold)
        update_fat_path_conflict_table!(model,table,i,mapf,fat_path)
    end
    return table
end

function init_fat_path_mapf(mapf,model=FlatFPCost())
    table = SoftConflictTable(mapf)
    CRCBS.populate_fat_path_table!(table,mapf,model)
    mapf = MAPF(
        base_env_type(mapf)(
            graph = mapf.env.graph,
            cost_model = construct_composite_cost_model(
                SumOfTravelTime(),
                SoftConflictCost(table)
            ),
            heuristic = construct_composite_heuristic(
                PerfectHeuristic((v1,v2)->get_dist_matrix(mapf.env.graph)[v1,v2]),
                NullHeuristic()
            )
        ),
        mapf.starts,
        mapf.goals
    )
end


text:
using
  FourierFlows,
  Statistics,
  Random,
  FFTW,
  Test

import # use 'import' rather than 'using' for submodules to keep namespace clean
  GeophysicalFlows.TwoDTurb,
  GeophysicalFlows.BarotropicQG,
  GeophysicalFlows.BarotropicQGQL,
  GeophysicalFlows.MultilayerQG

using FourierFlows: parsevalsum, xmoment, ymoment
using GeophysicalFlows: lambdipole, peakedisotropicspectrum

# the devices on which tests will run
devices = (CPU(),)
@has_cuda devices = (CPU(), GPU())
@has_cuda using CuArrays

const rtol_lambdipole = 1e-2 # tolerance for lamb dipole tests
const rtol_multilayerqg = 1e-13 # tolerance for multilayerqg forcing tests
const rtol_twodturb = 1e-13 # tolerance for twodturb forcing tests

"Get the CFL number, assuming a uniform grid with `dx=dy`."
cfl(u, v, dt, dx) = maximum([maximum(abs.(u)), maximum(abs.(v))]*dt/dx)
cfl(prob) = cfl(prob.vars.u, prob.vars.v, prob.clock.dt, prob.grid.dx)

# Run tests
testtime = @elapsed begin

for dev in devices

  println("testing on "*string(typeof(dev)))

  @testset "Utils" begin
    include("test_utils.jl")

    @test testpeakedisotropicspectrum(dev)
    @test_throws ErrorException("the domain is not square") testpeakedisotropicspectrum_rectangledomain()
  end

  @testset "TwoDTurb" begin
    include("test_twodturb.jl")

    @test test_twodturb_advection(0.0005, "ForwardEuler", dev)
    @test test_twodturb_lambdipole(256, 1e-3, dev)
    @test test_twodturb_stochasticforcingbudgets(dev)
    @test test_twodturb_deterministicforcingbudgets(dev)
    @test test_twodturb_energyenstrophy(dev)
    @test test_twodturb_problemtype(Float32)
    @test TwoDTurb.nothingfunction() == nothing
  end

end

println("rest of tests only on CPU")

@testset "BarotropicQG" begin
  include("test_barotropicqg.jl")

  @test test_bqg_rossbywave("ETDRK4", 1e-2, 20)
  @test test_bqg_rossbywave("FilteredETDRK4", 1e-2, 20)
  @test test_bqg_rossbywave("RK4", 1e-2, 20)
  @test test_bqg_rossbywave("FilteredRK4", 1e-2, 20)
  @test test_bqg_rossbywave("AB3", 1e-3, 200)
  @test test_bqg_rossbywave("FilteredAB3", 1e-3, 200)
  @test test_bqg_rossbywave("ForwardEuler", 1e-4, 2000)
  @test test_bqg_rossbywave("FilteredForwardEuler", 1e-4, 2000)
  @test test_bqg_stochasticforcingbudgets()
  @test test_bqg_deterministicforcingbudgets()
  @test test_bqg_advection(0.0005, "ForwardEuler")
  @test test_bqg_formstress(0.01, "ForwardEuler")
  @test test_bqg_energyenstrophy()
  @test test_bqg_meanenergyenstrophy()
  @test test_bqg_problemtype(Float32)
  @test BarotropicQG.nothingfunction() == nothing
end

@testset "BarotropicQGQL" begin
  include("test_barotropicqgql.jl")

  @test test_bqgql_rossbywave("ETDRK4", 1e-2, 20)
  @test test_bqgql_rossbywave("FilteredETDRK4", 1e-2, 20)
  @test test_bqgql_rossbywave("RK4", 1e-2, 20)
  @test test_bqgql_rossbywave("FilteredRK4", 1e-2, 20)
  @test test_bqgql_rossbywave("AB3", 1e-3, 200)
  @test test_bqgql_rossbywave("FilteredAB3", 1e-3, 200)
  @test test_bqgql_rossbywave("ForwardEuler", 1e-4, 2000)
  @test test_bqgql_rossbywave("FilteredForwardEuler", 1e-4, 2000)
  @test test_bqgql_deterministicforcingbudgets()
  @test test_bqgql_stochasticforcingbudgets()
  @test test_bqgql_advection(0.0005, "ForwardEuler")
  @test test_bqgql_energyenstrophy()
  @test test_bqgql_problemtype(Float32)
  @test BarotropicQGQL.nothingfunction() == nothing
end

@testset "MultilayerQG" begin
  include("test_multilayerqg.jl")

  @test test_pvtofromstreamfunction_2layer()
  @test test_pvtofromstreamfunction_3layer()
  @test test_mqg_nonlinearadvection(0.001, "ForwardEuler")
  @test test_mqg_linearadvection(0.001, "ForwardEuler")
  @test test_mqg_energies()
  @test test_mqg_fluxes()
  @test test_mqg_setqsetpsi()
  @test test_mqg_paramsconstructor()
  @test test_mqg_problemtype(Float32)
  @test MultilayerQG.nothingfunction() == nothing
end

end # time

println("Total test time: ", testtime)


text:
# %% imports

include("../../../Modules/CMAES/cmaes.jl")
include("EI_sim.jl")
include("../../../Modules/save_param.jl")

# %%

function optim()
    cfg = YAML.load(open("Julia/CartPole/LIF_base/cfg_cmaes.yml"))
    arch = cfg["arch"]

    N_alpha = arch[1]*4
    N_w = sum([arch[i]*(arch[i-1]-(div(arch[i-1],4))) for i in 2:length(arch)]) +1
    N = N_alpha + N_w

    best = Array{Float64}[]
    for i in 1:20
        push!(best,[])
    end
    best_fit = [-1.0 for i in 1:20]
    error = false

    # Create initial point (optional)
    results = load_param("Julia/CartPole/LIF_base/results_EI888.jld")
    genes_init = results["weights"][19]

    lambda = 4+floor(Int64,3*log(N))
    mu = floor(Int64,lambda/2)
    c = CMAES(genes_init, N=N, μ=mu, λ=lambda , τ=sqrt(N), τ_c=N^2, τ_σ=sqrt(N))
    for i in 1:500
        @time step!(c)
        bestind = argmin(c.F_λ)
        maxfit = -c.F_λ[bestind]
        println(i," ", maxfit, " (current best = $(maximum(best_fit)))")
        if maxfit > best_fit[1]
            best_fit[1] = maxfit
            best[1] = copy(c.offspring[bestind])
            idx = sortperm(best_fit)
            best_fit = best_fit[idx]
            best = best[idx]
        end
        if sum(best_fit) >= 4000
            break
        end
        if i > 20 && best_fit[end] < 190
            error = true
            break
        end
        if length(best[1]) > 0 && i%20 == 0
            save_param(best_fit,best)
        end
    end
    if best_fit[end] < 195
        error = true
    end
    return best_fit, best, error
end

# %% run sim

for opt in 1:20
    best_fit, best, error = optim()
    if error==false
        break
    end
end

max_stars_repo_name: SuReLI/RL-STDP

max_issues_repo_name: SuReLI/RL-STDP

max_forks_repo_name: SuReLI/RL-STDP


text:
function clear_rows!(cur_player::AbstractPlayer, cleared_rows::Vector{Int})
  cur_grid = cur_player.grid

  cur_js = """
    var beg_row, end_row, work_row;
  """

  for (cur_index, cur_row) in enumerate(cleared_rows)
    next_row =
      ( cur_index == length(cleared_rows) ) ?
      ( cur_grid.height + 1 ) :
      cleared_rows[cur_index+1]

    cur_range = cur_row+1:next_row-1

    cur_grid.table[cur_range.-cur_index,:] =
      cur_grid.table[cur_range,:]

    cur_js *= """
      \$(".cs-main-area .cs-row-$(cur_row)").empty();
    """

    for tmp_row in cur_range
      cur_js *= """
        beg_row = "cs-main-area .cs-row-$(tmp_row)";
        end_row = "cs-main-area .cs-row-$(tmp_row-cur_index)";

        \$("." + beg_row).children().appendTo("." + end_row);
        \$("." + beg_row).empty();
      """
    end
  end

  end_index = cur_grid.height
  row_count = length(cleared_rows)

  cur_grid.height -= row_count
  cur_player.lines += row_count

  lines_per_level = 10

  if cur_player.lines >= ( lines_per_level * cur_player.level )
    cur_player.level = 1 + Int(
      floor(
        cur_player.lines /
        lines_per_level
      )
    )

    if cur_player.level <= max_level
      cur_js *= """
        \$(".js-level-text").text("Level $(cur_player.level)");
      """

      if is_repl
        cur_string = []
        push!(cur_string, crayon_dict["grey"])
        push!(cur_string, "\x1b[$(8);$(11)H")
        push!(cur_string, "   $(lpad(cur_player.level, 2, "0"))   ")
        push!(cur_string, inv(crayon_dict["grey"]))
        push!(cur_string, "\x1b[u")
        print(cur_string...)
      end
    end
  end

  cur_range = ( -(row_count-1):0 ) .+ end_index

  cur_grid.table[cur_range, :] .= ""

  cur_string = "	" ^ cur_grid.cols

  for tmp_row in cur_range
    cur_js *= """
      work_row = "cs-main-area .cs-row-$(tmp_row)";

      \$("$(cur_string)").appendTo("." + work_row);
    """
  end

  cur_js
end


text:
export DialogState
export ElicitIntent
export ConfirmIntent
export ElicitSlot
export Fulfilled
export ReadyForFulfillment
export Failed

"""
The current state of the user interaction.
See https://docs.aws.amazon.com/lex/latest/dg/API_runtime_PostText.html#lex-runtime_PostText-response-dialogState
"""
abstract type DialogState end

"Lex assumes this state when it is unaware of the user's intent"
struct ElicitIntent <: DialogState end

"""
Lex assumes this state when attempting to confirm something from the user.
e.g. "blah blah blah, right?"
"""
struct ConfirmIntent <: DialogState end

"Lex assumes this state when asking the user for a slot value."
struct ElicitSlot <: DialogState end

"""
Lex assumes this state when a configured Lambda function has already fulfilled
the intent.
"""
struct Fulfilled <: DialogState end

"Lex assumes this state when the application must fulfill the intent."
struct ReadyForFulfillment <: DialogState end

"Lex assumes this state when it cannot continue after retrying."
struct Failed <: DialogState end

const DialogStateNames = Dict{String, DialogState}(
    "ElicitIntent" => ElicitIntent(),
    "ConfirmIntent" => ConfirmIntent(),
    "ElicitSlot" => ElicitSlot(),
    "Fulfilled" => Fulfilled(),
    "ReadyForFulfillment" => ReadyForFulfillment(),
    "Failed" => Failed()
)


text:
# The output of the SoS method on a polynomial program

type SoSSolution
    prog :: Program
    degree :: Int64
    primalobj :: Float64
    dualobj :: Float64
    moments :: Dict{SoSMonom,Float64}
    primalmatrix :: Array{Float64,2}
    dualmatrix :: Array{Float64,2}
    status :: Symbol # :Normal, :Infeasible, :Unbounded, :Warning, :Error
end

obj(sol :: SoSSolution) = sol.primalobj
primalobj(sol :: SoSSolution) = sol.primalobj
dualobj(sol :: SoSSolution) = sol.dualobj
status(sol :: SoSSolution) = sol.status

function sos_sol_infeasible(prog :: Program, deg :: Int)
    obj = prog.maximize ? -Inf : Inf
    SoSSolution(prog,deg,obj,obj,Dict{SoSMonom,Float64}(),zeros(0,0),zeros(0,0),:Infeasible)
end
function sos_sol_unbounded(prog :: Program, deg :: Int)
    obj = prog.maximize ? Inf : -Inf
    SoSSolution(prog,deg,obj,obj,Dict{SoSMonom,Float64}(),zeros(0,0),zeros(0,0),:Unbounded)
end

function badsol_check(sol :: SoSSolution)
    if sol.status == :Unbounded
        throw(ArgumentError("The program was unbounded."))
    elseif sol.status == :Infeasible
        throw(ArgumentError("The program was infeasible."))
    elseif sol.status == :Error
        throw(ArgumentError("There was an error in solving the program."))
    elseif sol.status == :Warning
        println("Warning: the SDP solution was abnormal in some way.")
    end
end

# Extracts moments from a solution.

function moment(sol :: SoSSolution, monom :: SoSMonom)

    if deg(monom) > sol.degree
       throw(ArgumentError("Requested moment degree is higher than solution degree"))
    elseif !haskey(sol.moments, monom)
       throw(ArgumentError("Requested moment is not described by this SoS solution"))
    end
    badsol_check(sol)

    sol.moments[monom]
end

moment(sol :: SoSSolution, poly :: SoSPoly) = sum([ moment(sol,monom) * coeff for (monom,coeff) in poly ])
moment(sol :: SoSSolution, poly :: Expr) = moment(sol, parsepoly(nothing, poly))
moment(sol :: SoSSolution, symb :: Symbol) = moment(sol, parsepoly(nothing, symb))
moment(sol :: SoSSolution, str :: AbstractString) = moment(sol, parse(str))
macro moment(sol, args...)
    escargs = [esc(x) for x in args[2:end]]
    quote
        str = @sprintf($(args[1]),$(escargs...))
        moment( $(esc(sol)), parse(str) )
    end
end

# Polynomial represented by the dual matrix. This is congruent,
# modulo the constraints, to the objective function minus the dual
# objective value, and is a sum of squares.
# XXX currently unused and private
function dualpoly(sol :: SoSSolution)
    mon = vcat( [ monoms(sol.prog,i) for i in 0:div(sol.degree,2) ] ... )

    po = SoSPoly()
    for i in 1:length(mon)
        for j in 1:length(mon)
            prod = mon[i] * mon[j]
            po[prod] = get(po, prod, 0.0) + sol.dualmatrix[i,j]
        end
    end
    po
end

# This code processes the dual solution / SoS proof, and prints polynomials, the sum of
# whose squares equals the dual polynomial (cf dualpoly()).
# XXX currently unused, private, and broken
function printsquares(sol :: SoSSolution; adjust=1.0, method=:svd, thresh=0.00001)

    # decode the dual matrix
    dm = sol.dualmatrix
    #mon = [ SumOfSquaresOptimization.monoms(prog,i) for i in 0:div(deg,2) ]
    mon = [ SumOfSquaresOptimization.monoms(prog,i) for i in div(deg,2):-1:0 ] # reverse order for good cholesky results
    mon = vcat(mon...)
    mtx = zeros(length(mon),length(mon))
    for i in 1:length(mon)
        for j in 1:length(mon)
            mtx[i,j] = dm[1,mon[i],mon[j]]
        end
    end

    if method == :cholesky
        ch=chol(mtx)

        nonzero = 0
        for i in 1:size(mtx,1)
            vec = Base.vec(ch[i,:])

            # threshold
            if dot(vec,vec) < thresh
                continue
            end

            # make the poly
            s = SoSPoly()
            for j in 1:size(mtx,1)
                if abs(vec[j]) < thresh
                    continue
                end
                s[mon[j]] = vec[j] / sqrt(adjust)
            end

            # display
            @printf("square of: %s\n\n", s)
            nonzero += 1

        end
        @printf("threshold after %d squares; the remaining %d are negligible\n", nonzero, size(mtx,1)-nonzero)

    else
        # svd to get the squares involved
        sv=svdfact(mtx)

        for i in 1:size(mtx,1)
            # singular value
            sc = sqrt(sv[:S][i] / adjust)

            # threshold
            if sc^2 < thresh
                @printf("threshold after %d squares; the remaining %d are negligible\n", i-1, size(mtx,1)-i+1)
                break
            end

            # make the poly
            s = SoSPoly()
            for j in 1:size(mtx,1)
                coeff = sv[:U][j,i] * sc
                if(abs(coeff) >= thresh)
                    s[mon[j]] = coeff
                end
            end

            # display
            @printf("square of: %s\n\n", s)
        end
    end
end

# Dumps a solution to stdout.
function dumpsol(sol :: SoSSolution)
    badsol_check(sol)
    println("Objective:")
    println(sol.primalobj)
    println("Moments:")
    println(sol.moments)
    println("Dual matrix:")
    println(sol.dualmatrix)
end

max_stars_repo_name: willperry/SumOfSquaresOptimization


text:
using CenteredAxes
using Test
using OffsetArrays

@testset "CenteredAxes.jl" begin
    @testset "Array" begin
        A = ones(3,3)
        I = to_indices(A, axes(A), (Centered(), :))
        @test I == (-1:1, 1:3)

        A = ones(2,2)
        I = to_indices(A, axes(A), (Centered(), 1:2))
        @test I == (-1:0, 1:2)
    end
    @testset "OffsetArrays" begin
        @testset "to_indices" begin
            A = ones(3:5, 3:5)
            I = to_indices(A, axes(A), (Centered(), :))
        	@test I == (-1:1, 3:5)
        	I = to_indices(A, axes(A), (Centered(), Centered()))
        	@test I == (-1:1, -1:1)
        	I = to_indices(A, axes(A), (3:4, Centered()))
        	@test I == (3:4, -1:1)

        	A = ones(7:8, 2:3)
        	I = to_indices(A, axes(A), (Centered(), :))
        	@test I == (-1:0, 2:3)
        	I = to_indices(A, axes(A), (:, Centered()))
        	@test I == (7:8, -1:0)
        end
        @testset "offset" begin
            @testset "Array" begin
                A = ones(2, 2)
                O = OffsetArray(A, Centered(), :)
                @test axes(O) == (-1:0, axes(A,2))
                O = OffsetArray(A, Centered(), Centered())
                @test axes(O) == (-1:0, -1:0)

                A = ones(3, 3)
                O = OffsetArray(A, Centered(), :)
                @test axes(O) == (-1:1, axes(A,2))
                O = OffsetArray(A, Centered(), Centered())
                @test axes(O) == (-1:1, -1:1)
            end
            @testset "OffsetArray" begin
                A = ones(2:3, 2:3)
                O = OffsetArray(A, Centered(), :)
                @test axes(O) == (-1:0, axes(A,2))
                O = OffsetArray(A, Centered(), Centered())
                @test axes(O) == (-1:0, -1:0)

                A = ones(2:4, 2:4)
                O = OffsetArray(A, Centered(), :)
                @test axes(O) == (-1:1, axes(A,2))
                O = OffsetArray(A, Centered(), Centered())
                @test axes(O) == (-1:1, -1:1)
            end
        end
    end
end


text:
#!/usr/bin/env julia

using Luxor

using Test

using Random
Random.seed!(42)

fname = "tiler-test1.pdf"
pagewidth, pageheight = 600, 900
Drawing(pagewidth, pageheight, fname)
origin() # move 0/0 to center
setantialias(6)
background("ivory")
setopacity(0.9)
setline(0.6)

# width, height, nrows, ncols, margin
pagetiles = Tiler(pagewidth, pageheight, 8, 2, margin=20)
t = length(pagetiles)

setopacity(0.5)

for (pos, n) in pagetiles
  randomhue()
  ellipse(pos, pagetiles.tilewidth, pagetiles.tileheight, :fill)
end

for tile in pagetiles
    cpos, n =  tile
    for j in 1:20
        box(cpos, 5j, 5j, :stroke)
    end
end

pagetiles = Tiler(200, 300, 4, 5, margin=20)
t = length(pagetiles)

for (pos, n) in pagetiles
  randomhue()
  ellipse(pos, pagetiles.tilewidth, pagetiles.tileheight, :fill)
end

@test finish() == true


text:
using Tulip
@static if VERSION < v"0.7.0-DEV.2005"
    using Base.Test
else
    using Test
end

include("../src/Tulip.jl")

# write your own tests here
const testdir = dirname(@__FILE__)

const test_files = [
    # include test file name here (without .jl extension)
    "model",
    "tst_basic",
    "denseBlockAngular",
    "linear_algebra"

]

for f in test_files
    tp = joinpath(testdir, "$(f).jl")
    include(tp)
end


text:
include("../neat_test.jl")

const DEFAULT_DATASET_PATH = "../../../datasets"

println("--> Dataset demo 2 (overlap)")
config = "test_overlap_config.txt"
p1 = run_NEAT_epochs(config, 5000, false)
print_best_solution_perfomance(p1)

plot_neat_fitness(p1, imagename="fitness-demo2-t1.png")
plot_neat_IP(p1, imagename="IP-demo2-t1.png")
plot_neat_species(p1, imagename="species-demo2-t1.png")
plot_output_distribution(p1, imagename="distribution-demo2-t1.png")
plot_complexity(p1, imagename="solution-complexity-demo2-t1.png")
plot_hit_rate(p1, imagename="hit-rate-demo2-t1.png")

#pop = getPopulation("checkpoint-dt-demo-overlap-t.jld2")

max_stars_repo_name: Lucas-Muniz/MNEAT

max_issues_repo_name: Lucas-Muniz/MNEAT

max_forks_repo_name: Lucas-Muniz/MNEAT


text:
#======================= Particle Swarm Optimization ==========================#

# Particle Swarm Optimization is a stochastic optimization algorithm without
# interbreeding.  It mimics a flock of birds, who prefer to spread out but will
# hone in if one finds what they are all looking for (in a very vague sense).

# A PSO solution is a list of the values for all the parameters of interest.
# These parameters must lie within user-specified bounds.  The goal is to
# find the set of parameters which maximizes a "fitness" function.  PSO is
# typically used to maximize erratic functions which depend on a large number of
# parameters.  (My introduction to PSO was http://boxcar2d.com/, where one
# optimizes the performance of a polygonal car with over 16 degrees of freedom.
# Generic algorithm and PSO are both options - PSO was better at fine-tuning)

module ParticleSwarm
export PSO

type Particle{T<:Vector}
  position::T
  currentFitness
  velocity::T
  bestPosition::T
  bestFitness
end

# Permit construction with no history
Particle{T<:Vector}(x::T, f, v::T) = Particle{T}(x, f, v, x, f)

# Compare two particles.  Julia can find maximum element of an array so long as
# Base.isless is defined.
import Base.isless
Base.isless(x::Particle, y::Particle) = x.currentFitness < y.currentFitness

# Helper to generate <amount> random numbers between two bounds.  Only uses
# Float64 precision but that should be enough for us.
randBetween(min::Float64, max::Float64, amount=1) = min + (max - min)*rand(amount)
randBetween(min::Integer, max::Integer, amount=1) = rand(min:max, amount)

# The simplest arguments to a generic PSO function are the population size, the
# fitness function, and the bounds on the parameters.  As solution candidates
# follow swarm mechanics, a sense of "inertia" is present - alterations happen
# to the velocity rather than directly to the position.  How many neighbors can
# influence this velocity varies depending on whether there has been recent
# success.  If the swarm is consistently improving the fitness every iteration,
# all candidates will follow closely.  If many iterations have gone by with no
# improvement, the candidates follow their own dispersion rather than take input
# from their neighbors.  Lastly, the user must specify how many iterations to
# run before returning the best solution found.

# Our PSO requires all parameters be real valued so that there is a sense of
# being between bounds.  It could be better generalized to anything comparable,
# but I am using functions that assume real numbers.

function PSO{T<:Real}(
          fitness::Function,
          boundsMin::Vector{T}, boundsMax::Vector{T};
          popSize::Integer=0, # If not overridden, defaults to 5x number of vars
          neighborhoodMin::Integer=0, # If not overridden, defaults to 1/10 pop
          maxIterations::Integer=1000,
          inertiaMin=0.007, inertiaMax=0.5,
          selfWeight=1, neighborWeight=1,
          candidate::Vector{T}=randBetween.(boundsMin, boundsMax))

  popSize = (popSize > 0) ? popSize : 3*length(boundsMin)
  neighborhoodMin = (neighborhoodMin > 0) ? neighborhoodMin : div(popSize, 10)

  # Initialize a pool of "Popsize" Particles, with each element in the bounds
  pinit = [candidate'; hcat(randBetween.(boundsMin, boundsMax, popSize-1)...)]
  vinit = hcat(randBetween.(boundsMin-boundsMax, boundsMax-boundsMin, popSize)...)
  finit = fitness([pinit[i,:] for i in 1:popSize])
  populationInfo = [Particle(pinit[i,:], finit[i], vinit[i,:])
                    for i in 1:popSize]
  winner = findmax(populationInfo)[1]

  # Initialize our running PSO variables
  winnerX, winnerF = winner.position, winner.currentFitness
  N = neighborhoodMin
  W = inertiaMax
  stallCounter = 0
  iters = 0

  # An iteration.
  while(iters < maxIterations && stallCounter < 100)
    improvementFlag = false

    # For each element find a subset of length N not including
    # the element itself and identify the winner.
    neighborhoods = [map(x -> x + Int(x >= i), randperm(popSize-1)[1:N])
                      for i in 1:popSize]
    localWinners = map(n -> findmax(populationInfo[n])[1], neighborhoods)

    # New velocities are a weighted sum of old velocity, distance to local
    # winner and distance from personal best
    map((x,y) -> x.velocity = round.(W*x.velocity +
           selfWeight*rand(length(x.position)).*(x.bestPosition - x.position)
         + neighborWeight*rand(length(x.position)).*(y.position - x.position)
         , populationInfo, localWinners))

    # Update the positions based on these new velocities (can you tell I prefer
    # functional programming?). We clip it to the proper range.
    map(x -> x.position = map((p,lo,hi) -> div(lo + hi + abs(p-lo) - abs(p-hi),2),
        x.position + x.velocity, boundsMin, boundsMax), populationInfo)

    # Update the current fitness.  If it is better than the old fitness, save
    # current position.  If it is the best seen so far, udpate best fitness.
    # Because we have a noisy signal, we also re-check the fitness of our
    # global best, and for better or worse assume the new value.
    fitnesses = fitness([[winnerX]; (x->x.position).(populationInfo)])
    maxF, ind = findmax(fitnesses)
    improvementFlag = (ind > 1)
    winnerF = maxF
    for n in 1:popSize
        x = populationInfo[n]
        x.currentFitness = fitnesses[n + 1]
        if (x.currentFitness > x.bestFitness)
          x.bestPosition = x.position
          x.bestFitness = x.currentFitness
        end
    end

    # Update PSO variables depending on state
    if improvementFlag
      winnerX = populationInfo[ind - 1].position
      stallCounter = max(0, stallCounter-1)
      N = neighborhoodMin
    else
        stallCounter += 1
      N = min(N + neighborhoodMin, popSize - 1)
    end

    if stallCounter < 2
      W = min(2*W, inertiaMax)
    elseif stallCounter > 5
      W = max(W/2, inertiaMin)
    end

  # Debug output
  println(iters)
  poolF, poolInd = findmax(fitnesses[2:(1+popSize)])
  println("Highest fitness this generation: "*string(poolF)*" by member "*string(poolInd - 1))
  println("Global optimum is "*string(winnerF)*" by parameters "*string(winnerX))

  iters += 1
  end # End loop

  # Return our best found position and its fitness score
  winnerX, winnerF
end

end # End module ParticleSwarm

max_stars_repo_name: PainterQubits/PulseController

max_issues_repo_name: PainterQubits/PulseController

max_forks_repo_name: PainterQubits/PulseController


text:
using PowerSystems
using NLsolve
const PSY = PowerSystems

############### Data Network ########################
include(joinpath(dirname(@__FILE__), "dynamic_test_data.jl"))
include(joinpath(dirname(@__FILE__), "data_utils.jl"))
############### Data Network ########################
threebus_file_dir = joinpath(dirname(@__FILE__), "ThreeBusNetwork.raw")
threebus_sys = System(threebus_file_dir, runchecks = false)
add_source_to_ref(threebus_sys)

### Case 2 Generators ###

function dyn_gen_simple_anderson(generator)
    return PSY.DynamicGenerator(
        name = get_name(generator), #static generator
        ω_ref = 1.0, # ω_ref
        machine = machine_simple_anderson(), #machine
        shaft = shaft_no_damping(), #shaft
        avr = avr_type1(), #avr
        prime_mover = tg_none(), #tg
        pss = pss_none(),
    ) #pss
end

for g in get_components(Generator, threebus_sys)
    case_gen = dyn_gen_simple_anderson(g)
    add_component!(threebus_sys, case_gen, g)
end

#Compute Y_bus after fault
fault_branches = deepcopy(collect(get_components(Branch, threebus_sys))[2:end])
Ybus_fault = PSY.Ybus(fault_branches, get_components(Bus, threebus_sys))[:, :]


text:
# eigenvalue/eigenvector computations

struct EigenvalueComputationError <: Exception end

Base.showerror(io::IO, ::EigenvalueComputationError) = print(
    io,
    "Failed to separate eigenvalues.\n",
    "You may try to increase precision, apply a similarity transform, or call `eig_multiple` if clusters of eigenvalues are expected.",
)

function approx_eig_qr!(
    eigvals::AcbVectorLike,
    eigvecs::AcbMatrixLike,
    A::AcbMatrixLike;
    tol = Mag(),
    maxiter = 0,
    prec = _precision(A),
    side = :right,
)
    @boundscheck size(eigvals, 1) == size(A, 1) && size(eigvecs) == size(A) || throw(
        DimensionMismatch("eigvals, eigvecs and A sizes are not compatible."),
    )
    @assert side in (:left, :right) || throw(
        ArgumentError("In approx_eig_qr!: `side` kwarg must be eithe :left or :right"),
    )

    if iszero(tol)
        if side == :right
            approx_eig_qr!(eigvals, C_NULL, eigvecs, A, C_NULL, maxiter, prec = prec)
        else # side == :left
            approx_eig_qr!(eigvals, eigvecs, C_NULL, A, C_NULL, maxiter, prec = prec)
        end
    else
        mag_tol = convert(Mag, tol)
        if side == :right
            approx_eig_qr!(eigvals, C_NULL, eigvecs, A, mag_tol, maxiter, prec = prec)
        else # side == :left
            approx_eig_qr!(eigvals, eigvecs, C_NULL, A, mag_tol, maxiter, prec = prec)
        end
    end
    return eigvals
end

function approx_eig_qr!(
    eigvals::AcbVectorLike,
    A::AcbMatrixLike;
    tol = Mag(),
    maxiter = 0,
    prec = _precision(A),
)
    @boundscheck size(eigvals, 1) == size(A, 1) || throw(
        DimensionMismatch("eigvals, eigvecs and A sizes are not compatible."),
    )
    if iszero(tol)
        approx_eig_qr!(eigvals, C_NULL, C_NULL, A, C_NULL, maxiter, prec = prec)
    else
        mag_tol = convert(Mag, tol)
        approx_eig_qr!(eigvals, C_NULL, C_NULL, A, mag_tol, maxiter, prec = prec)
    end
    return eigvals
end

function approx_eig_qr(
    A::Union{AcbMatrix,AcbRefMatrix};
    tol = Mag(),
    maxiter = 0,
    prec = precision(A),
    side = :right,
)
    λ_approx = similar(A, size(A, 1))
    eigvecs_approx = similar(A)
    approx_eig_qr!(
        λ_approx,
        eigvecs_approx,
        A,
        tol = tol,
        maxiter = maxiter,
        prec = prec,
        side = side,
    )
    return λ_approx, eigvecs_approx
end

for jlf in (:eig_simple_rump!, :eig_simple_vdhoeven_mourrain!, :eig_simple!)
    jlf_allocating = Symbol(string(jlf)[1:end-1])
    @eval begin
        function $jlf(
            eigvals::AcbVectorLike,
            eigvecs::AcbMatrixLike,
            A::AcbMatrixLike,
            eigvals_approx::AcbVectorLike,
            R_eigvecs_approx::AcbMatrixLike;
            prec = _precision(A),
            side = :right,
        )
            @assert side in (:left, :right) || throw(
                ArgumentError(
                    "In approx_eig_qr!: `side` kwarg must be either :left or :right",
                ),
            )

            @boundscheck size(eigvals, 1) == size(eigvals_approx, 1) == size(A, 1) || throw(
                DimensionMismatch("Eigenvalues sizes are not compatible with matrix A"),
            )
            @boundscheck size(eigvecs) == size(R_eigvecs_approx) == size(A) || throw(
                DimensionMismatch("Eigenvectors sizes are not compatible with matrix A"),
            )

            val = if side == :left
                $jlf(eigvals, eigvecs, C_NULL, A, eigvals_approx, R_eigvecs_approx, prec = prec)
            else
                $jlf(eigvals, C_NULL, eigvecs, A, eigvals_approx, R_eigvecs_approx, prec = prec)
            end
            isone(val) || throw(EigenvalueComputationError())
            return eigvals, eigvecs
        end

        function $jlf(
            eigvals::AcbVectorLike,
            A::AcbMatrixLike,
            eigvals_approx::AcbVectorLike,
            R_eigvecs_approx::AcbMatrixLike;
            prec = _precision(A),
        )
            @boundscheck size(eigvals_approx, 1) == size(A, 1) || throw(
                DimensionMismatch("Eigenvalues sizes are not compatible with matrix A"),
            )
            @boundscheck size(R_eigvecs_approx) == size(A) || throw(
                DimensionMismatch("Eigenvectors sizes are not compatible with matrix A"),
            )

            val = $jlf(
                eigvals,
                C_NULL,
                C_NULL,
                A,
                eigvals_approx,
                R_eigvecs_approx,
                prec = prec,
            )
            isone(val) || throw(EigenvalueComputationError())
            return eigvals
        end

        function $jlf(
            eigvals::AcbVectorLike,
            eigvecs::AcbMatrixLike,
            A::Union{AcbMatrix,AcbRefMatrix};
            prec = precision(A),
            side = :right,
        )
            eigvals_approx, R_eigvecs_approx = approx_eig_qr(A, prec = prec)
            return $jlf(
                eigvals,
                eigvecs,
                A,
                eigvals_approx,
                R_eigvecs_approx,
                prec = prec,
                side = side,
            )
        end

        function $jlf(
            eigvals::AcbVectorLike,
            A::Union{AcbMatrix,AcbRefMatrix};
            prec = precision(A),
        )
            λ_approx, R_approx = approx_eig_qr(A, prec = prec)
            return $jlf(eigvals, A, λ_approx, R_approx, prec = prec)
        end

        function $jlf_allocating(
            A::Union{AcbMatrix,AcbRefMatrix};
            prec = precision(A),
            side = :right,
        )
            eigvals = similar(A, size(A, 1))
            eigvecs = similar(A)
            $jlf(eigvals, eigvecs, A, prec = prec, side = side)
            return eigvals, eigvecs
        end
    end
end

function eig_global_enclosure(
    A::Union{AcbMatrix,AcbRefMatrix},
    eigvals_approx::AcbVectorLike,
    R_eigvecs_approx::AcbMatrixLike;
    prec = precision(A),
)
    return eig_global_enclosure!(Mag(), A, λ_approx, R_approx, prec = prec)
end

function eig_enclosure_rump!(
    λ::AcbLike,
    eigvecs::Union{AcbMatrix,AcbRefMatrix},
    A::Union{AcbMatrix,AcbRefMatrix},
    λ_approx::AcbLike,
    R_eigvecs_approx::Union{AcbMatrix,AcbRefMatrix};
    prec = precision(A),
)
    @boundscheck size(eigvecs) == size(R_eigvecs_approx) &&
                 size(eigvecs, 1) == size(A, 1) ||
                 throw(DimensionMismatch("Eigenvalues sizes are not compatible"))

    return eig_enclosure_rump!(
        λ,
        C_NULL,
        eigvecs,
        A,
        λ_approx,
        R_eigvecs_approx,
        prec = prec,
    )
end

for f in (:eig_multiple_rump, :eig_multiple)
    f_inplace = Symbol(f, "!")
    @eval begin
        function $f_inplace(
            eigvals::Union{AcbVector,AcbRefVector},
            A::Union{AcbMatrix,AcbRefMatrix};
            prec = precision(A),
        )
            λ_approx, R_approx = approx_eig_qr(A, prec = prec)
            return $f_inplace(eigvals, A, λ_approx, R_approx, prec = prec)
        end

        function $f(
            A::Union{AcbMatrix,AcbRefMatrix},
            eigvals_approx::AcbVectorLike,
            R_eigvecs_approx::AcbMatrixLike;
            prec = precision(A),
        )
            λ = similar(A, size(A, 1))
            $f_inplace(λ, A, eigvals_approx, R_eigvecs_approx, prec = prec)
            return λ
        end

        function $f(A::Union{AcbMatrix,AcbRefMatrix}; prec = precision(A))
            λ = similar(A, size(A, 1))
            $f_inplace(λ, A, prec = prec)
            return λ
        end

    end
end

LinearAlgebra.eigvals(A::Union{AcbMatrix,AcbRefMatrix}) = eig_multiple(A)