text:
@doc raw"""
    y = prox_distance(M,λ,f,x [, p=2])
    prox_distance!(M, y, λ, f, x [, p=2])

compute the proximal map ``\operatorname{prox}_{λ\varphi}`` with
parameter λ of ``φ(x) = \frac{1}{p}d_{\mathcal M}^p(f,x)``.
For the mutating variant the computation is done in place of `y`.

# Input
* `M` – a [Manifold](https://juliamanifolds.github.io/Manifolds.jl/stable/interface.html#ManifoldsBase.Manifold) ``\mathcal M``
* `λ` – the prox parameter
* `f` – a point ``f ∈ \mathcal M`` (the data)
* `x` – the argument of the proximal map

# Optional argument
* `p` – (`2`) exponent of the distance.

# Ouput
* `y` – the result of the proximal map of ``φ``
"""
function prox_distance(M::AbstractManifold, λ, f, x, p::Int=2)
    d = distance(M, f, x)
    if p == 2
        t = λ / (1 + λ)
    elseif p == 1
        t = (λ < d) ? λ / d : 1.0
    else
        throw(
            ErrorException(
                "Proximal Map of distance(M,f,x) not implemented for p=$(p) (requires p=1 or 2)",
            ),
        )
    end
    return exp(M, x, log(M, x, f), t)
end
function prox_distance!(M::AbstractManifold, y, λ, f, x, p::Int=2)
    d = distance(M, f, x)
    if p == 2
        t = λ / (1 + λ)
    elseif p == 1
        t = (λ < d) ? λ / d : 1.0
    else
        throw(
            ErrorException(
                "Proximal Map of distance(M,f,x) not implemented for p=$(p) (requires p=1 or 2)",
            ),
        )
    end
    return exp!(M, y, x, log(M, x, f), t)
end

@doc raw"""
    [y1,y2] = prox_TV(M, λ, [x1,x2] [,p=1])
    prox_TV!(M, [y1,y2] λ, [x1,x2] [,p=1])

Compute the proximal map ``\operatorname{prox}_{λ\varphi}`` of
``φ(x,y) = d_{\mathcal M}^p(x,y)`` with
parameter `λ`.

# Input

* `M` – a [Manifold](https://juliamanifolds.github.io/Manifolds.jl/stable/interface.html#ManifoldsBase.Manifold)
* `λ` – a real value, parameter of the proximal map
* `(x1,x2)` – a tuple of two points,

# Optional

(default is given in brackets)
* `p` – (1) exponent of the distance of the TV term

# Ouput

* `(y1,y2)` – resulting tuple of points of the ``\operatorname{prox}_{λφ}(```(x1,x2)```)``.
  The result can also be computed in place.
"""
function prox_TV(M::AbstractManifold, λ::Number, x::Tuple{T,T}, p::Int=1) where {T}
    d = distance(M, x[1], x[2])
    if p == 1
        t = min(0.5, λ / d)
    elseif p == 2
        t = λ / (1 + 2 * λ)
    else
        throw(
            ErrorException(
                "Proximal Map of TV(M,x1,x2,p) not implemented for p=$(p) (requires p=1 or 2)",
            ),
        )
    end
    return (exp(M, x[1], log(M, x[1], x[2]), t), exp(M, x[2], log(M, x[2], x[1]), t))
end
function prox_TV!(M::AbstractManifold, y, λ::Number, x::Tuple{T,T}, p::Int=1) where {T}
    d = distance(M, x[1], x[2])
    if p == 1
        t = min(0.5, λ / d)
    elseif p == 2
        t = λ / (1 + 2 * λ)
    else
        throw(
            ErrorException(
                "Proximal Map of TV(M,x1,x2,p) not implemented for p=$(p) (requires p=1 or 2)",
            ),
        )
    end
    X1 = log(M, x[1], x[2])
    X2 = log(M, x[2], x[1])
    exp!(M, y[1], x[1], X1, t)
    exp!(M, y[2], x[2], X2, t)
    return y
end
@doc raw"""
    ξ = prox_TV(M,λ,x [,p=1])

compute the proximal maps ``\operatorname{prox}_{λ\varphi}`` of
all forward differences occurring in the power manifold array, i.e.
``\varphi(xi,xj) = d_{\mathcal M}^p(xi,xj)`` with `xi` and `xj` are array
elemets of `x` and `j = i+e_k`, where `e_k` is the ``k``th unitvector.
The parameter `λ` is the prox parameter.

# Input
* `M` – a [Manifold](https://juliamanifolds.github.io/Manifolds.jl/stable/interface.html#ManifoldsBase.Manifold)
* `λ` – a real value, parameter of the proximal map
* `x` – a point.

# Optional
(default is given in brackets)
* `p` – (1) exponent of the distance of the TV term

# Ouput
* `y` – resulting  point containing with all mentioned proximal
  points evaluated (in a cyclic order). The computation can also be done in place
"""
function prox_TV(M::PowerManifold, λ, x, p::Int=1)
    y = deepcopy(x)
    power_size = power_dimensions(M)
    R = CartesianIndices(Tuple(power_size))
    d = length(power_size)
    maxInd = last(R).I
    for k in 1:d # for all directions
        ek = CartesianIndex(ntuple(i -> (i == k) ? 1 : 0, d)) #k th unit vector
        for l in 0:1
            for i in R # iterate over all pixel
                if (i[k] % 2) == l
                    J = i.I .+ ek.I #i + e_k is j
                    if all(J .<= maxInd) # is this neighbor in range?
                        j = CartesianIndex(J...) # neigbbor index as Cartesian Index
                        (y[i], y[j]) = prox_TV(M.manifold, λ, (y[i], y[j]), p) # Compute TV on these
                    end
                end
            end # i in R
        end # even odd
    end # directions
    return y
end
function prox_TV!(M::PowerManifold, y, λ, x, p::Int=1)
    power_size = power_dimensions(M)
    R = CartesianIndices(Tuple(power_size))
    d = length(power_size)
    copyto!(M, y, x)
    maxInd = last(R).I
    for k in 1:d # for all directions
        ek = CartesianIndex(ntuple(i -> (i == k) ? 1 : 0, d)) #k th unit vector
        for l in 0:1
            for i in R # iterate over all pixel
                if (i[k] % 2) == l # even/odd splitting
                    J = i.I .+ ek.I #i + e_k is j
                    if all(J .<= maxInd) # is this neighbor in range?
                        j = CartesianIndex(J...) # neigbbor index as Cartesian Index
                        prox_TV!(M.manifold, [y[i], y[j]], λ, (y[i], y[j]), p) # Compute TV on these
                    end
                end
            end # i in R
        end # even odd
    end # directions
    return y
end
@doc raw"""
    y = prox_parallel_TV(M, λ, x [,p=1])
    prox_parallel_TV!(M, y, λ, x [,p=1])

compute the proximal maps ``\operatorname{prox}_{λφ}`` of
all forward differences occurring in the power manifold array, i.e.
``φ(x_i,x_j) = d_{\mathcal M}^p(x_i,x_j)`` with `xi` and `xj` are array
elements of `x` and `j = i+e_k`, where `e_k` is the ``k``th unit vector.
The parameter `λ` is the prox parameter.

# Input
* `M`     – a `PowerManifold` manifold
* `λ`     – a real value, parameter of the proximal map
* `x`     – a point

# Optional
(default is given in brackets)
* `p` – (`1`) exponent of the distance of the TV term

# Ouput
* `y`  – resulting Array of points with all mentioned proximal
  points evaluated (in a parallel within the arrays elements).
  The computation can also be done in place.

*See also* [`prox_TV`](@ref)
"""
function prox_parallel_TV(M::PowerManifold, λ, x::AbstractVector, p::Int=1)
    R = CartesianIndices(x[1])
    d = ndims(x[1])
    if length(x) != 2 * d
        throw(
            ErrorException(
                "The number of inputs from the array ($(length(x))) has to be twice the data dimensions ($(d)).",
            ),
        )
    end
    maxInd = Tuple(last(R))
    # create an array for even/odd splitted proxes along every dimension
    y = deepcopy(x)
    yV = reshape(y, d, 2)
    xV = reshape(x, d, 2)
    for k in 1:d # for all directions
        ek = CartesianIndex(ntuple(i -> (i == k) ? 1 : 0, d)) #k th unit vector
        for l in 0:1 # even odd
            for i in R # iterate over all pixel
                if (i[k] % 2) == l
                    J = i.I .+ ek.I #i + e_k is j
                    if all(J .<= maxInd) # is this neighbor in range?
                        j = CartesianIndex(J...) # neigbbor index as Cartesian Index
                        # parallel means we apply each (direction even/odd) to a seperate copy of the data.
                        (yV[k, l + 1][i], yV[k, l + 1][j]) = prox_TV(
                            M.manifold, λ, (xV[k, l + 1][i], xV[k, l + 1][j]), p
                        ) # Compute TV on these
                    end
                end
            end # i in R
        end # even odd
    end # directions
    return y
end
function prox_parallel_TV!(
    M::PowerManifold, y::AbstractVector, λ, x::AbstractVector, p::Int=1
)
    R = CartesianIndices(x[1])
    d = ndims(x[1])
    if length(x) != 2 * d
        throw(
            ErrorException(
                "The number of inputs from the array ($(length(x))) has to be twice the data dimensions ($(d)).",
            ),
        )
    end
    maxInd = Tuple(last(R))
    # init y
    for i in 1:length(x)
        copyto!(M, y[i], x[i])
    end
    yV = reshape(y, d, 2)
    xV = reshape(x, d, 2)
    for k in 1:d # for all directions
        ek = CartesianIndex(ntuple(i -> (i == k) ? 1 : 0, d)) #k th unit vector
        for l in 0:1 # even odd
            for i in R # iterate over all pixel
                if (i[k] % 2) == l
                    J = i.I .+ ek.I #i + e_k is j
                    if all(J .<= maxInd) # is this neighbor in range?
                        j = CartesianIndex(J...) # neigbbor index as Cartesian Index
                        # parallel means we apply each (direction even/odd) to a seperate copy of the data.
                        prox_TV!(
                            M.manifold,
                            [yV[k, l + 1][i], yV[k, l + 1][j]],
                            λ,
                            (xV[k, l + 1][i], xV[k, l + 1][j]),
                            p,
                        ) # Compute TV on these in place of y
                    end
                end
            end # i in R
        end # even odd
    end # directions
    return y
end

@doc raw"""
    (y1,y2,y3) = prox_TV2(M,λ,(x1,x2,x3),[p=1], kwargs...)
    prox_TV2!(M, y, λ,(x1,x2,x3),[p=1], kwargs...)

Compute the proximal map ``\operatorname{prox}_{λ\varphi}`` of
``\varphi(x_1,x_2,x_3) = d_{\mathcal M}^p(c(x_1,x_3),x_2)`` with
parameter `λ`>0, where ``c(x,z)`` denotes the mid point of a shortest
geodesic from `x1` to `x3` that is closest to `x2`.
The result can be computed in place of `y`.

# Input

* `M`          – a manifold
* `λ`          – a real value, parameter of the proximal map
* `(x1,x2,x3)` – a tuple of three points

* `p` – (`1`) exponent of the distance of the TV term

# Optional
`kwargs...` – parameters for the internal [`subgradient_method`](@ref)
    (if `M` is neither `Euclidean` nor `Circle`, since for these a closed form
    is given)

# Output
* `(y1,y2,y3)` – resulting tuple of points of the proximal map.
  The computation can also be done in place.
"""
function prox_TV2(
    M::AbstractManifold,
    λ,
    x::Tuple{T,T,T},
    p::Int=1;
    stopping_criterion::StoppingCriterion=StopAfterIteration(10),
    kwargs...,
) where {T}
    (p != 1) && throw(
        ErrorException(
            "Proximal Map of TV2(M, λ, x, p) not implemented for p=$(p) (requires p=1) on general manifolds.",
        ),
    )
    PowX = SVector(x)
    PowM = PowerManifold(M, NestedPowerRepresentation(), 3)
    xR = PowX
    F(M, x) = 1 / 2 * distance(M, PowX, x)^2 + λ * costTV2(M, x)
    ∂F(PowM, x) = log(PowM, x, PowX) + λ * grad_TV2(PowM, x)
    subgradient_method!(PowM, F, ∂F, xR; stopping_criterion=stopping_criterion, kwargs...)
    return (xR...,)
end
function prox_TV2!(
    M::AbstractManifold,
    y,
    λ,
    x::Tuple{T,T,T},
    p::Int=1;
    stopping_criterion::StoppingCriterion=StopAfterIteration(10),
    kwargs...,
) where {T}
    (p != 1) && throw(
        ErrorException(
            "Proximal Map of TV2(M, λ, x, p) not implemented for p=$(p) (requires p=1) on general manifolds.",
        ),
    )
    PowX = SVector(x)
    PowM = PowerManifold(M, NestedPowerRepresentation(), 3)
    copyto!(M, y, PowX)
    F(M, x) = 1 / 2 * distance(M, PowX, x)^2 + λ * costTV2(M, x)
    ∂F!(M, y, x) = log!(M, y, x, PowX) + λ * grad_TV2!(M, y, x)
    subgradient_method!(
        PowM,
        F,
        ∂F!,
        y;
        stopping_criterion=stopping_criterion,
        evaluation=MutatingEvaluation(),
        kwargs...,
    )
    return y
end
@doc raw"""
    y = prox_TV2(M, λ, x[, p=1])
    prox_TV2!(M, y, λ, x[, p=1])

compute the proximal maps ``\operatorname{prox}_{λ\varphi}`` of
all centered second order differences occuring in the power manifold array, i.e.
``\varphi(x_k,x_i,x_j) = d_2(x_k,x_i.x_j)``, where ``k,j`` are backward and forward
neighbors (along any dimension in the array of `x`).
The parameter `λ` is the prox parameter.

# Input
* `M` – a [Manifold](https://juliamanifolds.github.io/Manifolds.jl/stable/interface.html#ManifoldsBase.Manifold)
* `λ` – a real value, parameter of the proximal map
* `x` – a points.

# Optional
(default is given in brackets)
* `p` – (`1`) exponent of the distance of the TV term

# Output
* `y` – resulting point with all mentioned proximal points evaluated (in a cylic order).
  The computation can also be done in place.
"""
function prox_TV2(M::PowerManifold{N,T}, λ, x, p::Int=1) where {N,T}
    y = deepcopy(x)
    return prox_TV2!(M, y, λ, x, p)
end
function prox_TV2!(M::PowerManifold{N,T}, y, λ, x, p::Int=1) where {N,T}
    power_size = power_dimensions(M)
    R = CartesianIndices(power_size)
    d = length(size(x))
    minInd = first(R).I
    maxInd = last(R).I
    copyto!(M, y, x)
    for k in 1:d # for all directions
        ek = CartesianIndex(ntuple(i -> (i == k) ? 1 : 0, d)) #k th unit vector
        for l in 0:2
            for i in R # iterate over all pixel
                if (i[k] % 3) == l
                    JForward = i.I .+ ek.I #i + e_k
                    JBackward = i.I .- ek.I # i - e_k
                    all(JForward .<= maxInd) &&
                        all(JBackward .>= minInd) &&
                        prox_TV2!(
                            M.manifold,
                            [y[M, JBackward...], y[M, i.I...], y[M, JForward...]],
                            λ,
                            (y[M, JBackward...], y[M, i.I...], y[M, JForward...]),
                            p,
                        )
                end # if mod 3
            end # i in R
        end # for mod 3
    end # directions
    return y
end
@doc raw"""
    project_collaborative_TV(M, λ, x, Ξ[, p=2,q=1])
    project_collaborative_TV!(M, Θ, λ, x, Ξ[, p=2,q=1])

compute the projection onto collaborative Norm unit (or α-) ball, i.e. of the function

```math
F^q(x) = \sum_{i∈\mathcal G}
  \Bigl( \sum_{j∈\mathcal I_i}
    \sum_{k=1^d} \lVert X_{i,j}\rVert_x^p\Bigr)^\frac{q/p},
```

where ``\mathcal G`` is the set of indices for ``x∈\mathcal M`` and ``\mathcal I_i``
is the set of its forward neighbors.
The computation can also be done in place of `Θ`.

This is adopted from the paper by Duran, Möller, Sbert, Cremers:
_Collaborative Total Variation: A General Framework for Vectorial TV Models_
(arxiv: [1508.01308](https://arxiv.org/abs/1508.01308)), where the most inner
norm is not on a manifold but on a vector space, see their Example 3 for
details.
"""
function project_collaborative_TV(N::PowerManifold, λ, x, Ξ, p=2.0, q=1.0, α=1.0)
    pdims = power_dimensions(N)
    if length(pdims) == 1
        d = 1
        s = 1
        iRep = (1,)
    else
        d = pdims[end]
        s = length(pdims) - 1
        if s != d
            throw(
                ErrorException(
                    "the last dimension ($(d)) has to be equal to the number of the previous ones ($(s)) but its not.",
                ),
            )
        end
        iRep = (Integer.(ones(d))..., d)
    end
    if q == 1 # Example 3 case 2
        if p == 1
            normΞ = norm.(Ref(N.manifold), x, Ξ)
            return max.(normΞ .- λ, 0.0) ./ ((normΞ .== 0) .+ normΞ) .* Ξ
        end
        if p == 2 # Example 3 case 3
            norms = sqrt.(sum(norm.(Ref(N.manifold), x, Ξ) .^ 2; dims=d + 1))
            if length(iRep) > 1
                norms = repeat(norms; inner=iRep)
            end
            # if the norm is zero add 1 to avoid division by zero, also then the
            # nominator is already (max(-λ,0) = 0) so it stays zero then
            return max.(norms .- λ, 0.0) ./ ((norms .== 0) .+ norms) .* Ξ
        end
        throw(ErrorException("The case p=$p, q=$q is not yet implemented"))
    elseif q == Inf
        if p == 2
            norms = sqrt.(sum(norm.(Ref(N.manifold), x, Ξ) .^ 2; dims=d + 1))
            if length(iRep) > 1
                norms = repeat(norms; inner=iRep)
            end
        elseif p == 1
            norms = sum(norm.(Ref(N.manifold), x, Ξ); dims=d + 1)
            if length(iRep) > 1
                norms = repeat(norms; inner=iRep)
            end
        elseif p == Inf
            norms = norm.(Ref(N.manifold), x, Ξ)
        else
            throw(ErrorException("The case p=$p, q=$q is not yet implemented"))
        end
        return (α .* Ξ) ./ max.(Ref(α), norms)
    end # end q
    return throw(ErrorException("The case p=$p, q=$q is not yet implemented"))
end
function project_collaborative_TV(N::PowerManifold, λ, x, Ξ, p::Int, q::Float64=1.0, α=1.0)
    return project_collaborative_TV(N, λ, x, Ξ, Float64(p), q, α)
end
function project_collaborative_TV(N::PowerManifold, λ, x, Ξ, p::Float64, q::Int, α=1.0)
    return project_collaborative_TV(N, λ, x, Ξ, p, Float64(q), α)
end
function project_collaborative_TV(N::PowerManifold, λ, x, Ξ, p::Int, q::Int, α=1.0)
    return project_collaborative_TV(N, λ, x, Ξ, Float64(p), Float64(q), α)
end

function project_collaborative_TV!(N::PowerManifold, Θ, λ, x, Ξ, p=2.0, q=1.0, α=1.0)
    pdims = power_dimensions(N)
    if length(pdims) == 1
        d = 1
        s = 1
        iRep = (1,)
    else
        d = pdims[end]
        s = length(pdims) - 1
        if s != d
            throw(
                ErrorException(
                    "the last dimension ($d) has to be equal to the number of the previous ones ($s) but its not.",
                ),
            )
        end
        iRep = (Integer.(ones(d))..., d)
    end
    if q == 1 # Example 3 case 2
        if p == 1
            normΞ = norm.(Ref(N.manifold), x, Ξ)
            Θ .= max.(normΞ .- λ, 0.0) ./ ((normΞ .== 0) .+ normΞ) .* Ξ
            return Θ
        elseif p == 2 # Example 3 case 3
            norms = sqrt.(sum(norm.(Ref(N.manifold), x, Ξ) .^ 2; dims=d + 1))
            if length(iRep) > 1
                norms = repeat(norms; inner=iRep)
            end
            # if the norm is zero add 1 to avoid division by zero, also then the
            # nominator is already (max(-λ,0) = 0) so it stays zero then
            Θ .= max.(norms .- λ, 0.0) ./ ((norms .== 0) .+ norms) .* Ξ
            return Θ
        else
            throw(ErrorException("The case p=$p, q=$q is not yet implemented"))
        end
    elseif q == Inf
        if p == 2
            norms = sqrt.(sum(norm.(Ref(N.manifold), x, Ξ) .^ 2; dims=d + 1))
            (length(iRep) > 1) && (norms = repeat(norms; inner=iRep))
        elseif p == 1
            norms = sum(norm.(Ref(N.manifold), x, Ξ); dims=d + 1)
            (length(iRep) > 1) && (norms = repeat(norms; inner=iRep))
        elseif p == Inf
            norms = norm.(Ref(N.manifold), x, Ξ)
        else
            throw(ErrorException("The case p=$p, q=$q is not yet implemented"))
        end
        Θ .= (α .* Ξ) ./ max.(Ref(α), norms)
        return Θ
    end # end q
    return throw(ErrorException("The case p=$p, q=$q is not yet implemented"))
end
function project_collaborative_TV!(
    N::PowerManifold, Θ, λ, x, Ξ, p::Int, q::Float64=1.0, α=1.0
)
    return project_collaborative_TV!(N, Θ, λ, x, Ξ, Float64(p), q, α)
end
function project_collaborative_TV!(N::PowerManifold, Θ, λ, x, Ξ, p::Float64, q::Int, α=1.0)
    return project_collaborative_TV!(N, Θ, λ, x, Ξ, p, Float64(q), α)
end
function project_collaborative_TV!(N::PowerManifold, Θ, λ, x, Ξ, p::Int, q::Int, α=1.0)
    return project_collaborative_TV!(N, Θ, λ, x, Ξ, Float64(p), Float64(q), α)
end


text:
# ---
# title: 1512. Number of Good Pairs
# id: problem1512
# author: Tian Jun
# date: 2020-10-31
# difficulty: Easy
# categories: Array, Hash Table, Math
# link: <https://leetcode.com/problems/number-of-good-pairs/description/>
# hidden: true
# ---
#
# Given an array of integers `nums`.
#
# A pair `(i,j)` is called _good_ if `nums[i]` == `nums[j]` and `i` < `j`.
#
# Return the number of _good_ pairs.
#
#
#
# **Example 1:**
#
#
#
#     Input: nums = [1,2,3,1,1,3]
#     Output: 4
#     Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.
#
#
# **Example 2:**
#
#
#
#     Input: nums = [1,1,1,1]
#     Output: 6
#     Explanation: Each pair in the array are _good_.
#
#
# **Example 3:**
#
#
#
#     Input: nums = [1,2,3]
#     Output: 0
#
#
#
#
# **Constraints:**
#
#   * `1 <= nums.length <= 100`
#   * `1 <= nums[i] <= 100`
#
#
## @lc code=start
using LeetCode

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

ext: jl


text:
# Catalyst specific symbolics to support SBML
struct ParameterConstantSpecies end
struct VariableBCSpecies end
Symbolics.option_to_metadata_type(::Val{:isconstantspecies}) = ParameterConstantSpecies
Symbolics.option_to_metadata_type(::Val{:isbcspecies}) = VariableBCSpecies

"""
    Catalyst.isconstant(s)

Tests if the given symbolic variable corresponds to a constant species.
"""
isconstant(s::Num) = isconstant(MT.value(s))
function isconstant(s)
    MT.getmetadata(s, ParameterConstantSpecies, false)
end

"""
    Catalyst.isbc(s)

Tests if the given symbolic variable corresponds to a boundary condition species.
"""
isbc(s::Num) = isbc(MT.value(s))
function isbc(s)
    MT.getmetadata(s, VariableBCSpecies, false)
end

# true for species which shouldn't change from the reactions
drop_dynamics(s) = isconstant(s) || isbc(s)

"""
$(TYPEDEF)

One chemical reaction.

# Fields
$(FIELDS)

# Examples

```julia
using Catalyst
@parameters k[1:20]
@variables t A(t) B(t) C(t) D(t)
rxs = [Reaction(k[1], nothing, [A]),            # 0 -> A
       Reaction(k[2], [B], nothing),            # B -> 0
       Reaction(k[3],[A],[C]),                  # A -> C
       Reaction(k[4], [C], [A,B]),              # C -> A + B
       Reaction(k[5], [C], [A], [1], [2]),      # C -> A + A
       Reaction(k[6], [A,B], [C]),              # A + B -> C
       Reaction(k[7], [B], [A], [2], [1]),      # 2B -> A
       Reaction(k[8], [A,B], [A,C]),            # A + B -> A + C
       Reaction(k[9], [A,B], [C,D]),            # A + B -> C + D
       Reaction(k[10], [A], [C,D], [2], [1,1]), # 2A -> C + D
       Reaction(k[11], [A], [A,B], [2], [1,1]), # 2A -> A + B
       Reaction(k[12], [A,B,C], [C,D], [1,3,4], [2, 3]),          # A+3B+4C -> 2C + 3D
       Reaction(k[13], [A,B], nothing, [3,1], nothing),           # 3A+B -> 0
       Reaction(k[14], nothing, [A], nothing, [2]),               # 0 -> 2A
       Reaction(k[15]*A/(2+A), [A], nothing; only_use_rate=true), # A -> 0 with custom rate
       Reaction(k[16], [A], [B]; only_use_rate=true),             # A -> B with custom rate.
       Reaction(k[17]*A*exp(B), [C], [D], [2], [1]),              # 2C -> D with non constant rate.
       Reaction(k[18]*B, nothing, [B], nothing, [2]),             # 0 -> 2B with non constant rate.
       Reaction(k[19]*t, [A], [B]),                                # A -> B with non constant rate.
       Reaction(k[20]*t*A, [B,C], [D],[2,1],[2])                  # 2A +B -> 2C with non constant rate.
  ]
```

Notes:
- `nothing` can be used to indicate a reaction that has no reactants or no products.
  In this case the corresponding stoichiometry vector should also be set to `nothing`.
- The three-argument form assumes all reactant and product stoichiometric coefficients
  are one.
"""
struct Reaction{S, T}
    """The rate function (excluding mass action terms)."""
    rate
    """Reaction substrates."""
    substrates::Vector
    """Reaction products."""
    products::Vector
    """The stoichiometric coefficients of the reactants."""
    substoich::Vector{T}
    """The stoichiometric coefficients of the products."""
    prodstoich::Vector{T}
    """The net stoichiometric coefficients of all species changed by the reaction."""
    netstoich::Vector{Pair{S,T}}
    """
    `false` (default) if `rate` should be multiplied by mass action terms to give the rate law.
    `true` if `rate` represents the full reaction rate law.
    """
    only_use_rate::Bool
end

"""
    isvalidreactant(s)

Test if a species is valid as a reactant (i.e. a variable or a constant parameter).
"""
isvalidreactant(s) = (isconstant(s) == MT.isparameter(s))

function Reaction(rate, subs, prods, substoich, prodstoich;
                  netstoich=nothing, only_use_rate=false,
                  kwargs...)

    (isnothing(prods)&&isnothing(subs)) && throw(ArgumentError("A reaction requires a non-nothing substrate or product vector."))
    (isnothing(prodstoich)&&isnothing(substoich)) && throw(ArgumentError("Both substrate and product stochiometry inputs cannot be nothing."))
    if isnothing(subs)
        subs = Vector{Term}()
        !isnothing(substoich) && throw(ArgumentError("If substrates are nothing, substrate stiocihometries have to be so too."))
        substoich = typeof(prodstoich)()
    end
    S = eltype(substoich)

    if isnothing(prods)
        prods = Vector{Term}()
        !isnothing(prodstoich) && throw(ArgumentError("If products are nothing, product stiocihometries have to be so too."))
        prodstoich = typeof(substoich)()
    end
    T = eltype(prodstoich)

    subs = value.(subs)
    prods = value.(prods)

    # try to get a common type for stoichiometry, using Any if have Syms
    stoich_type = promote_type(S,T)
    if stoich_type <: Num
        stoich_type = Any
        substoich′  = Any[value(s) for s in substoich]
        prodstoich′ = Any[value(p) for p in prodstoich]
    else
        substoich′ = (S == stoich_type) ? substoich : convert.(stoich_type, substoich)
        prodstoich′ = (T == stoich_type) ? prodstoich : convert.(stoich_type, prodstoich)
    end

    if !(all(isvalidreactant, subs) && all(isvalidreactant, prods))
        badsts = union(filter(!isvalidreactant, subs), filter(!isvalidreactant, prods))
        throw(ArgumentError("""Constant species must be parameters, and parameters must have
                 the isconstantspecies metadata, to be a substrate or product. The following
                 reactants do not follow this convention:\n $badsts"""))
    end

    ns = if netstoich === nothing
        get_netstoich(subs, prods, substoich′, prodstoich′)
    else
        (netstoich_stoichtype(netstoich) != stoich_type) ?
            convert.(stoich_type, netstoich) : netstoich
    end

    Reaction(value(rate), subs, prods, substoich′, prodstoich′, ns, only_use_rate)
end

# three argument constructor assumes stoichiometric coefs are one and integers
function Reaction(rate, subs, prods; kwargs...)
    sstoich = isnothing(subs) ? nothing : ones(Int,length(subs))
    pstoich = isnothing(prods) ? nothing : ones(Int,length(prods))
    Reaction(rate, subs, prods, sstoich, pstoich; kwargs...)
end

function print_rxside(io::IO, specs, stoich)
    # reactants/substrates
    if isempty(specs)
        print(io, "∅")
    else
        for (i,spec) in enumerate(specs)
            prspec = MT.isparameter(spec) ? spec : MT.operation(spec)
            if isequal(stoich[i],one(stoich[i]))
                print(io, prspec)
            elseif Symbolics.istree(stoich[i])
                print(io, "(", stoich[i], ")*", prspec)
            else
                print(io, stoich[i], "*", prspec)
            end

            (i < length(specs)) && print(io, " + ")
        end
    end
    nothing
end

function Base.show(io::IO, rx::Reaction)
    print(io, rx.rate, ", ")
    print_rxside(io, rx.substrates, rx.substoich)
    arrow = rx.only_use_rate ? "⇒" : "-->"
    print(io, " ", arrow, " ")
    print_rxside(io, rx.products, rx.prodstoich)
end

function ModelingToolkit.namespace_equation(rx::Reaction, name)
    subs  = isempty(rx.substrates) ? rx.substrates : [namespace_expr(sub, name) for sub in rx.substrates]
    prods = isempty(rx.products) ? rx.products : [namespace_expr(prod, name) for prod in rx.products]
    Reaction(namespace_expr(rx.rate, name),
             subs, prods, rx.substoich, rx.prodstoich,
             [namespace_expr(n[1],name) => n[2] for n in rx.netstoich], rx.only_use_rate)
end

netstoich_stoichtype(::Vector{Pair{S,T}}) where {S,T} = T

# calculates the net stoichiometry of a reaction as a vector of pairs (sub,substoich)
function get_netstoich(subs, prods, sstoich, pstoich)
    # stoichiometry as a Dictionary
    nsdict = Dict{Any, eltype(sstoich)}(sub => -sstoich[i] for (i,sub) in enumerate(subs))
    for (i,p) in enumerate(prods)
        coef = pstoich[i]
        @inbounds nsdict[p] = haskey(nsdict, p) ? nsdict[p] + coef : coef
    end

    # stoichiometry as a vector
    [el for el in nsdict if !_iszero(el[2])]
end

"""
    isbcbalanced(rx::Reaction)

True if any BC species in `rx` appears as a substrate and product with the same
stoichiometry.
"""
function isbcbalanced(rx::Reaction)
    # any substrate BC must be a product with the same stoichiometry
    for (sidx,sub) in enumerate(rx.substrates)
        if isbc(sub)
            pidx = findfirst(Base.Fix1(isequal, sub), rx.products)
            (pidx === nothing) && return false
            isequal(rx.prodstoich[pidx], rx.substoich[sidx]) || return false
        end
    end

    for prod in rx.products
        if isbc(prod)
            any(Base.Fix1(isequal,prod), rx.substrates) || return false
        end
    end

    true
end

################################## Reaction Complexes ####################################

"""
$(TYPEDEF)
One reaction complex element

# Fields
$(FIELDS)
"""
struct ReactionComplexElement{T}
    """The integer id of the species representing this element."""
    speciesid::Int
    """The stoichiometric coefficient of this species."""
    speciesstoich::T
end

"""
$(TYPEDEF)
One reaction complex.

# Fields
$(FIELDS)
"""
struct ReactionComplex{V<:Integer} <: AbstractVector{ReactionComplexElement{V}}
    """The integer ids of all species participating in this complex."""
    speciesids::Vector{Int}
    """The stoichiometric coefficients of all species participating in this complex."""
    speciesstoichs::Vector{V}

    function ReactionComplex{V}(speciesids::Vector{Int}, speciesstoichs::Vector{V}) where {V<:Integer}
        new{V}(speciesids, speciesstoichs)
    end
end

function ReactionComplex(speciesids::Vector{Int}, speciesstoichs::Vector{V}) where {V<:Integer}
    (length(speciesids) == length(speciesstoichs)) || error("Creating a complex with different number of species ids and associated stoichiometries.")
    ReactionComplex{V}(speciesids, speciesstoichs)
end

function (==)(a::ReactionComplex{V},b::ReactionComplex{V}) where {V <: Integer}
    (a.speciesids == b.speciesids) &&
    (a.speciesstoichs == b.speciesstoichs)
end
hash(rc::ReactionComplex,h::UInt) = Base.hash(rc.speciesids,Base.hash(rc.speciesstoichs,h))
Base.size(rc::ReactionComplex) = size(rc.speciesids)
Base.length(rc::ReactionComplex) = length(rc.speciesids)
Base.getindex(rc::ReactionComplex, i...) =
        ReactionComplexElement(getindex(rc.speciesids, i...), getindex(rc.speciesstoichs, i...))
Base.setindex!(rc::ReactionComplex, t::ReactionComplexElement, i...) =
    (setindex!(rc.speciesids, t.speciesid, i...); setindex!(rc.speciesstoichs, t.speciesstoich, i...); rc)
Base.isless(a::ReactionComplexElement, b::ReactionComplexElement) = isless(a.speciesid, b.speciesid)
Base.Sort.defalg(::ReactionComplex{T}) where {T <: Integer} = Base.DEFAULT_UNSTABLE

############################### Network Properties ####################################

# Internal cache for various ReactionSystem calculated properties
Base.@kwdef mutable struct NetworkProperties{I <: Integer, V <: Term}
    isempty::Bool = true
    netstoichmat::Union{Matrix{Int},SparseMatrixCSC{Int,Int}} = Matrix{Int}(undef,0,0)
    conservationmat::Matrix{I} = Matrix{I}(undef,0,0)
    col_order::Vector{Int} = Int[]
    rank::Int = 0
    nullity::Int = 0
    indepspecs::Set{V} = Set{V}()
    depspecs::Set{V} = Set{V}()
    conservedeqs::Vector{Equation} = Equation[]
    constantdefs::Vector{Equation} = Equation[]
    speciesmap::Dict{V,Int} = Dict{V,Int}()
    complextorxsmap::OrderedDict{ReactionComplex{Int},Vector{Pair{Int,Int}}} = OrderedDict{ReactionComplex{Int},Vector{Pair{Int,Int}}}()
    complexes::Vector{ReactionComplex{Int}} = Vector{ReactionComplex{Int}}(undef,0)
    incidencemat::Union{Matrix{Int},SparseMatrixCSC{Int,Int}} = Matrix{Int}(undef,0,0)
    complexstoichmat::Union{Matrix{Int},SparseMatrixCSC{Int,Int}} = Matrix{Int}(undef,0,0)
    complexoutgoingmat::Union{Matrix{Int},SparseMatrixCSC{Int,Int}} = Matrix{Int}(undef,0,0)
    incidencegraph::Graphs.SimpleDiGraph{Int} = Graphs.DiGraph()
    linkageclasses::Vector{Vector{Int}} = Vector{Vector{Int}}(undef,0)
    deficiency::Int = 0
end

function Base.show(io::IO, nps::NetworkProperties)
    if (nps.conservationmat !== nothing)
        println(io, "Conserved Equations: ")
        foreach(eq -> println(io,eq), nps.conservedeqs)
        println()
    end
end

Base.isempty(nps::NetworkProperties) = getfield(nps, :isempty)

function Base.setproperty!(nps::NetworkProperties, sym::Symbol, x)
    (sym !== :isempty) && setfield!(nps, :isempty, false)
    setfield!(nps, sym, x)
end

function reset!(nps::NetworkProperties{I,V}) where {I,V}
    nps.isempty && return
    nps.netstoichmat = Matrix{Int}(undef,0,0)
    nps.conservationmat = Matrix{I}(undef,0,0)
    empty!(nps.col_order)
    nps.rank = 0
    nps.nullity = 0
    empty!(nps.indepspecs)
    empty!(nps.depspecs)
    empty!(nps.conservedeqs)
    empty!(nps.constantdefs)
    empty!(nps.speciesmap)
    empty!(nps.complextorxsmap)
    empty!(nps.complexes)
    nps.incidencemat = Matrix{Int}(undef,0,0)
    nps.complexstoichmat = Matrix{Int}(undef,0,0)
    nps.complexoutgoingmat = Matrix{Int}(undef,0,0)
    nps.incidencegraph = Graphs.DiGraph()
    empty!(nps.linkageclasses)
    nps.deficiency = 0

    # this needs to be last due to setproperty! setting it to false
    nps.isempty = true
    nothing
end

"""
$(TYPEDEF)

A system of chemical reactions.

# Fields
$(FIELDS)

# Example
Continuing from the example in the [`Reaction`](@ref) definition:
```julia
# simple constructor that infers species and parameters
@named rs = ReactionSystem(rxs, t)

# allows specification of species and parameters
@named rs = ReactionSystem(rxs, t, [A,B,C,D], k)
```

Keyword Arguments:
- `observed::Vector{Equation}`, equations specifying observed variables.
- `systems::Vector{AbstractSystems}`, vector of sub-systems. Can be `ReactionSystem`s,
  `ODESystem`s, or `NonlinearSystem`s.
- `name::Symbol`, the name of the system (must be provided, or `@named` must be used).
- `defaults::Dict`, a dictionary mapping parameters to their default values and species to
  their default initial values.
- `checks = true`, boolean for whether to check units.
- `constraints = nothing`, a `NonlinearSystem` or `ODESystem` of coupled constraint
  equations.
- `networkproperties = NetworkProperties()`, cache for network properties calculated via API
  functions.
- `combinatoric_ratelaws = true`, sets the default value of `combinatoric_ratelaws` used in
  calls to `convert` or calling various problem types with the `ReactionSystem`.
- `balanced_bc_check = true`, sets whether to check that BC species appearing in reactions
  are balanced (i.e appear as both a substrate and a product with the same stoichiometry).

Notes:
- ReactionSystems currently do rudimentary unit checking, requiring that all species have
  the same units, and all reactions have rate laws with units of (species units) / (time
  units). Unit checking can be disabled by passing the keyword argument `checks=false`.
"""
struct ReactionSystem{U <: Union{Nothing,MT.AbstractSystem}, V <: NetworkProperties} <: MT.AbstractTimeDependentSystem
    """The reactions defining the system."""
    eqs::Vector{Reaction}
    """Independent variable (usually time)."""
    iv::Any
    """Dependent (state) variables representing amount of each species. Must not contain the
    independent variable."""
    states::Vector
    """Parameter variables. Must not contain the independent variable."""
    ps::Vector
    """Maps Symbol to corresponding variable."""
    var_to_name::Dict{Symbol,Any}
    """Equations for observed variables."""
    observed::Vector{Equation}
    """The name of the system"""
    name::Symbol
    """Internal sub-systems"""
    systems::Vector
    """
    The default values to use when initial conditions and/or
    parameters are not supplied in `ODEProblem`.
    """
    defaults::Dict
    """Type of the system"""
    connection_type::Any
    """Non-`Reaction` equations that further constrain the system"""
    constraints::U
    """`NetworkProperties` object that can be filled in by API functions. INTERNAL -- not
    considered part of the public API."""
    networkproperties::V
    """Sets whether to use combinatoric scalings in rate laws. true by default."""
    combinatoric_ratelaws::Bool

    # inner constructor is considered private and may change between non-breaking releases.
    function ReactionSystem(eqs, iv, states, ps, var_to_name, observed, name, systems,
                            defaults, connection_type, csys, nps, cls;
                            checks::Bool=true)
        if checks
            check_variables(states, iv)
            check_parameters(ps, iv)
        end

        rs = new{typeof(csys), typeof(nps)}(eqs, iv, states, ps, var_to_name, observed, name,
                                            systems, defaults, connection_type, csys, nps, cls)
        checks && validate(rs)
        rs
    end
end

function get_speciestype(iv, states, systems, constraints)
    T = Nothing
    !isempty(states) && (T = typeof(first(states)))

    if !isempty(systems)
        for sys in Iterators.filter(s -> s isa ReactionSystem, systems)
            sts = MT.states(sys)
            if !isempty(sts)
                T = typeof(first(sts))
                break
            end
        end
    end

    if T <: Nothing
        @variables A($iv)
        T = typeof(MT.unwrap(A))
    end

    T
end

function ReactionSystem(eqs, iv, states, ps;
                        observed = [],
                        systems = [],
                        name = nothing,
                        default_u0=Dict(),
                        default_p=Dict(),
                        defaults=_merge(Dict(default_u0), Dict(default_p)),
                        connection_type=nothing,
                        checks = true,
                        constraints = nothing,
                        networkproperties = nothing,
                        combinatoric_ratelaws = true,
                        balanced_bc_check = true)
    name === nothing && throw(ArgumentError("The `name` keyword must be provided. Please consider using the `@named` macro"))
    sysnames = nameof.(systems)
    (length(unique(sysnames)) == length(sysnames)) ||
        throw(ArgumentError("System names must be unique."))

    if !(isempty(default_u0) && isempty(default_p))
        Base.depwarn("`default_u0` and `default_p` are deprecated. Use `defaults` instead.", :ReactionSystem, force=true)
    end
    defaults = MT.todict(defaults)
    defaults = Dict{Any,Any}(value(k) => value(v) for (k, v) in pairs(defaults))

    iv′     = value(iv)
    states′ = value.(MT.scalarize(states))
    ps′     = value.(MT.scalarize(ps))
    eqs′    = (eqs isa Vector) ? eqs : collect(eqs)

    if any(MT.isparameter, states′)
        psts = filter(MT.isparameter, states′)
        throw(ArgumentError("Found one or more parameters among the states; this is not "
                            * "allowed. Move: $psts to be parameters."))
    end

    if any(isconstant, states′)
        csts = filter(isconstant, states′)
        throw(ArgumentError("Found one or more constant species among the states; this is "
                            * "not allowed. Move: $csts to be parameters."))
    end

    # if there are BC species, check they are balanced in their reactions
    if balanced_bc_check && any(isbc, states′)
        for rx in eqs
            isbcbalanced(rx) || throw(ErrorException("BC species must be balanced, appearing as a substrate and product with the same stoichiometry. Please fix reaction: $rx"))
        end
    end

    var_to_name = Dict()
    MT.process_variables!(var_to_name, defaults, states′)
    MT.process_variables!(var_to_name, defaults, ps′)
    MT.collect_var_to_name!(var_to_name, eq.lhs for eq in observed)

    nps = if networkproperties === nothing
        NetworkProperties{Int, get_speciestype(iv′, states′, systems, constraints)}()
    else
        networkproperties
    end

    ReactionSystem(eqs′, iv′, states′, ps′, var_to_name, observed, name, systems,
                   defaults, connection_type, constraints, nps, combinatoric_ratelaws;
                   checks = checks)
end

# Previous function called by the macro, but still avaiable for general use.
function ReactionSystem(rxs::Vector{<:Reaction}, iv; kwargs...)
    make_ReactionSystem_internal(rxs, iv, nothing, Vector{Num}(); kwargs...)
end

# search the symbolic expression for parameters or states
# and save in ps and sts respectively. vars is used to cache results
function findvars!(ps, sts, exprtosearch, t, vars)
    MT.get_variables!(vars, exprtosearch)
    for var in vars
        isequal(t,var) && continue
        if MT.isparameter(var)
            push!(ps, var)
        else
            push!(sts, var)
        end
    end
    empty!(vars)
end

# Only used internally by the @reaction_network macro. Permits giving an initial order to the parameters,
# and then adds additional ones found in the reaction. Name could be changed.
function make_ReactionSystem_internal(rxs::Vector{<:Reaction}, iv, no_sps::Nothing, ps_in; kwargs...)
    t    = value(iv)
    sts  = OrderedSet()
    ps   = OrderedSet{Any}(ps_in)
    vars = OrderedSet()

    # add species / parameters that are substrates / products first
    for rx in rxs, reactants in (rx.substrates, rx.products)
        for spec in reactants
            MT.isparameter(spec) ? push!(ps, spec) : push!(sts, spec)
        end
    end

    for rx in rxs
        findvars!(ps, sts, rx.rate, t, vars)
        for s in rx.substoich
            (s isa Symbolics.Symbolic) && findvars!(ps, sts, s, t, vars)
        end
        for p in rx.prodstoich
            (p isa Symbolics.Symbolic) && findvars!(ps, sts, p, t, vars)
        end
    end
    ReactionSystem(rxs, t, collect(sts), collect(ps); kwargs...)
end

function ReactionSystem(iv; kwargs...)
    ReactionSystem(Reaction[], iv, [], []; kwargs...)
end

####################### ModelingToolkit inherited accessors #############################

"""
    get_constraints(sys::ReactionSystem)

Return the current constraint subsystem, if none is defined will return `nothing`.
"""
get_constraints(sys::ReactionSystem) = getfield(sys, :constraints)
has_constraints(sys::ReactionSystem) = isdefined(sys, :constraints)

"""
    get_networkproperties(sys::ReactionSystem)

Return the current network properties of `sys`.
"""
get_networkproperties(sys::ReactionSystem) = getfield(sys, :networkproperties)

"""
    get_combinatoric_ratelaws(sys::ReactionSystem)

Returns true if the default for the system is to rescale ratelaws, see
https://catalyst.sciml.ai/dev/tutorials/using_catalyst/#Reaction-rate-laws-used-in-simulations
for details. Can be overriden via passing `combinatoric_ratelaws` to `convert` or the
`*Problem` functions.
"""
get_combinatoric_ratelaws(sys::ReactionSystem) = getfield(sys, :combinatoric_ratelaws)

function MT.states(sys::ReactionSystem)
    sts = (get_constraints(sys) === nothing) ? get_states(sys) : vcat(get_states(sys), get_states(get_constraints(sys)))
    systems = get_systems(sys)
    unique(isempty(systems) ? sts : [sts; reduce(vcat,namespace_variables.(systems))])
end

function MT.parameters(sys::ReactionSystem)
    ps = (get_constraints(sys) === nothing) ? get_ps(sys) : vcat(get_ps(sys), get_ps(get_constraints(sys)))
    systems = get_systems(sys)
    unique(isempty(systems) ? ps : [ps; reduce(vcat,namespace_parameters.(systems))])
end

function MT.equations(sys::ReactionSystem)
    eqs = (get_constraints(sys) === nothing) ? get_eqs(sys) : Any[get_eqs(sys); get_eqs(get_constraints(sys))]
    systems = get_systems(sys)
    if !isempty(systems)
        return Any[eqs; reduce(vcat, MT.namespace_equations.(systems); init=Any[])]
    end
    return eqs
end

"""
    combinatoric_ratelaws(sys::ReactionSystem)

Returns the effective (default) `combinatoric_ratelaw` value for a compositional system,
calculated by taking the logical or of each component `ReactionSystem`. Can be overriden
during calls to `convert` of problem constructors.
"""
function combinatoric_ratelaws(sys::ReactionSystem)
    crl = get_combinatoric_ratelaws(sys)
    subsys = Iterators.filter(s -> s isa ReactionSystem, get_systems(sys))
    mapreduce(combinatoric_ratelaws, |, subsys; init=crl)
end

function MT.defaults(sys::ReactionSystem)
    constraints = get_constraints(sys)
    systems = get_systems(sys)
    defs = get_defaults(sys)

    if constraints !== nothing
        defs = merge(defs, get_defaults(constraints))
    end

    mapfoldr(MT.namespace_defaults, merge, systems, init=defs)
end

function MT.observed(sys::ReactionSystem)
    constraints = get_constraints(sys)
    systems = get_systems(sys)
    obs = get_observed(sys)

    if constraints !== nothing
        obs = vcat(obs, get_observed(constraints))
    end
    reduce(vcat,
           (map(o->MT.namespace_equation(o,s), MT.observed(s)) for s in systems);
           init=obs)
end

function MT.getvar(sys::ReactionSystem, name::Symbol; namespace=false)
    if isdefined(sys, name)
        Base.depwarn("`sys.name` like `sys.$name` is deprecated. Use getters like `get_$name` instead.", "sys.$name")
        return getfield(sys, name)
    end

    systems = get_systems(sys)
    i = findfirst(x->nameof(x)==name, systems)
    i === nothing || return namespace ? rename(systems[i], renamespace(sys, name)) : systems[i]

    constraints = get_constraints(sys)
    if constraints !== nothing && nameof(constraints) == name
        return namespace ? rename(constraints, renamespace(sys, name)) : constraints
    end

    avs = get_var_to_name(sys)
    v = get(avs, name, nothing)
    v === nothing || return namespace ? renamespace(sys, v) : v

    sts = get_states(sys)
    i = findfirst(x->getname(x) == name, sts)
    i === nothing || return namespace ? renamespace(sys, sts[i]) : sts[i]

    ps = get_ps(sys)
    i = findfirst(x->getname(x) == name,ps)
    i === nothing || return namespace ? renamespace(sys, ps[i]) : ps[i]

    obs = get_observed(sys)
    i = findfirst(x->getname(x.lhs)==name,obs)
    i === nothing || return namespace ? renamespace(sys, obs[i]) : obs[i]

    if constraints !== nothing
        return getvar(rename(constraints, nameof(sys)), name; namespace=namespace)
    end

    throw(ArgumentError("System $(nameof(sys)): variable $name does not exist"))
end

# get the non-bc, independent state variables, preserving their relative order in
# get_states(rs). ASSUMES system has been validated to have no constant species as states.
function get_indep_sts(rs::ReactionSystem, remove_conserved=false)
    sts = get_states(rs)
    nps = get_networkproperties(rs)
    indepsts = if remove_conserved
        filter(s -> (s ∈ nps.indepspecs) && (!isbc(s)), sts)
    else
        filter(s -> !isbc(s), sts)
    end
    indepsts
end

######################## Conversion to ODEs/SDEs/jump, etc ##############################

"""
    oderatelaw(rx; combinatoric_ratelaw=true)

Given a [`Reaction`](@ref), return the symbolic reaction rate law used in
generated ODEs for the reaction. Note, for a reaction defined by

`k*X*Y, X+Z --> 2X + Y`

the expression that is returned will be `k*X(t)^2*Y(t)*Z(t)`. For a reaction of
the form

`k, 2X+3Y --> Z`

the expression that is returned will be `k * (X(t)^2/2) * (Y(t)^3/6)`.

Notes:
- Allocates
- `combinatoric_ratelaw=true` uses factorial scaling factors in calculating the
    rate law, i.e. for `2S -> 0` at rate `k` the ratelaw would be `k*S^2/2!`. If
    `combinatoric_ratelaw=false` then the ratelaw is `k*S^2`, i.e. the scaling
    factor is ignored.
"""
function oderatelaw(rx; combinatoric_ratelaw=true)
    @unpack rate, substrates, substoich, only_use_rate = rx
    rl = rate

    # if the stoichiometric coefficients are not integers error if asking to scale rates
    !all(s -> s isa Union{Integer,Symbolics.Symbolic}, substoich) && (combinatoric_ratelaw==true) &&
        error("Non-integer stoichiometric coefficients require the combinatoric_ratelaw=false keyword to oderatelaw, or passing combinatoric_ratelaws=false to convert or ODEProblem.")

    if !only_use_rate
        coef = eltype(substoich) <: Number ? one(eltype(substoich)) : 1
        for (i,stoich) in enumerate(substoich)
            combinatoric_ratelaw && (coef *= factorial(stoich))
            rl *= isequal(stoich,one(stoich)) ? substrates[i] : substrates[i]^stoich
        end
        combinatoric_ratelaw && (!isequal(coef,one(coef))) && (rl /= coef)
    end
    rl
end

function assemble_oderhs(rs, sts; combinatoric_ratelaws=true, remove_conserved=false)
    nps = get_networkproperties(rs)
    species_to_idx = Dict(x => i for (i,x) in enumerate(sts))
    rhsvec = Any[0 for _ in sts]
    depspec_submap = if remove_conserved
        Dict(eq.lhs => eq.rhs for eq in nps.conservedeqs)
    else
        Dict()
    end

    for rx in get_eqs(rs)
        rl = oderatelaw(rx; combinatoric_ratelaw=combinatoric_ratelaws)
        remove_conserved && (rl = substitute(rl, depspec_submap))
        for (spec,stoich) in rx.netstoich
            # dependent species don't get an ODE, so are skipped
            remove_conserved && (spec in nps.depspecs) && continue

            # constant or BC species also do not get equations
            drop_dynamics(spec) && continue

            i = species_to_idx[spec]
            if _iszero(rhsvec[i])
                if stoich isa Symbolics.Symbolic
                    rhsvec[i] = stoich * rl
                else
                    signedrl  = (stoich > zero(stoich)) ? rl : -rl
                    rhsvec[i] = isone(abs(stoich)) ? signedrl : stoich * rl
                end
            else
                if stoich isa Symbolics.Symbolic
                    rhsvec[i] += stoich * rl
                else
                    Δspec     = isone(abs(stoich)) ? rl : abs(stoich) * rl
                    rhsvec[i] = (stoich > zero(stoich)) ? (rhsvec[i] + Δspec) : (rhsvec[i] - Δspec)
                end
            end
        end
    end

    rhsvec
end

function assemble_drift(rs, sts; combinatoric_ratelaws=true, as_odes=true, include_zero_odes=true,
                            remove_conserved=false)
    rhsvec = assemble_oderhs(rs, sts; combinatoric_ratelaws, remove_conserved)
    if as_odes
        D = Differential(get_iv(rs))
        eqs = [Equation(D(x),rhs) for (x,rhs) in zip(sts,rhsvec) if (include_zero_odes || (!_iszero(rhs)))]
    else
        eqs = [Equation(0,rhs) for rhs in rhsvec if (include_zero_odes || (!_iszero(rhs)))]
    end
    eqs
end

function assemble_diffusion(rs, sts, noise_scaling; combinatoric_ratelaws=true,
                                                    remove_conserved=false)
    # as BC species should ultimately get an equation, we include them in the noise matrix
    num_bcsts = count(isbc, get_states(rs))
    eqs  = Matrix{Any}(undef, length(sts) + num_bcsts, length(get_eqs(rs)))
    eqs .= 0
    species_to_idx = Dict((x => i for (i,x) in enumerate(sts)))
    nps = get_networkproperties(rs)
    depspec_submap = if remove_conserved
        Dict(eq.lhs => eq.rhs for eq in nps.conservedeqs)
    else
        Dict()
    end

    for (j,rx) in enumerate(get_eqs(rs))
        rlsqrt = sqrt(abs(oderatelaw(rx; combinatoric_ratelaw=combinatoric_ratelaws)))
        (noise_scaling!==nothing) && (rlsqrt *= noise_scaling[j])
        remove_conserved && (rlsqrt = substitute(rlsqrt, depspec_submap))

        for (spec,stoich) in rx.netstoich
            # dependent species don't get an equation
            remove_conserved && (spec in nps.depspecs) && continue

            # constant or BC species also do not get equations
            drop_dynamics(spec) && continue

            i = species_to_idx[spec]
            if stoich isa Symbolics.Symbolic
                eqs[i,j] = stoich * rlsqrt
            else
                signedrlsqrt = (stoich > zero(stoich)) ? rlsqrt : -rlsqrt
                eqs[i,j]     = isone(abs(stoich)) ? signedrlsqrt : stoich * rlsqrt
            end
        end
    end
    eqs
end

"""
    jumpratelaw(rx; combinatoric_ratelaw=true)

Given a [`Reaction`](@ref), return the symbolic reaction rate law used in
generated stochastic chemical kinetics model SSAs for the reaction. Note,
for a reaction defined by

`k*X*Y, X+Z --> 2X + Y`

the expression that is returned will be `k*X^2*Y*Z`. For a reaction of
the form

`k, 2X+3Y --> Z`

the expression that is returned will be `k * binomial(X,2) *
binomial(Y,3)`.

Notes:
- Allocates
- `combinatoric_ratelaw=true` uses binomials in calculating the rate law, i.e. for `2S ->
  0` at rate `k` the ratelaw would be `k*S*(S-1)/2`. If `combinatoric_ratelaw=false` then
  the ratelaw is `k*S*(S-1)`, i.e. the rate law is not normalized by the scaling
  factor.
"""
function jumpratelaw(rx; combinatoric_ratelaw=true)
    @unpack rate, substrates, substoich, only_use_rate = rx
    rl = rate
    if !only_use_rate
        coef = eltype(substoich) <: Number ? one(eltype(substoich)) : 1
        for (i,stoich) in enumerate(substoich)
            s = substrates[i]
            if stoich isa Symbolics.Symbolic
                rl *= combinatoric_ratelaw ? binomial(s,stoich) : factorial(s) / factorial(s-stoich)
            else
                rl *= s
                isone(stoich) && continue
                for i in one(stoich):(stoich-one(stoich))
                    rl *= (s - i)
                end
                combinatoric_ratelaw && (coef *= factorial(stoich))
            end
        end
        combinatoric_ratelaw && !isequal(coef,one(coef)) && (rl /= coef)
    end
    rl
end

# if haveivdep=false then time dependent rates will still be classified as mass action
"""
```julia
ismassaction(rx, rs; rxvars = get_variables(rx.rate),
                              haveivdep = any(var -> isequal(get_iv(rs),var), rxvars),
                              stateset = Set(states(rs)))
```

True if a given reaction is of mass action form, i.e. `rx.rate` does not depend
on any chemical species that correspond to states of the system, and does not
depend explicitly on the independent variable (usually time).

# Arguments
- `rx`, the [`Reaction`](@ref).
- `rs`, a [`ReactionSystem`](@ref) containing the reaction.
- Optional: `rxvars`, `Variable`s which are not in `rxvars` are ignored as
  possible dependencies.
- Optional: `haveivdep`, `true` if the [`Reaction`](@ref) `rate` field
  explicitly depends on the independent variable.
- Optional: `stateset`, set of states which if the rxvars are within mean rx is
  non-mass action.

Notes:
- Non-integer stoichiometry is treated as non-mass action. This includes
  symbolic variables/terms or floating point numbers for stoichiometric
  coefficients.
"""
function ismassaction(rx, rs; rxvars = get_variables(rx.rate),
                              haveivdep = any(var -> isequal(get_iv(rs),var), rxvars),
                              stateset = Set(get_states(rs)))

    # we define non-integer (i.e. float or symbolic) stoich to be non-mass action
    ((eltype(rx.substoich) <: Integer) && (eltype(rx.prodstoich) <: Integer)) || return false

    # if no dependencies must be zero order
    (length(rxvars)==0) && return true
    haveivdep && return false
    rx.only_use_rate && return false
    @inbounds for var in rxvars
        # not mass action if have a non-constant, variable species in the rate expression
        (var in stateset) && return false
    end

    return true
end

@inline function makemajump(rx; combinatoric_ratelaw=true)
    @unpack rate, substrates, substoich, netstoich = rx
    zeroorder = (length(substoich) == 0)
    reactant_stoch = Vector{Pair{Any,eltype(substoich)}}()
    @inbounds for (i,spec) in enumerate(substrates)
        # move constant species into the rate
        if isconstant(spec)
            rate *= spec
            isone(substoich[i]) && continue
            for i = 1:(substoich[i]-1)
                rate *= spec - i
            end
        else
            push!(reactant_stoch, substrates[i] => substoich[i])
        end
    end

    if (!zeroorder) && combinatoric_ratelaw
        coef = prod(factorial, substoich)
        (!isone(coef)) && (rate /= coef)
    end

    net_stoch = filter(p -> !drop_dynamics(p[1]), netstoich)
    if isempty(net_stoch)
        error("$rx has no net stoichiometry change once accounting for "
              * "constant and boundary condition species. This is not supported.")
    end

    MassActionJump(Num(rate), reactant_stoch, net_stoch, scale_rates=false, useiszero=false)
end

function assemble_jumps(rs; combinatoric_ratelaws=true)
    meqs = MassActionJump[]; ceqs = ConstantRateJump[]; veqs = VariableRateJump[]
    stateset = Set(get_states(rs))
    rxvars = []

    isempty(get_eqs(rs)) && error("Must give at least one reaction before constructing a JumpSystem.")
    for rx in get_eqs(rs)
        empty!(rxvars)
        (rx.rate isa Symbolic) && get_variables!(rxvars, rx.rate)
        haveivdep = false
        @inbounds for rxvar in rxvars
            if isequal(rxvar, get_iv(rs))
                haveivdep = true
                break
            end
        end
        if ismassaction(rx, rs; rxvars=rxvars, haveivdep=haveivdep, stateset=stateset)
            push!(meqs, makemajump(rx, combinatoric_ratelaw=combinatoric_ratelaws))
        else
            rl = jumpratelaw(rx, combinatoric_ratelaw=combinatoric_ratelaws)
            affect = Vector{Equation}()
            for (spec,stoich) in rx.netstoich
                # don't change species that are constant or BCs
                (!drop_dynamics(spec)) && push!(affect, spec ~ spec + stoich)
            end
            if haveivdep
                push!(veqs, VariableRateJump(rl,affect))
            else
                push!(ceqs, ConstantRateJump(rl,affect))
            end
        end
    end
    vcat(meqs,ceqs,veqs)
end

# convert subsystems to the system type T
# function make_systems_with_type!(systems::Vector{T}, rs::ReactionSystem, include_zero_odes=true) where {T <: MT.AbstractSystem}
#     resize!(systems, length(get_systems(rs)))
#     for (i,sys) in enumerate(get_systems(rs))
#         if sys isa ReactionSystem
#             systems[i] = convert(T, sys, include_zero_odes=include_zero_odes)
#         elseif sys isa T
#             systems[i] = sys
#         else
#             try
#                 if (T <: MT.AbstractTimeDependentSystem) && (sys isa MT.AbstractTimeIndependentSystem)
#                     systems[i] = MT.convert_system(T, sys, get_iv(rs))
#                 else
#                     systems[i] = MT.convert_system(T, sys)
#                 end
#             catch e
#                 error("ModelingToolkit does not currently support convert_system($T, $(typeof(sys)))")
#             end
#         end
#     end
#     systems
# end

# merge constraint components with the ReactionSystem components
# also handles removing BC and constant species
function addconstraints!(eqs, rs::ReactionSystem, ists; remove_conserved=false)
    # if there are BC species, put them after the independent species
    rssts = get_states(rs)
    sts = any(isbc, rssts) ? vcat(ists, filter(isbc, rssts)) : ists
    ps = get_ps(rs)

    # make dependent species observables and add conservation constants as parameters
    if remove_conserved
        nps = get_networkproperties(rs)

        # add the conservation constants as parameters and set their values
        ps = vcat(ps, collect(eq.lhs for eq in nps.constantdefs))
        defs = copy(MT.defaults(rs))
        for eq in nps.constantdefs
            defs[eq.lhs] = eq.rhs
        end

        # add the dependent species as observed
        obs = copy(MT.observed(rs))
        append!(obs, nps.conservedeqs)
    else
        defs = MT.defaults(rs)
        obs = MT.observed(rs)
    end

    csys = get_constraints(rs)
    if csys !== nothing
        if remove_conserved
            @info """
                  Be careful mixing constraints and elimination of conservation laws. We do
                  not check that the conserved equations still hold for the final coupled
                  system of equations. Consider using remove_conserved=false and instead
                  calling ModelingToolkit.structural_simplify to simplify any generated
                  ODESystem or NonlinearSystem.
                  """
        end

        # merge in states of csys
        csts = get_states(csys)
        if any(isconstant, csts)
            const_csts = filter(isconstant, csts)
            error("""Found a constant species among the states of the constraint system.
                    This is not allowed. Please make the following species parameters with
                    the isconstantspecies metadata set: $const_csts.""")
        end
        sts = unique!(vcat(sts, csts))

        # merge constant species that are only in the constraints into parameters
        if !all(MT.isparameter, get_ps(csys))
            nonps = filter(!MT.isparameter, get_ps(csys))
            error("""Found constraint system parameters that were not created as
                     ModelingToolkit parameters: $nonps.""")
        end
        ps = unique!(vcat(ps, get_ps(csys)))

        ceqs = get_eqs(csys)
        (!isempty(ceqs)) && append!(eqs,ceqs)
        defs = merge(defs, MT.defaults(csys))
        obs = vcat(obs, MT.observed(csys))
    end

    eqs,sts,ps,obs,defs
end

# used by systems that don't support constraint equations currently
function error_if_constraints(::Type{T}, sys::ReactionSystem) where {T <: MT.AbstractSystem}
    (get_constraints(sys) === nothing) ||
            error("Can not convert to a system of type ", T, " when there are constraints.")
end

function error_if_constraint_odes(::Type{T}, rs::ReactionSystem) where {T <: MT.AbstractSystem}
    csys = get_constraints(rs)
    if csys !== nothing
        any(eq -> MT.isdiffeq(eq), equations(csys)) &&
            error("Cannot convert to system type $T when there are ODE constraint equations.")
    end
    nothing
end

"""
```julia
Base.convert(::Type{<:ODESystem},rs::ReactionSystem)
```
Convert a [`ReactionSystem`](@ref) to an `ModelingToolkit.ODESystem`.

Keyword args and default values:
- `combinatoric_ratelaws=true` uses factorial scaling factors in calculating the rate law,
  i.e. for `2S -> 0` at rate `k` the ratelaw would be `k*S^2/2!`. Set
  `combinatoric_ratelaws=false` for a ratelaw of `k*S^2`, i.e. the scaling factor is
  ignored. Defaults to the value given when the `ReactionSystem` was constructed (which
  itself defaults to true).
- `remove_conserved=false`, if set to `true` will calculate conservation laws of the
  underlying set of reactions (ignoring constraint equations), and then apply them to reduce
  the number of equations.
"""
function Base.convert(::Type{<:ODESystem}, rs::ReactionSystem;
                      name=nameof(rs), combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                      include_zero_odes=true, remove_conserved=false, checks=false, kwargs...)
    fullrs = Catalyst.flatten(rs)
    remove_conserved && conservationlaws(fullrs)
    ists = get_indep_sts(fullrs, remove_conserved)
    eqs = assemble_drift(fullrs, ists; combinatoric_ratelaws, remove_conserved,
                                      include_zero_odes)
    eqs,sts,ps,obs,defs = addconstraints!(eqs, fullrs, ists; remove_conserved)
    csys = get_constraints(fullrs)
    continuous_events = (csys === nothing) ? nothing : MT.get_continuous_events(csys)
    ODESystem(eqs, get_iv(fullrs), sts, ps; name, defaults=defs, observed=obs,
                                            checks, continuous_events, kwargs...)
end

"""
```julia
Base.convert(::Type{<:NonlinearSystem},rs::ReactionSystem)
```

Convert a [`ReactionSystem`](@ref) to an `ModelingToolkit.NonlinearSystem`.

Keyword args and default values:
- `combinatoric_ratelaws=true` uses factorial scaling factors in calculating the rate law,
  i.e. for `2S -> 0` at rate `k` the ratelaw would be `k*S^2/2!`. Set
  `combinatoric_ratelaws=false` for a ratelaw of `k*S^2`, i.e. the scaling factor is
  ignored. Defaults to the value given when the `ReactionSystem` was constructed (which
  itself defaults to true).
- `remove_conserved=false`, if set to `true` will calculate conservation laws of the
  underlying set of reactions (ignoring constraint equations), and then apply them to reduce
  the number of equations.
"""
function Base.convert(::Type{<:NonlinearSystem}, rs::ReactionSystem;
                      name=nameof(rs), combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                      include_zero_odes=true, remove_conserved=false, checks=false, kwargs...)
    fullrs = Catalyst.flatten(rs)
    remove_conserved && conservationlaws(fullrs)
    ists = get_indep_sts(fullrs, remove_conserved)
    eqs = assemble_drift(fullrs, ists; combinatoric_ratelaws, remove_conserved, as_odes=false,
                                      include_zero_odes)
    error_if_constraint_odes(NonlinearSystem, fullrs)
    eqs,sts,ps,obs,defs = addconstraints!(eqs, fullrs, ists; remove_conserved)
    NonlinearSystem(eqs, sts, ps; name, defaults=defs, observed=obs, checks, kwargs...)
end

"""
```julia
Base.convert(::Type{<:SDESystem},rs::ReactionSystem)
```

Convert a [`ReactionSystem`](@ref) to an `ModelingToolkit.SDESystem`.

Notes:
- `combinatoric_ratelaws=true` uses factorial scaling factors in calculating the rate law,
  i.e. for `2S -> 0` at rate `k` the ratelaw would be `k*S^2/2!`. Set
  `combinatoric_ratelaws=false` for a ratelaw of `k*S^2`, i.e. the scaling factor is
  ignored. Defaults to the value given when the `ReactionSystem` was constructed (which
  itself defaults to true).
- `noise_scaling=nothing::Union{Vector{Num},Num,Nothing}` allows for linear scaling of the
  noise in the chemical Langevin equations. If `nothing` is given, the default value as in
  Gillespie 2000 is used. Alternatively, a `Num` can be given, this is added as a parameter
  to the system (at the end of the parameter array). All noise terms are linearly scaled
  with this value. The parameter may be one already declared in the `ReactionSystem`.
  Finally, a `Vector{Num}` can be provided (the length must be equal to the number of
  reactions). Here the noise for each reaction is scaled by the corresponding parameter in
  the input vector. This input may contain repeat parameters.
- `remove_conserved=false`, if set to `true` will calculate conservation laws of the
  underlying set of reactions (ignoring constraint equations), and then apply them to reduce
  the number of equations.
"""
function Base.convert(::Type{<:SDESystem}, rs::ReactionSystem;
                      noise_scaling=nothing, name=nameof(rs),
                      combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                      include_zero_odes=true, checks = false, remove_conserved=false,
                      kwargs...)

    flatrs = Catalyst.flatten(rs)
    error_if_constraints(SDESystem, flatrs)

    if noise_scaling isa AbstractArray
        (length(noise_scaling)!=numreactions(flatrs)) &&
        error("The number of elements in 'noise_scaling' must be equal " *
              "to the number of reactions in the flattened reaction system.")
        if !(noise_scaling isa Symbolics.Arr)
            noise_scaling = value.(noise_scaling)
        end
    elseif !isnothing(noise_scaling)
        noise_scaling = fill(value(noise_scaling),numreactions(flatrs))
    end

    remove_conserved && conservationlaws(flatrs)
    ists = get_indep_sts(flatrs, remove_conserved)
    eqs = assemble_drift(flatrs, ists; combinatoric_ratelaws, include_zero_odes,
                                       remove_conserved)
    noiseeqs = assemble_diffusion(flatrs, ists, noise_scaling; combinatoric_ratelaws,
                                                               remove_conserved)
    eqs,sts,ps,obs,defs = addconstraints!(eqs, flatrs, ists; remove_conserved)
    ps = (noise_scaling===nothing) ? ps : vcat(ps,toparam(noise_scaling))

    if any(isbc, get_states(flatrs))
        @info "Boundary condition species detected. As constraints are not supported when converting to SDESystems, the resulting system will be undetermined. Consider using constant species instead."
    end

    SDESystem(eqs, noiseeqs, get_iv(flatrs), sts, ps; name, defaults=defs,
                                                      observed=obs, checks, kwargs...)
end

"""
```julia
Base.convert(::Type{<:JumpSystem},rs::ReactionSystem; combinatoric_ratelaws=true)
```

Convert a [`ReactionSystem`](@ref) to an `ModelingToolkit.JumpSystem`.

Notes:
- `combinatoric_ratelaws=true` uses binomials in calculating the rate law, i.e. for `2S ->
  0` at rate `k` the ratelaw would be `k*S*(S-1)/2`. If `combinatoric_ratelaws=false` then
  the ratelaw is `k*S*(S-1)`, i.e. the rate law is not normalized by the scaling factor.
  Defaults to the value given when the `ReactionSystem` was constructed (which itself
  defaults to true).
"""
function Base.convert(::Type{<:JumpSystem},rs::ReactionSystem;
                      name=nameof(rs), combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                      checks = false, kwargs...)

    flatrs = Catalyst.flatten(rs)
    error_if_constraints(JumpSystem, flatrs)

    eqs = assemble_jumps(flatrs; combinatoric_ratelaws)

    # handle BC species
    sts = get_indep_sts(flatrs)
    any(isbc, get_states(flatrs)) && (sts = vcat(sts, filter(isbc, get_states(flatrs))))
    ps = get_ps(flatrs)

    JumpSystem(eqs, get_iv(flatrs), sts, ps; name, defaults=MT.defaults(flatrs),
                                            observed=MT.observed(flatrs), checks, kwargs...)
end

### Converts a reaction system to ODE or SDE problems ###

# ODEProblem from AbstractReactionNetwork
function DiffEqBase.ODEProblem(rs::ReactionSystem, u0, tspan, p=DiffEqBase.NullParameters(), args...;
                               check_length=false, name=nameof(rs),
                               combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                               include_zero_odes=true, remove_conserved=false, checks=false,
                               kwargs...)
    u0map = symmap_to_varmap(rs, u0)
    pmap  = symmap_to_varmap(rs, p)
    osys  = convert(ODESystem, rs; name, combinatoric_ratelaws, include_zero_odes, checks,
                                   remove_conserved)
    return ODEProblem(osys, u0map, tspan, pmap, args...; check_length, kwargs...)
end

# NonlinearProblem from AbstractReactionNetwork
function DiffEqBase.NonlinearProblem(rs::ReactionSystem, u0, p=DiffEqBase.NullParameters(), args...;
                                     name=nameof(rs), include_zero_odes=true,
                                     combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                                     remove_conserved=false, checks = false,
                                     check_length=false, kwargs...)
    u0map = symmap_to_varmap(rs, u0)
    pmap  = symmap_to_varmap(rs, p)
    nlsys = convert(NonlinearSystem, rs; name, combinatoric_ratelaws, include_zero_odes,
                                         checks, remove_conserved)
    return NonlinearProblem(nlsys, u0map, pmap, args...; check_length, kwargs...)
end

# SDEProblem from AbstractReactionNetwork
function DiffEqBase.SDEProblem(rs::ReactionSystem, u0, tspan, p=DiffEqBase.NullParameters(), args...;
                               noise_scaling=nothing, name=nameof(rs),
                               combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                               include_zero_odes=true, checks = false, check_length=false,
                               remove_conserved=false, kwargs...)
    u0map = symmap_to_varmap(rs, u0)
    pmap  = symmap_to_varmap(rs, p)
    sde_sys  = convert(SDESystem, rs; noise_scaling, name, combinatoric_ratelaws,
                                      include_zero_odes, checks, remove_conserved)
    p_matrix = zeros(length(get_states(sde_sys)), numreactions(rs))
    return SDEProblem(sde_sys, u0map, tspan, pmap, args...; check_length,
                                                            noise_rate_prototype=p_matrix, kwargs...)
end

# DiscreteProblem from AbstractReactionNetwork
function DiffEqBase.DiscreteProblem(rs::ReactionSystem, u0, tspan::Tuple, p=DiffEqBase.NullParameters(),
                                    args...; name=nameof(rs),
                                    combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                                    checks = false, kwargs...)
    u0map = symmap_to_varmap(rs, u0)
    pmap  = symmap_to_varmap(rs, p)
    jsys  = convert(JumpSystem, rs; name, combinatoric_ratelaws, checks)
    return DiscreteProblem(jsys, u0map, tspan, pmap, args...; kwargs...)
end

# JumpProblem from AbstractReactionNetwork
function DiffEqJump.JumpProblem(rs::ReactionSystem, prob, aggregator, args...;
                                name=nameof(rs),
                                combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                                checks = false, kwargs...)
    jsys = convert(JumpSystem, rs; name, combinatoric_ratelaws, checks)
    return JumpProblem(jsys, prob, aggregator, args...; kwargs...)
end

# SteadyStateProblem from AbstractReactionNetwork
function DiffEqBase.SteadyStateProblem(rs::ReactionSystem, u0, p=DiffEqBase.NullParameters(), args...;
                                       check_length=false, name=nameof(rs),
                                       combinatoric_ratelaws=get_combinatoric_ratelaws(rs),
                                       remove_conserved=false, include_zero_odes=true,
                                       checks=false, kwargs...)
    u0map = symmap_to_varmap(rs, u0)
    pmap = symmap_to_varmap(rs, p)
    osys = convert(ODESystem, rs; name, combinatoric_ratelaws, include_zero_odes, checks,
                                  remove_conserved)
    return SteadyStateProblem(osys, u0map, pmap, args...; check_length, kwargs...)
end

####################### dependency graph utilities ########################

# determine which species a reaction depends on
function ModelingToolkit.get_variables!(deps::Set, rx::Reaction, variables)
    (rx.rate isa Symbolic) && get_variables!(deps, rx.rate, variables)
    for s in rx.substrates
        push!(deps, s)
    end
    deps
end

# determine which species a reaction modifies
function ModelingToolkit.modified_states!(mstates, rx::Reaction, sts::Set)
    for (species,stoich) in rx.netstoich
        (species in sts) && push!(mstates, species)
    end
    mstates
end

########################## Compositional Tooling ###########################
function getsubsyseqs!(eqs::Vector{Equation}, sys)
    if sys isa ReactionSystem
        push!(eqs, get_eqs(get_constraints(sys)))
    else
        push!(eqs, get_eqs(sys))
    end

    for subsys in get_systems(sys)
        getsubsyseqs!(eqs, subsys)
    end
    eqs
end
function getsubsyseqs(sys)
    getsubsyseqs!(Vector{Equation}(), sys)
end

function getsubsystypes!(typeset::Set{Type}, sys::T) where {T <: MT.AbstractSystem}
    push!(typeset, T)
    csys = (sys isa ReactionSystem) ? get_constraints(sys) : nothing
    csys !== nothing && getsubsystypes!(typeset, csys)
    for subsys in get_systems(sys)
        getsubsystypes!(typeset, subsys)
    end
    typeset
end
function getsubsystypes(sys)
    typeset = Set{Type}()
    getsubsystypes!(typeset, sys)
    typeset
end

"""
    Catalyst.flatten(rs::ReactionSystem)

Merges all subsystems of the given [`ReactionSystem`](@ref) up into `rs`.

Notes:
- Returns a new `ReactionSystem` that represents the flattened system.
- All `Reaction`s within subsystems are namespaced and merged into the list of `Reactions`
  of `rs`. The merged list is then available as `reactions(rs)` or `get_eqs(rs)`.
- All algebraic equations are merged into a `NonlinearSystem` or `ODESystem` stored as
  `get_constraints(rs)`. If `get_constraints !== nothing` then the algebraic equations are
  merged with the current constraints in a system of the same type as the current
  constraints, otherwise the new constraint system is an `ODESystem`.
- Currently only `ReactionSystem`s, `NonlinearSystem`s and `ODESystem`s are supported as
  sub-systems when flattening.
- `rs.networkproperties` is reset upon flattening.
- The default value of `combinatoric_ratelaws` will be the logical or of all
  `ReactionSystem`s.
"""
function MT.flatten(rs::ReactionSystem; name=nameof(rs))

    isempty(get_systems(rs)) && return rs

    # right now only NonlinearSystems and ODESystems can be handled as subsystems
    subsys_types  = getsubsystypes(rs)
    allowed_types = (ReactionSystem, NonlinearSystem, ODESystem)
    all(T -> any(T .<: allowed_types), subsys_types) ||
        error("flattening is currently only supported for subsystems mixing ReactionSystems, NonlinearSystems and ODESystems.")

    specs      = species(rs)
    sts        = states(rs)
    reactionps = reactionparams(rs)
    ps         = parameters(rs)
    alleqs     = equations(rs)
    rxs        = Reaction[rx for rx in alleqs if rx isa Reaction]
    combinatoric_ratelaws = Catalyst.combinatoric_ratelaws(rs)

    # constraints = states, parameters and equations that do not appear in Reactions
    csts = setdiff(sts, specs)
    cps  = setdiff(ps, reactionps)
    ceqs = Equation[eq for eq in alleqs if eq isa Equation]
    if isempty(csts) && isempty(cps) && isempty(ceqs)
        newcsys = nothing
    else
        if ODESystem in subsys_types
            newcsys = ODESystem(ceqs, get_iv(rs), csts, cps; name=name)
        else # must be a NonlinearSystem
            any(T -> T <: NonlinearSystem, subsys_types) ||
                error("Error, found constraint Equations but no ODESystem or NonlinearSystem associated with them.")
            newcsys = NonlinearSystem(ceqs, csts, cps; name=name)
        end
    end

    ReactionSystem(rxs, get_iv(rs), specs, reactionps; observed = MT.observed(rs),
                                                       name,
                                                       defaults = MT.defaults(rs),
                                                       checks = false,
                                                       constraints = newcsys,
                                                       combinatoric_ratelaws)
end

"""
    ModelingToolkit.extend(sys::Union{NonlinearSystem,ODESystem}, rs::ReactionSystem; name::Symbol=nameof(sys))

Extends the indicated [`ReactionSystem`](@ref) with a
`ModelingToolkit.NonlinearSystem` or `ModelingToolkit.ODESystem`, which will be
stored internally as constraint equations.

Notes:
- Returns a new `ReactionSystem` and does not modify `rs`.
- By default, the new `ReactionSystem` will have the same name as `sys`.
"""
function ModelingToolkit.extend(sys::Union{NonlinearSystem,ODESystem}, rs::ReactionSystem; name::Symbol=nameof(sys))
    csys = (get_constraints(rs) === nothing) ? sys : extend(sys, get_constraints(rs))
    combinatoric_ratelaws = get_combinatoric_ratelaws(rs)
    ReactionSystem(get_eqs(rs), get_iv(rs), get_states(rs), get_ps(rs);
                    observed = get_observed(rs), name = name,
                    systems = get_systems(rs), defaults = get_defaults(rs),
                    checks=false, constraints=csys, combinatoric_ratelaws)
end

"""
    ModelingToolkit.extend(sys::ReactionSystem, rs::ReactionSystem; name::Symbol=nameof(sys))

Extends the indicated [`ReactionSystem`](@ref) with another `ReactionSystem`.
Similar to calling `merge!` except constraint systems are allowed (and will also
be merged together).

Notes:
- Returns a new `ReactionSystem` and does not modify `rs`.
- By default, the new `ReactionSystem` will have the same name as `sys`.
"""
function ModelingToolkit.extend(sys::ReactionSystem, rs::ReactionSystem; name::Symbol=nameof(sys))
    eqs  = union(get_eqs(rs), get_eqs(sys))
    sts  = union(get_states(rs), get_states(sys))
    ps   = union(get_ps(rs), get_ps(sys))
    obs  = union(get_observed(rs), get_observed(sys))
    defs = merge(get_defaults(rs), get_defaults(sys)) # prefer `sys`
    syss = union(get_systems(rs), get_systems(sys))
    combinatoric_ratelaws = Catalyst.get_combinatoric_ratelaws(sys) |
                            Catalyst.get_combinatoric_ratelaws(rs)

    csys = get_constraints(rs)
    csys2 = get_constraints(sys)
    if csys === nothing
        newcsys = csys2
    else
        newcsys = (csys2 === nothing) ? csys : extend(csys2, csys, name)
    end

    ReactionSystem(eqs, get_iv(rs), sts, ps; observed = obs, name = name,
                    systems = syss, defaults = defs, checks=false, constraints=newcsys,
                    combinatoric_ratelaws)
end


text:
@testset "33.search-in-rotated-sorted-array.jl" begin
    @test search_in_rotated_array([4, 5, 6, 7, 0, 1, 2], 0) == 4
    @test search_in_rotated_array([4, 5, 6, 7, 0, 1, 2], 2) == 6
    @test search_in_rotated_array([4, 5, 6, 7, 0, 1, 2], 3) == -1
    @test search_in_rotated_array([1], 0) == -1
end


text:
#! /usr/bin/env julia

using PolygonClipping
pc = PolygonClipping
using Base.Test
using Lint

# Test Doubly linked list
println("Testing Polygon Structure...")
poly = Polygon()
vert1 = Vertex(1,2)
push!(poly, vert1)
for i = 1:10
    push!(poly, Vertex(rand(2)))
end
# Test iterator
i = 0
for vert in poly
    i += 1
end
@test i == 11
@test length(poly) == 11

vert1 = poly.start
vert2 = vert1.next
for i = 1:10
    @test vert1 === vert2.prev
    vert1 = vert1.next
    vert2 = vert2.next
end

println("Testing vertex constructors...")
vert1 = Vertex(0,0)
vert2 = Vertex(2,1)
poly = Polygon()
push!(poly, vert1)
push!(poly, vert2)
a = Vertex(poly.start, poly.start.next, 0.25)
@test a.location == [0.5,0.25]
@test poly.start === vert1
@test a.prev === vert1
@test a.next === vert2
@test vert1.next === a
@test vert2.prev === a

# test isinside method
println("Testing point in polygon...")
poly1 = Polygon()
push!(poly1, Vertex(0,0))
push!(poly1, Vertex(1,0))
push!(poly1, Vertex(1,1))
push!(poly1, Vertex(0,1))
@test isinside(Vertex(0.5,0.5), poly1) == true
@test isinside(Vertex(-0.5,0.5), poly1) == false
@test_throws VertexException isinside(Vertex(0,0), poly1)
@test_throws VertexException isinside(Vertex(1,0), poly1)
@test_throws EdgeException isinside(Vertex(0.5,0.0), poly1)
for i = 1:100
    @test isinside(Vertex(rand(2)), poly1) == true
end

# add non-convexity
push!(poly1, Vertex(0.9,0.5))
@test isinside(Vertex(0.9,0.9), poly1) == true
@test isinside(Vertex(0.9,0.9), poly1) == true
@test isinside(Vertex(0.99,0.1), poly1) == true
@test isinside(Vertex(0.99,0.5), poly1) == true
@test isinside(Vertex(0.9,0.1), poly1) == true

# add self-intersection
push!(poly1, Vertex(1.1, 0.25))
@test isinside(Vertex(1.09,0.25), poly1) == true
@test isinside(Vertex(1.09,0.26), poly1) == true
@test isinside(Vertex(0.9,0.25), poly1) == false
@test isinside(Vertex(0.9,0.05), poly1) == true
@test isinside(Vertex(0.9,0.9), poly1) == true

println("Testing line intersection method...")
@test (intersection(Vertex(0,0), Vertex(1,1), Vertex(1,0), Vertex(0,1))
        == (true, 0.5, 0.5))
@test (intersection(Vertex(0,0), Vertex(1,1), Vertex(1/2,0), Vertex(0,1/2))
        == (true, 0.25, 0.5))
@test (intersection(Vertex(0,0), Vertex(2,2), Vertex(1/2,0), Vertex(0,1/2))
        == (true, 0.125, 0.5))
@test (intersection(Vertex(0,0), Vertex(0,1), Vertex(1,0), Vertex(1,1))
        == (false, 0, 0))
@test (intersection(Vertex(0.5,0), Vertex(0.5,1), Vertex(0,0.5), Vertex(1,0.5))
        == (true, 0.5, 0.5))
@test (intersection(Vertex(0,0), Vertex(1,1), Vertex(0,0), Vertex(-1,-1))
        == (false, 0, 0))
@test (intersection(Vertex(0,0), Vertex(0,0), Vertex(1,1), Vertex(1,1))
        == (false, 0, 0))
@test (intersection(Vertex(0,0), Vertex(1,0), Vertex(0.25,0.5), Vertex(0.25,-0.5))
        == (true, 0.25, 0.5))
@test (intersection(Vertex(1,0), Vertex(0,0), Vertex(0.25,0.5), Vertex(0.25,-0.5))
        == (true, 0.75, 0.5))
@test (intersection(Vertex(0,0), Vertex(1,0), Vertex(0.25,-0.5), Vertex(0.25,0.25))
        == (true, 0.25, 2/3))
@test (intersection(Vertex(0,0), Vertex(1,0), Vertex(0.25,0.25), Vertex(0.25,-0.5))
        == (true, 0.25, 1/3))
@test (intersection(Vertex(0,0), Vertex(1,0), Vertex(1.5,0.5), Vertex(1.5,-0.5))
        == (false, 0, 0))
@test_throws DegeneracyException intersection(Vertex(0,0), Vertex(1,0), Vertex(0.5,0), Vertex(0.5,1.0))

println("Testing Vertex insertion")
vert1 = Vertex(0,0)
vert2 = Vertex(1,1)
vert3 = Vertex(vert1, vert2, 0.25)
@test vert3.next === vert2
@test vert3.prev === vert1
@test vert3.location == [0.25,0.25]
vert3 = Vertex(vert2, vert1, 0.25)
@test vert3.next === vert1
@test vert3.prev === vert2
@test vert3.location == [0.75,0.75]

println("Testing unprocessed")
poly1 = Polygon()
push!(poly1, Vertex(0,0))
push!(poly1, Vertex(1,0))
push!(poly1, Vertex(1,1))
push!(poly1, Vertex(0,1))
@test unprocessed(poly1) == false
poly1.start.next.intersect = true
@test unprocessed(poly1) == true
poly1.start.next.visited = true
@test unprocessed(poly1) == false

println("Testing remove vertices")
poly1 = Polygon()
vert1 = Vertex(0,1)
push!(poly1, vert1)
@test length(poly1) == 1
@test is(poly1.start, vert1)
remove(vert1, poly1)
@test length(poly1) == 0
@test is(poly1.start, nothing)
@test is(vert1.next, nothing)
@test is(vert1.prev, nothing)
push!(poly1, vert1)
vert2 = Vertex(1,1)
push!(poly1, vert2)
push!(poly1, Vertex(1,0))
push!(poly1, Vertex(0,0))
@test length(poly1) == 4
remove(vert1, poly1)
@test length(poly1) == 3
@test is(poly1.start, vert2)

# test clipping
println("Testing clipping...")
poly1 = Polygon()
push!(poly1, Vertex(0,1))
push!(poly1, Vertex(1,1))
push!(poly1, Vertex(1,0))
push!(poly1, Vertex(0,0))
poly3 = Polygon()
push!(poly3, Vertex(0.9,-0.1))
push!(poly3, Vertex(0.9,0.1))
push!(poly3, Vertex(0.5,-0.05))
push!(poly3, Vertex(0.1,0.1))
push!(poly3, Vertex(0.1,-0.1))

#test phase1
@test length(poly1) == 4
@test length(poly3) == 5
pc.phase1!(poly3, poly1)
@test length(poly1) == 8
@test length(poly3) == 9
intersects = 0
for p1 in poly1, p2 in poly3
    if p1.location == p2.location
        @test is(p1.neighbor, p2)
        @test is(p2.neighbor, p1)
        @test p1.intersect
        @test p2.intersect
        intersects += 1
    end
end
@test intersects == 4 # make sure we found 4 intersections

pc.phase2!(poly3, poly1)
pc.phase2!(poly1, poly3)
entries = 0
for vert in poly1
    if vert.entry
        entries += 1
    end
end
@test entries == 6
entries = 0
for vert in poly3
    if vert.entry
        entries += 1
    end
end
@test entries == 5

# Test phase1 with holes
poly1 = Polygon()
push!(poly1, Vertex(0.3,1.5))
push!(poly1, Vertex(0.6,1.5))
push!(poly1, Vertex(0.6,-1.5))
push!(poly1, Vertex(0.3,-1.5))
poly2 = Polygon()
push!(poly2, Vertex(0.25,0.25))
push!(poly2, Vertex(0.25,0.75))
push!(poly2, Vertex(0.75,0.75))
push!(poly2, Vertex(0.75,0.25))
poly3 = Polygon()
push!(poly3, Vertex(0,1))
push!(poly3, Vertex(1,1))
push!(poly3, Vertex(1,0))
push!(poly3, Vertex(0,0))
pc.phase1!(poly1,poly2,poly3)
@test length(poly1) == 12
@test length(poly2) == 8
@test length(poly3) == 8
intersects = 0
for p1 in poly1, p2 in poly2
    if p1.location == p2.location
        @test is(p1.neighbor, p2)
        @test is(p2.neighbor, p1)
        @test p1.intersect
        @test p2.intersect
        intersects += 1
    end
end
for p1 in poly1, p2 in poly3
    if p1.location == p2.location
        @test is(p1.neighbor, p2)
        @test is(p2.neighbor, p1)
        @test p1.intersect
        @test p2.intersect
        intersects += 1
    end
end
@test intersects == 8 # make sure we found 4 intersections

poly1 = Polygon()
push!(poly1, Vertex(0,1))
push!(poly1, Vertex(1,1))
push!(poly1, Vertex(1,0))
push!(poly1, Vertex(0,0))
poly3 = Polygon()
push!(poly3, Vertex(0.9,-0.1))
push!(poly3, Vertex(0.9,0.1))
push!(poly3, Vertex(0.5,-0.05))
push!(poly3, Vertex(0.1,0.1))
push!(poly3, Vertex(0.1,-0.1))

results = intersection(poly3, poly1)

@test length(results) == 2
@test length(results[1]) == 4
@test length(results[2]) == 4

poly1 = Polygon()
push!(poly1, Vertex(0,1))
push!(poly1, Vertex(1,1))
push!(poly1, Vertex(1,0))
push!(poly1, Vertex(0,0))

poly2 = Polygon()
push!(poly2, Vertex(0.5,0.5))
push!(poly2, Vertex(1.5,0.5))
push!(poly2, Vertex(1.5,-0.5))
push!(poly2, Vertex(0.5,-0.5))
results = intersection(poly1, poly2)
@test length(results) == 1
@test length(results[1]) == 5

poly1 = Polygon()
push!(poly1, Vertex(1,0))
push!(poly1, Vertex(1,1))
push!(poly1, Vertex(0,1))
push!(poly1, Vertex(0,0))

poly2 = Polygon()
push!(poly2, Vertex(0.5,0.5))
push!(poly2, Vertex(1.5,0.5))
push!(poly2, Vertex(1.5,-0.5))
push!(poly2, Vertex(0.5,-0.5))
results = intersection(poly1, poly2)
@test length(results) == 1
@test length(results[1]) == 5

# Issue 2

polya = Polygon()
push!(polya, Vertex(-0.5, 0))
push!(polya, Vertex(1.5, 0.0))
push!(polya, Vertex(1.5, 1))
push!(polya, Vertex(-0.5, 1))

polyb = Polygon()
push!(polyb, Vertex(0, -0.5))
push!(polyb, Vertex(0, 1.5))
push!(polyb, Vertex(1, 1.5))
push!(polyb, Vertex(1, -0.5))

PolygonClipping.phase1!(polya, polyb)

intersects = 0
for p1 in polya, p2 in polyb
    if p1.location == p2.location
        @test is(p1.neighbor, p2)
        @test is(p2.neighbor, p1)
        @test p1.intersect
        @test p2.intersect
        intersects += 1
    end
end
@test intersects == 4 # make sure we found 4 intersections

polya = Polygon()
push!(polya, Vertex(-0.5, 0))
push!(polya, Vertex(1.5, 0.0))
push!(polya, Vertex(1.5, 1))
push!(polya, Vertex(-0.5, 1))

polyb = Polygon()
push!(polyb, Vertex(0, -0.5))
push!(polyb, Vertex(0, 1.5))
push!(polyb, Vertex(1, 1.5))
push!(polyb, Vertex(1, -0.5))

PolygonClipping.phase1!(polyb, polya)

intersects = 0
for p1 in polya, p2 in polyb
    if p1.location == p2.location
        @test is(p1.neighbor, p2)
        @test is(p2.neighbor, p1)
        @test p1.intersect
        @test p2.intersect
        intersects += 1
    end
end
@test intersects == 4 # make sure we found 4 intersections

PolygonClipping.phase2!(polyb, polya)
PolygonClipping.phase2!(polya, polyb)

println("Testing infill")
polya = Polygon()
push!(polya, Vertex(0.0, 1.0))
push!(polya, Vertex(1.0, 1.0))
push!(polya, Vertex(1.0, 0.0))
push!(polya, Vertex(0.0, 0.0))

polyb = Polygon()
push!(polyb, Vertex(-0.15, -0.5))
push!(polyb, Vertex(-0.15, 1.5))
push!(polyb, Vertex(0.15, 1.5))
push!(polyb, Vertex(0.15, -0.2))
push!(polyb, Vertex(0.3, -0.2))
push!(polyb, Vertex(0.3, 1.5))
push!(polyb, Vertex(0.45, 1.5))
push!(polyb, Vertex(0.45, -0.5))
fill = infill(polya, polyb)

# run lint
println("Running Lint...")
lintpkg("PolygonClipping")


text:
module PolynomialOperators
using Polynomials
using LinearOperators
using IterativeSolvers

type PolynomialOperator <: AbstractLinearOperator
    A::AbstractLinearOperator
    p::Poly

    nrow::Integer
    ncol::Integer
    dtype::DataType
    symmetric::Bool
    hermitian::Bool
    prod::Function
    tprod::Nullable{Function}
    ctprod::Nullable{Function}
end

function poly_prod(p::Poly, A::AbstractLinearOperator,
                   v::StridedVector, tmp::StridedVector)
    w = zeros(promote_type(eltype(v), A.dtype), A.ncol)
    tmp[:] = v
    for k = 1:(length(p.a)-1)
        w += p.a[k]*tmp
        tmp[:] = A*tmp[:]
    end
    w += p.a[end]*tmp
    w
end

solve!{T<:Number}(x::StridedVector{T}, A::PolynomialOperator, B::StridedVector{T}) = gmres!(x,A,B)

import Polynomials: polyval
function polyval(p::Poly, A::AbstractLinearOperator, tmp::StridedVector)
    PolynomialOperator(A, p,
                       A.nrow, A.ncol, A.dtype,
                       A.symmetric, A.hermitian,
                       v -> poly_prod(p, A, v, tmp),
                       Nullable{Function}(v -> poly_tprod(p, A, v, tmp)),
                       Nullable{Function}(v -> poly_ctprod(p, A, v, tmp)))
end

import Base: *
(*)(op::PolynomialOperator, M::Vector) = op.prod(M)
(*)(op::PolynomialOperator, M::StridedVecOrMat) = op.prod(M)

export PolynomialOperator, solve!, polyval
end # module


text:
using AddInit
using Test

@testset "AddInit.jl" begin
    @add_init struct A
        a::String
        b::Int
    end

    @test A(Dict("a" => "foo", "b" => 1)) == A("foo", 1)
    @test A("""{"a":"foo", "b":1}""") == A("foo", 1)

    Base.@kwdef struct B
        a::String = "default"
        b::Int = 1
    end

    @add_init B

    @test B(Dict("a" => "foo", "b" => 1)) == B("foo", 1)

    @test B("{}") == B("default", 1)

    @add_init struct C
        a::A
        b::B
    end

    @test C(Dict("a" => Dict("a" => "foo", "b" => 1), "b" => Dict("a" => "default", "b" => 1))) == C(A("foo", 1), B("default", 1))
    @test C("""{"a":{"a":"foo", "b":1}, "b":{}}""") == C(A("foo", 1), B("default", 1))

end


text:
module DistributedEnvironments

export @initcluster, @eachmachine, @everywhere, cluster_status

using Distributed, Pkg, MacroTools

"""
Allows for kwargs with macro, looks for additional args and splits them on =
"""
function preprocess_args(args)
    kwargs = Dict{Symbol, Any}()
    for arg in args
        @capture(arg, param_ = value_) || throw(ArgumentError("wrong syntax for argument $(arg)"))
        kwargs[param] = value
    end
    kwargs
end

"""
    @initcluster ips [worker_procs=:auto] [sync=true] [status=false]

Takes a list of ip-strings and sets up the current environment on these machines.
The machines should be reachable using ssh from the machine running the command.
The setup will copy the local project and manifest files as well as copying all
packages that are added to the env using `dev` to corresponding location on the
remote machines.

Additional arguments:
* `worker_procs` - Integer or :auto (default), how many workers are added on each machine.
* `sync` - Whether or not to sync the local environment (default is `true`) before adding the workers.
* `status` - Whether or not to show a short status (current users, cpu utilization, julia version) for each machine and remove any machine that does not connect. Default is `false`.

Needs to be called from top level since the macro includes imports.

# Example
```julia
using DistributedEnvironments

ips = ["10.0.0.1", "10.0.0.2"]
@initcluster ips

@everywhere using SomePackage
...
"""
macro initcluster(nodes, args...)
    kwargs = preprocess_args(args)
    return _initcluster(nodes; kwargs...)
end

function _initcluster(nodes; status=false, sync=true, worker_procs=:auto)
    quote
        cluster = collect($(esc(nodes)))

        length(cluster) > 0 || throw(ArgumentError("no servers supplied, nodes=$cluster"))

        # 1 is host, if it is in workers it is the only one. Otherwise remove all workers.
        if 1 ∉ workers()
            rmprocs(workers())
        end

        # Check status of machines
        $(status) && cluster_status(cluster)

        # Sync and instantiate (does precompilation)
        if $(sync)
            # Sync local packages and environment files to all nodes
            sync_env(cluster)

            # Add single worker on each machine to precompile
            addprocs(
                map(node -> (node, 1), cluster),
                topology = :master_worker,
                tunnel = true,
                exeflags = "--project=$(Base.active_project())",
                max_parallel = length(cluster),
            )

            # Instantiate environment on all machines
            @everywhere begin
                import Pkg
                Pkg.instantiate()
            end

            # Remove precompile workers
            # TODO should be able to keep them and add the right amount, maybe SSHManager?
            # Or maybe not, good to have restart of all machines after precompile since sometimes it hangs there.
            rmprocs(workers())
        end

        # Add one worker per thread on each node in the cluster
        addprocs(
            map(node -> (node, $(worker_procs)), cluster),
            topology=:master_worker,
            tunnel=true,
            exeflags = "--project=$(Base.active_project())",
            max_parallel=24*length(cluster), # TODO what should this be?
        )
        println("All workers initialized.")
    end
end

"""
    @eachmachine expr

Similar to `@everywhere`, but only runs on one worker per machine.
Can be used for things like precompiling, downloading datasets or similar.
"""
macro eachmachine(expr)
    return _eachmachine(expr)
end

function _eachmachine(expr)
    machinepids = get_unique_machine_ids()
    quote
        @everywhere $machinepids $expr
    end
end

get_unique_machine_ids() = unique(id -> Distributed.get_bind_addr(id), procs())
get_unique_machine_ips() = unique(map(id -> Distributed.get_bind_addr(id), procs()))

function sync_env(cluster)
    proj_path = dirname(Pkg.project().path)
    deps = Pkg.dependencies()
    # (:name, :version, :tree_hash, :is_direct_dep, :is_pinned, :is_tracking_path, :is_tracking_repo, :is_tracking_registry, :git_revision, :git_source, :source, :dependencies)

    Threads.@threads for node in cluster
        rsync("$(proj_path)/Project.toml", node)
        println("Worker $(node): Copied Project.toml")
        rsync("$(proj_path)/Manifest.toml", node)
        println("Worker $(node): Copied Manifest.toml")

        for (id, package) in deps
            if package.is_tracking_path
                rsync(package.source, node)
                println("Worker $(node): Copied $(package.name)")
            end
        end
    end
end

function rsync(path, target)
    run(`ssh -q -t $(target) mkdir -p $(dirname(path))`) # Make sure path exists
    if isfile(path)
        run(`rsync -ue ssh $(path) $(target):$(path)`) # Copy
    else
        run(`rsync -rue ssh --delete $(path)/ $(target):$(path)`) # Copy
    end
end

function scp(path, target)
    dir = isfile(path) ? dirname(path) : path
    run(`ssh -q -t $(target) mkdir -p $(dir)`) # Make sure path exists
    run(`ssh -q -t $(target) rm -rf $(path)`) # Delete old
    run(`scp -r -q $(path) $(target):$(path)`) # Copy
end

"""
    cluster_status!(cluster)

Run a status check on each machine in the list and remove any machines not reachable.
"""
function cluster_status!(cluster::Vector{String})
    calc_cpu = "awk '{u=\$2+\$4; t=\$2+\$4+\$5; if (NR==1){u1=u; t1=t;} else print (\$2+\$4-u1) * 100 / (t-t1) \"%\"; }' <(grep 'cpu ' /proc/stat) <(sleep 1;grep 'cpu ' /proc/stat)"

    connection_error = []
    for node in cluster
        printstyled("Checking machine $(node):\n", bold=true, color=:magenta)
        try
            run(`ssh -q -t $(node) who \&\& $calc_cpu \&\& julia --version`)
        catch
            connection_error = vcat(connection_error, node)
        end
    end

    filter!(x -> x ∉ connection_error, cluster)

    if !isempty(connection_error)
        println("Failed to connect to the following machines:")
        for node in connection_error
            println("\t $(node)")
        end
    end
end

"""
    cluster_status()

Run a status check on each machine in the running cluster.

Prints current users, current cpu utilization and current julia version.
"""
cluster_status() = cluster_status!(get_unique_machine_ips())

end