text:
export discriminant_group, torsion_quadratic_module, normal_form, genus, isgenus,
isdegenerate, cover, relations

# Torsion QuadraticForm
#
# Example:
# A = matrix(ZZ, [[2,0,0,-1],[0,2,0,-1],[0,0,2,-1],[-1,-1,-1,2]])
# L = Zlattice(gram = A)
# T = Hecke.discriminant_group(T)

# We represent torsion quadratic modules as quotients of Z-lattices
# by a full rank sublattice.
#
# We store them as a Z-lattice M together with a projection p : M -> A
# onto an abelian group A. The bilinear structure of A is induced via p,
# that is <a, b> = <p^-1(a), p^-1(a)> with values in Q/nZ, where n
# is the modulus and depends on the kernel of p.
#
# Elements of A are basically just elements of the underlying abelian group.
# To move between M and A, we use the lift function lift : M -> A
# and coercion A(m).
#
# N.B. Since there are no elements of Z-latties, we think of elements of M as
# elements of the ambient vector space. Thus if v::Vector is such an element
# then the coordinates with respec to the basis of M are given by
# v * inv(basis_matrix(M)).
@attributes mutable struct TorQuadMod
  ab_grp::GrpAbFinGen             # underlying abelian group
  cover::ZLat                     # ZLat -> ab_grp, x -> x * proj
  rels::ZLat
  proj::fmpz_mat                  # is a projection and respects the forms
  gens_lift::Vector{Vector{fmpq}}
  gens_lift_mat::fmpq_mat
  modulus::fmpq
  modulus_qf::fmpq
  value_module::QmodnZ
  value_module_qf::QmodnZ
  gram_matrix_bilinear::fmpq_mat
  gram_matrix_quadratic::fmpq_mat
  gens
  isnormal::Bool

  TorQuadMod() = new()
end

################################################################################
#
#  Construction
#
################################################################################

# compute the torsion quadratic module M/N

@doc Markdown.doc"""
    torsion_quadratic_module(M::ZLat, N::ZLat; gens::Union{Nothing, Vector{<:Vector}} = nothing,
                                                    snf::Bool = true,
                                                    modulus::fmpq = fmpq(0),
                                                    check::Bool = true)

Given a Z-lattice $M$ and a sublattice $N$ of $M$, return the torsion quadratic
module $M/N$.

If `gens` is set, the images of `gens` will be used as the
generators of the abelian group $M/N$.

If `snf` is `true`, the underlying abelian group will be in Smith normal form.
Otherwise, the images of the basis of $M$ will be used as the generators.
"""
function torsion_quadratic_module(M::ZLat, N::ZLat; gens::Union{Nothing, Vector{<:Vector}} = nothing,
                                                    snf::Bool = true,
                                                    modulus::fmpq = fmpq(0),
                                                    modulus_qf::fmpq = fmpq(0),
                                                    check::Bool = true)
  @req ambient_space(M) === ambient_space(N) """
      Lattices must have same ambient space
      """
  fl, _rels = issublattice_with_relations(M, N)
  @req fl "Second lattice must be a sublattice of first lattice"
  rels = change_base_ring(FlintZZ, _rels)
  A = abelian_group(rels)
  n = dim(ambient_space(M))
  BM = basis_matrix(M)
  if gens != nothing
    gens_in_A = elem_type(A)[]
    for g in gens
      @req length(g) == n "Generator not an element of the ambient space"
      fl, v = can_solve_with_solution(BM,
                                      matrix(FlintQQ, 1, n, g),
                                      side = :left)
      @req denominator(v) == 1 "Generator not an element of the lattice"
      ginA = A(change_base_ring(FlintZZ, v))
      push!(gens_in_A, ginA)
    end
    S, mS = sub(A, gens_in_A)
    if check
      if order(S) != order(A)
        throw(ArgumentError("Generators do not generator the torsion module"))
      end
    end
  else
    if snf
      S, mS = Hecke.snf(A)
    else
      S, mS = A, id_hom(A)
    end
  end
  # mS : S -> A
  # generators of S lifted along M -> M/N = A -> S
  if gens != nothing
    gens_lift = gens
  else
    gens_lift = Vector{fmpq}[reshape(collect(change_base_ring(FlintQQ, mS(s).coeff) * BM), :) for s in Hecke.gens(S)]
  end

  num = basis_matrix(M) * gram_matrix(ambient_space(M)) * transpose(basis_matrix(N))
  if iszero(modulus)
    modulus = reduce(gcd, [a for a in num], init = zero(fmpq))
  end
  norm = reduce(gcd, diagonal(gram_matrix(N)), init = zero(fmpq))

  if iszero(modulus_qf)
    modulus_qf = gcd(norm, 2 * modulus)
  else
    modulus_qf = modulus_qf
  end

  T = TorQuadMod()
  T.cover = M
  T.rels = N
  T.ab_grp = S
  T.proj = inv(mS).map
  T.gens_lift = gens_lift
  T.gens_lift_mat = matrix(FlintQQ, length(gens_lift), ngens(A), reduce(vcat, gens_lift, init = fmpq[]))
  T.modulus = modulus
  T.modulus_qf = modulus_qf
  T.value_module = QmodnZ(modulus)
  T.value_module_qf = QmodnZ(modulus_qf)
  T.isnormal = false
  return T
end

# compute M^#/M
function discriminant_group(L::ZLat)
  @req isintegral(L) "the lattice must be integral"
  T = torsion_quadratic_module(dual(L), L)
  set_attribute!(T,:isdegenerate => false)
  return T
end

@doc Markdown.doc"""
    order(T::TorQuadMod) -> fmpz

Return the order of `T`
"""
function order(T::TorQuadMod)
  return order(abelian_group(T))
end

@doc Markdown.doc"""
    exponent(T::TorQuadMod) -> fmpz

Return the exponent of `T`
"""
function exponent(T::TorQuadMod)
  return exponent(abelian_group(T))
end

@doc Markdown.doc"""
    elementary_divisors(T::TorQuadMod) -> Vector{fmpz}

Return the elementary divisors of underlying abelian group of `T`.
"""
function elementary_divisors(T::TorQuadMod)
  return elementary_divisors(abelian_group(T))
end

################################################################################
#
#  Basic field access
#
################################################################################

abelian_group(T::TorQuadMod) = T.ab_grp

cover(T::TorQuadMod) = T.cover

relations(T::TorQuadMod) = T.rels

value_module(T::TorQuadMod) = T.value_module

value_module_quadratic_form(T::TorQuadMod) = T.value_module_qf

################################################################################
#
#  Gram matrices
#
################################################################################

function gram_matrix_bilinear(T::TorQuadMod)
  if isdefined(T, :gram_matrix_bilinear)
    return T.gram_matrix_bilinear
  end
  g = gens(T)
  G = zero_matrix(FlintQQ, length(g), length(g))
  for i in 1:length(g)
    for j in 1:i
      G[i, j] = G[j, i] = lift(g[i] * g[j])
    end
  end
  T.gram_matrix_bilinear = G
  return G
end

function gram_matrix_quadratic(T::TorQuadMod)
  if isdefined(T, :gram_matrix_quadratic)
    return T.gram_matrix_quadratic
  end
  g = gens(T)
  r = length(g)
  G = zero_matrix(FlintQQ, r, r)
  for i in 1:r
    for j in 1:(i - 1)
      G[i, j] = G[j, i] = lift(g[i] * g[j])
    end
    G[i, i] = lift(quadratic_product(g[i]))
  end
  T.gram_matrix_quadratic = G
  return G
end

################################################################################
#
#  I/O
#
################################################################################

# TODO: Print like abelian group
function Base.show(io::IO, ::MIME"text/plain" , T::TorQuadMod)
  @show_name(io,T)
  print(io, "Finite quadratic module over Integer Ring with underlying abelian group\n")
  println(io, abelian_group(T))
  print(io, "Gram matrix of the quadratic form with values in ")
  println(io, value_module_quadratic_form(T))
  show(io,MIME"text/plain"(), gram_matrix_quadratic(T))
end

function Base.show(io::IO, T::TorQuadMod)
  compact = get(io, :compact, false)
  if compact
    name = get_attribute(T,:name)
    if name !== nothing
      print(io, name)
    else
      print(io, "TorQuadMod ", gram_matrix_quadratic(T))
    end
  else
    print(io, "TorQuadMod: ")
    A = abelian_group(T)
    if issnf(A)
      show_snf_structure(io, abelian_group(T))
      print(io, " ")
    end
    print(io, gram_matrix_quadratic(T))
  end
end

################################################################################
#
#  Elements
#
################################################################################

mutable struct TorQuadModElem
  data::GrpAbFinGenElem
  parent::TorQuadMod

  TorQuadModElem(T::TorQuadMod, a::GrpAbFinGenElem) = new(a, T)
end

elem_type(::Type{TorQuadMod}) = TorQuadModElem

################################################################################
#
#  Creation
#
################################################################################

function (T::TorQuadMod)(a::GrpAbFinGenElem)
  @req abelian_group(T) === parent(a) "Parents do not match"
  return TorQuadModElem(T, a)
end

# Coerces an element of the ambient space of cover(T) to T

function (T::TorQuadMod)(v::Vector)
  @req length(v) == dim(ambient_space(cover(T))) "Vector of wrong length"
  vv = map(FlintQQ, v)
  if eltype(vv) != fmpq
    error("Cannot coerce elements to the rationals")
  end
  return T(vv::Vector{fmpq})
end

function (T::TorQuadMod)(v::Vector{fmpq})
  @req length(v) == dim(ambient_space(cover(T))) "Vector of wrong length"
  vv = change_base_ring(FlintZZ, matrix(FlintQQ, 1, length(v), v) * inv(basis_matrix(cover(T))))
  return T(abelian_group(T)(vv * T.proj))
end

################################################################################
#
#  Printing
#
################################################################################

function Base.show(io::IO, a::TorQuadModElem)
  v = a.data.coeff
  print(io, "[")
  for i in 1:length(v)
    if i == length(v)
      print(io, v[i])
    else
      print(io, v[i], ", ")
    end
  end
  print(io, "]")
end

################################################################################
#
#  Equality
#
################################################################################

function Base.:(==)(a::TorQuadModElem, b::TorQuadModElem)
  if parent(a) !== parent(b)
    return false
  else
    return data(a) == data(b)
  end
end

################################################################################
#
#  Generators
#
################################################################################

function gens(T::TorQuadMod)
  if isdefined(T, :gens)
    return T.gens::Vector{TorQuadModElem}
  else
    _gens = TorQuadModElem[T(g) for g in gens(abelian_group(T))]
    T.gens = _gens
    return _gens
  end
end

ngens(T::TorQuadMod) = length(T.gens_lift)

parent(a::TorQuadModElem) = a.parent

data(a::TorQuadModElem) = a.data

# Check the parent
function (A::GrpAbFinGen)(a::TorQuadModElem)
  @req A === abelian_group(parent(a)) "Parents do not match"
  return a.data
end

################################################################################
#
#  Addition
#
################################################################################

function Base.:(+)(a::TorQuadModElem, b::TorQuadModElem)
  @req parent(a) === parent(b) "Parents do not match"
  T = parent(a)
  return T(a.data + b.data)
end

function Base.:(*)(a::TorQuadModElem, b::fmpz)
  T = parent(a)
  return T(a.data * b)
end

Base.:(*)(a::fmpz, b::TorQuadModElem) = b * a

Base.:(*)(a::Integer, b::TorQuadModElem) = fmpz(a) * b

Base.:(*)(a::TorQuadModElem, b::Integer) = b * a

################################################################################
#
#  Inner product
#
################################################################################

function Base.:(*)(a::TorQuadModElem, b::TorQuadModElem)
  T = parent(a)
  z = inner_product(ambient_space(cover(T)), lift(a), lift(b))
  return value_module(T)(z)
end

inner_product(a::TorQuadModElem, b::TorQuadModElem)=(a*b)

################################################################################
#
#  Quadratic product
#
################################################################################

function quadratic_product(a::TorQuadModElem)
  T = parent(a)
  al = lift(a)
  z = inner_product(ambient_space(cover(T)), al, al)
  return value_module_quadratic_form(T)(z)
end

################################################################################
#
#  order
#
################################################################################

order(a::TorQuadModElem) = order(a.data)

################################################################################
#
#  Lift
#
################################################################################

# Lift an element to the ambient space of cover(parent(a))
function lift(a::TorQuadModElem)
  T = parent(a)
  z = change_base_ring(FlintQQ, a.data.coeff) * T.gens_lift_mat
  return fmpq[z[1, i] for i in 1:ncols(z)]
end

################################################################################
#
#  Maps between torsion quadratic modules
#
################################################################################

mutable struct TorQuadModMor <: Map{TorQuadMod, TorQuadMod, HeckeMap, TorQuadModMor}
  header::MapHeader{TorQuadMod, TorQuadMod}
  map_ab::GrpAbFinGenMap

  function TorQuadModMor(T::TorQuadMod, S::TorQuadMod, m::GrpAbFinGenMap)
    z = new()
    z.header = MapHeader(T, S)
    z.map_ab = m
    return z
  end
end

################################################################################
#
#  User constructors
#
################################################################################

function hom(T::TorQuadMod, S::TorQuadMod, M::fmpz_mat)
  map_ab = hom(abelian_group(T), abelian_group(S), M)
  return TorQuadModMor(T, S, map_ab)
end

function hom(T::TorQuadMod, S::TorQuadMod, img::Vector{TorQuadModElem})
  _img = GrpAbFinGenElem[]
  @req length(img) == ngens(T) "Wrong number of elements"
  for g in img
    @req parent(g) === S "Elements have the wrong parent"
    push!(_img, abelian_group(S)(g))
  end
  map_ab = hom(abelian_group(T), abelian_group(S), _img)
  return TorQuadModMor(T, S, map_ab)
end

function identity_map(T::TorQuadMod)
  map_ab = id_hom(abelian_group(T))
  return TorQuadModMor(T, T, map_ab)
end

id_hom(T::TorQuadMod) = identity_map(T)

function inv(f::TorQuadModMor)
  map_ab = inv(f.map_ab)
  return TorQuadModMor(codomain(f),domain(f),map_ab)
end

function compose(f::TorQuadModMor, g::TorQuadModMor)
  codomain(f) == domain(g) || error("incompatible (co)domains")
  map_ab = compose(f.map_ab, g.map_ab)
  return TorQuadModMor(domain(f), codomain(g), map_ab)
end

function image(f::TorQuadModMor, a::TorQuadModElem)
  A = abelian_group(domain(f))
  return codomain(f)(f.map_ab(A(a)))
end

function preimage(f::TorQuadModMor, a::TorQuadModElem)
  A = abelian_group(domain(f))
  return domain(f)(f.map_ab\(A(a)))
end

isbijective(f::TorQuadModMor) = isbijective(f.map_ab)

################################################################################
#
#  Submodules
#
################################################################################

@doc Markdown.doc"""
    sub(T::TorQuadMod, generators::Vector{TorQuadModElem})-> TorQuadMod, Map

Return the submodule of `T` defined by `generators` and the inclusion morphism.
"""
function sub(T::TorQuadMod, gens::Vector{TorQuadModElem})
  if length(gens) > 0
    _gens = [lift(g) for g in gens]
    V = ambient_space(T.cover)
    _gens_mat = matrix(QQ, _gens)
    gens_new = [basis_matrix(T.rels); _gens_mat]
    cover = lattice(V, gens_new, isbasis = false)
  else
    cover = T.cover
    _gens = nothing
  end
  S = torsion_quadratic_module(cover, T.rels, gens=_gens, modulus=T.modulus,
                               modulus_qf=T.modulus_qf)
  imgs = [T(lift(g)) for g in Hecke.gens(S)]
  inclusion = hom(S, T, imgs)
  return S, inclusion
end

function TorQuadMod(q::fmpq_mat)
  @req issquare(q) "Matrix must be a square matrix"
  @req issymmetric(q) "Matrix must be symmetric"

  d = denominator(q)
  Q = change_base_ring(FlintZZ, d * q)
  S, U, V = snf_with_transform(Q)
  D = change_base_ring(FlintQQ, U) * q * change_base_ring(FlintQQ, V)
  L = Zlattice(1//d * identity_matrix(QQ, nrows(q)), gram = d^2 * q)
  denoms = [denominator(D[i, i]) for i in 1:ncols(D)]
  rels = diagonal_matrix(denoms) * U
  LL = lattice(ambient_space(L), 1//d * change_base_ring(QQ, rels))
  return torsion_quadratic_module(L, LL, modulus = fmpq(1))
end

@doc Markdown.doc"""
    primary_part(T::TorQuadMod, m::fmpz)-> Tuple{TorQuadMod, TorQuadModMor}

Return the primary part of `T` as a submodule.
"""
function primary_part(T::TorQuadMod, m::fmpz)
  S, i = primary_part(T.ab_grp, m)
  genprimary = [i(s) for s in gens(S)]
  submod = sub(T, [T(a) for a in genprimary])
  return submod
end

primary_part(T::TorQuadMod,m::Int) = primary_part(T,ZZ(m))

@doc Markdown.doc"""
    orthogonal_submodule_to(T::TorQuadMod, S::TorQuadMod)-> TorQuadMod

Return the orthogonal submodule to the submodule `S` of `T`.
"""
function orthogonal_submodule_to(T::TorQuadMod, S::TorQuadMod)
  @assert issublattice(cover(T), cover(S)) "The second argument is not a submodule of the first argument"
  V = ambient_space(cover(T))
  G = gram_matrix(V)
  B = basis_matrix(cover(T))
  C = basis_matrix(cover(S))
  m = T.modulus
  Y = B * G * transpose(C)
  # Elements of the ambient module which pair integrally with cover(T)
  integral = inv(Y) * B
  # Element of the ambient module which pair in mZZ with cover(T)
  orthogonal =  m * integral
  # We have to make sure we get a submodule
  ortho = intersect(lattice(V, B), lattice(V, orthogonal))
  Borth = basis_matrix(ortho)
  gens_orth = [T(vec(collect(Borth[i,:]))) for i in 1:nrows(Borth)]
  return sub(T, gens_orth)
end

@doc Markdown.doc"""
    isdegenerate(T::TorQuadMod)-> Bool

Return true if the underlying bilinear form is degenerate.
"""
function isdegenerate(T::TorQuadMod)
  return get_attribute!(T,:isdegenerate) do
    return order(orthogonal_submodule_to(T,T)[1]) != 1
  end
end

@doc Markdown.doc"""
    radical_bilinear(T::TorQuadMod) -> Tuple{TorQuadMod, TorQuadModMor}

Return the radical `\{x \in T | b(x,T) = 0\}` of the bilinear form `b` on `T`.
"""
function radical_bilinear(T::TorQuadMod)
  return orthogonal_submodule_to(T,T)
end

@doc Markdown.doc"""
    radical_quadratic(T::TorQuadMod) -> Tuple{TorQuadMod, TorQuadModMor}

Return the radical `\{x \in T | b(x,T) = 0 and q(x)=0\}` of the quadratic form
`q` on `T`.
"""
function radical_quadratic(T::TorQuadMod)
  Kb, ib = radical_bilinear(T)
  G = gram_matrix_quadratic(Kb)*1//Kb.modulus
  F = GF(2, cached=false)
  G2 = map_entries(F, G)
  r, kermat = left_kernel(G2)
  kermat = lift(kermat[1:r,:])
  g = gens(Kb)
  n = length(g)
  kergen = [sum(kermat[i,j]*g[j] for j in 1:n) for i in 1:r]
  Kq, iq = sub(Kb,kergen)
  @assert iszero(gram_matrix_quadratic(Kq))
  return Kq, compose(iq,ib)
end

@doc Markdown.doc"""
    rescale(T::TorQuadMod, k::RingElement) -> TorQuadMod

Return the torsion quadratic module with quadratic form scaled by ``k``,
where k is a non-zero rational number.
If the old form was defined modulo `n`, then the new form is defined
modulo `n k`.
"""
function rescale(T::TorQuadMod, k::RingElement)
  @req !iszero(k) "Parameter ($k) must be non-zero"
  C = cover(T)
  inner_product_mat = k * gram_matrix(ambient_space(C))
  V = quadratic_space(QQ, inner_product_mat)
  M = lattice(V, basis_matrix(C))
  N = lattice(V, basis_matrix(T.rels))
  return torsion_quadratic_module(M, N)
end

@doc Markdown.doc"""
    normal_form(T::TorQuadMod; partial=false) -> tuple{TorQuadMod,TorQuadModMor}

Return the normal form `N` of the given torsion quadratic module `T` along
with the projection ``T -> N``.

Let `K` be the radical of the quadratic form of `T`. Then `N = T/K` is
half-regular. Two half-regular torsion quadratic modules are isometric
if and only if they have equal normal forms.
"""
function normal_form(T::TorQuadMod; partial=false)
  if T.isnormal
    return T, hom(T,T,gens(T))
  end
  if isdegenerate(T)
    K, _ = radical_quadratic(T)
    N = torsion_quadratic_module(cover(T), cover(K), modulus=T.modulus, modulus_qf=T.modulus_qf)
    i = hom(T, N, [N(lift(g)) for g in gens(T)])
  else
    N = T
    i = identity_map(T)
  end
  normal_gens = TorQuadModElem[]
  prime_div = prime_divisors(exponent(N))
  for p in prime_div
    D_p, I_p = primary_part(N, p)
    q_p = gram_matrix_quadratic(D_p)
    if p == 2
      q_p = q_p * D_p.modulus_qf^-1
    else
      q_p = q_p * D_p.modulus^-1
    end

    # the normal form is implemented for p-adic lattices
    # so we should work with the lattice q_p --> q_p^-1
    q_p1 = inv(q_p)
    prec = valuation(exponent(T), p) + 5
    D, U = padic_normal_form(q_p1, p, prec=prec, partial=partial)
    R = ResidueRing(ZZ, ZZ(p)^prec)
    U = map_entries(x->R(ZZ(x)),U)
    U = transpose(inv(U))

    # the inverse is in normal form - so to get a normal form for
    # the original one
    # it is enough to massage each 1x1 resp. 2x2 block.
    denom = denominator(q_p)
    q_pR = map_entries(x->R(ZZ(x)), denom*q_p)
    D = U * q_pR * transpose(U)
    D = map_entries(x->R(mod(lift(x),denom)), D)
    if p != 2
       # follow the conventions of Miranda-Morrison
       m = ZZ(D_p.modulus_qf//D_p.modulus)
       D = R(m)^-1*D
    end

    D1, U1 = _normalize(D, ZZ(p), false)
    U = U1 * U

    #apply U to the generators
    n1 = ncols(U)
    Gp =  gens(D_p);
    for i in 1:nrows(U)
      g = sum(lift(U[i,j]) * Gp[j] for j in 1:ncols(U))
      push!(normal_gens, I_p(g))
    end
  end

  S, j =  sub(N, normal_gens)
  J = compose(i,inv(j))
  if !partial
    S.isnormal = true
  end
  return S, J
end

@doc Markdown.doc"""
_brown_indecomposable(q::MatElem, p::fmpz) ->  fmpz
Return the Brown invariant of the indecomposable form ``q``.

The values are taken from Table 2.1 in [Shim2016]_.
INPUT:
- ``q`` - an indecomposable quadratic form represented by a
  rational `1 \times 1` or `2 \times 2` matrix
- ``p`` - a prime number
EXAMPLES::

  julia> q = matrix(QQ, 1, 1, [1//3])
  julia> _brown_indecomposable(q,fmpz(3))
  6
  julia> q = matrix(QQ, 1, 1, [2//3])
  julia> _brown_indecomposable(q,fmpz(3))
  2
"""
function _brown_indecomposable(q::MatElem, p::fmpz)
  v = valuation(denominator(q), p)
  if p == 2
    # brown(U) = 0
    if ncols(q) == 2
      if iszero(q[1,1]) || iszero(q[2,2]) || (valuation(q[1,1],2) > v + 1 && valuation(q[2, 2],2) > v + 1)
        # type U
        return mod(0, 8)
      else
        # type V
        return mod(4*v, 8)
      end
    end
    u = numerator(q[1, 1])
    return mod(u + divexact(v*(u^2 - 1), 2), 8)
  end
  if p % 4 == 1
    e = -1
  end
  if p % 4 == 3
    e = 1
  end
  if v % 2 == 1
    u = div(numerator(q[1, 1]), 2)
    if jacobi_symbol(u, p) == 1
      return mod(1 + e, 8)
    else
      return mod(-3 + e, 8)
    end
  end
  return mod(0, 8)
end

@doc Markdown.doc"""
    brown_invariant(self::TorQuadMod) -> Nemo.nmod
Return the Brown invariant of this torsion quadratic form.

Let `(D,q)` be a torsion quadratic module with values in `\QQ / 2 \ZZ`.
The Brown invariant `Br(D,q) \in \Zmod{8}` is defined by the equation

.. MATH::

  \exp \left( \frac{2 \pi i }{8} Br(q)\right) =
  \frac{1}{\sqrt{D}} \sum_{x \in D} \exp(i \pi q(x)).

The Brown invariant is additive with respect to direct sums of
torsion quadratic modules.

OUTPUT:

  - an element of `\Zmod{8}`
EXAMPLES::

  julia> L = Zlattice(gram=matrix(ZZ, [[2,-1,0,0],[-1,2,-1,-1],[0,-1,2,0],[0,-1,0,2]]))
  julia> T = Hecke.discriminant_group(L)
  julia> brown_invariant(T)
  4
"""
function brown_invariant(T::TorQuadMod)
  @req T.modulus_qf == 2 "the torsion quadratic form must have values in Q/2Z"
  @req !isdegenerate(T) "the torsion quadratic form must be non-degenerate"
  brown = ResidueRing(ZZ, 8)(0)
  for p in prime_divisors(exponent(T))
    q = normal_form(primary_part(T, p)[1])[1]
    q = gram_matrix_quadratic(q)
    L = collect_small_blocks(q)
    for qi in L
      brown += _brown_indecomposable(qi, p)
    end
  end
  return brown
end

@doc Markdown.doc"""
    genus(T::TorQuadMod, signature_pair::Tuple{Int, Int}) -> ZGenus

Return the genus defined by a TorQuadMod T and the ``signature_pair``.
If no such genus exists, raise a ``ErrorException``.

REFERENCES:

  [Nik1977]_ Corollary 1.9.4 and 1.16.3.

"""
function genus(T::TorQuadMod, signature_pair::Tuple{Int, Int})
  s_plus = signature_pair[1]
  s_minus = signature_pair[2]
  rank = s_plus + s_minus
  if s_plus < 0 || s_minus < 0
    error("signatures must be non-negative")
  end
  if length(elementary_divisors(T)) > rank
    error("this discriminant form and signature do not define a genus")
  end
  disc = order(T)
  determinant = ZZ(-1)^s_minus * disc
  local_symbols = ZpGenus[]
  P = prime_divisors(2 * disc)
  sort!(P) # expects primes in ascending order
  for p in P
    D, _ = primary_part(T, p)
    if length(elementary_divisors(D)) != 0
      G_p = inv(gram_matrix_quadratic(D))
      # get rid of denominators without changing the local equivalence class
      G_p *= denominator(G_p)^2
      G_p = change_base_ring(ZZ, G_p)
      genus_p = genus(G_p, p, valuation(elementary_divisors(D)[end], p))
    else
      genus_p = ZpGenus(p, Vector{Int}[])
    end
    rk = rank - length(elementary_divisors(D))
    if rk > 0
      if p == 2
        det = remove(determinant, 2)[2]
        det *= prod([di[3] for di in genus_p._symbol])
        det = mod(det, 8)
        push!(genus_p._symbol, [0, rk, det, 0, 0])
      else
        det = jacobi_symbol(remove(determinant, p)[2], p)
        det = det * prod([di[3] for di in genus_p._symbol])
        push!(genus_p._symbol, [0, rk, det])
      end
    end
    sort!(genus_p._symbol)
    push!(local_symbols, genus_p)
  end
  # This genus has the right discriminant group
  # but it may be empty
  sym2 = local_symbols[1]._symbol

  if sym2[1][1] != 0
    sym2 = pushfirst!(sym2, [0, 0, 1, 0, 0])
  end
  if length(sym2) <= 1 || sym2[2][1] != 1
    sym2 = insert!(sym2, 2, [1, 0, 1, 0, 0])
  end
  if length(sym2) <= 2 || sym2[3][1] != 2
    sym2 = insert!(sym2, 3, [2, 0, 1, 0, 0])
  end

  if T.modulus_qf == 1
    # in this case the blocks of scales 1, 2, 4 are under determined
    # make sure the first 3 symbols are of scales 1, 2, 4
    # i.e. their valuations are 0, 1, 2

    # the form is odd
    block0 = [b for b in _blocks(sym2[1]) if b[4] == 1]

    o = sym2[2][4]
    # no restrictions on determinant and
    # oddity beyond existence
    # but we know if even or odd
    block1 = [b for b in _blocks(sym2[2]) if b[4] == o]

    d = sym2[3][3]
    o = sym2[3][4]
    t = sym2[3][5]
    # if the jordan block of scale 2 is even we know it
    if o == 0
      block2 = [sym2[3]]
      # if it is odd we know det and oddity mod 4 at least
    else
      block2 = [b for b in _blocks(sym2[3]) if b[4] == o
        && mod(b[3] - d, 4) == 0
        && mod(b[5] - t, 4) == 0
        && mod(b[3] - d, 8) == mod(b[5] - t, 8)  # if the oddity is altered by 4 then so is the determinant
        ]
    end
  else
    if T.modulus_qf == 2
      # the form is even
      block0 = [b for b in _blocks(sym2[1]) if b[4] == 0]

      # if the jordan block of scale 2 is even we know it
      d = sym2[2][3]
      o = sym2[2][4]
      t = sym2[2][5]
      if o == 0
        block1 = [sym2[2]]
      else
        # the block is odd and we know det and oddity mod 4
        block1 = [b for b in _blocks(sym2[2])
                if b[4] == o
                && mod(b[3] - d, 4) == 0
                && mod(b[5] - t, 4) == 0
                && mod(b[3] - d, 8) == mod(b[5] - t, 8) # if the oddity is altered by 4 then so is the determinant
                ]
      end
      # this is completely determined
      block2 = [sym2[3]]
    else
      error("this is not a discriminant form of a ZLattice")
    end
  end

  # figure out which symbol defines a genus and return that
  for b0 in block0
    for b1 in block1
      for b2 in block2
        sym2[1:3] = [b0, b1, b2]
        local_symbols[1] = ZpGenus(2, sym2)
        genus = ZGenus(signature_pair, local_symbols)
        if _isglobal_genus(genus)
          # make the symbol sparse again.
          i = 0
          k = 1
          while i < 3
            if sym2[k][2] == 0
              deleteat!(sym2, k)
            else
              k = k + 1
            end
            i = i + 1
          end
          local_symbols[1] = ZpGenus(2, sym2)
          genus = ZGenus(signature_pair, local_symbols)
          return genus
        end
      end
    end
  end
  error("this discriminant form and signature do not define a genus")
end

@doc Markdown.doc"""
    isgenus(T::TorQuadMod, signature_pair::Tuple{Int, Int}; even=true) -> Bool
Return ``true`` if there is a lattice with this signature and discriminant form.

INPUT:

- signature_pair -- a tuple of non negative integers ``(s_plus, s_minus)``
- even -- bool (default: ``True``)
"""
function isgenus(T::TorQuadMod, signature_pair::Tuple{Int, Int}; even=true)
  s_plus = signature_pair[1]
  s_minus = signature_pair[2]
  if s_plus < 0 || s_minus < 0
    error("signature invariants must be non negative")
  end
  rank = s_plus + s_minus
  signature = s_plus - s_minus
  D = order(T)
  det = (-1)^s_minus * D
  if rank < length(elementary_divisors(T))
    return false
  end
  if even==true && T.modulus_qf != 2
    error("the discriminant form of an even lattice has values modulo 2.")
  end
  if even!=true && T.modulus != T.modulus_qf != 1
    error("the discriminant form of an odd lattice has values modulo 1.")
  end
  if even == false
    error("at the moment sage knows how to do this only for even genera. Help us to implement this for odd genera.")
  end
  for p in prime_divisors(D)
    # check the determinant conditions
    Q_p = primary_part(T, p)[1]
    gram_p = gram_matrix_quadratic(Q_p)
    length_p = length(elementary_divisors(Q_p))
    u = remove(det, p)[2]
    up = remove(numerator(Hecke.det(gram_p)), p)[2]
    if p != 2 && length_p == rank
      if jacobi_symbol(u, p) != jacobi_symbol(up, p)
        return false
      end
    end
    if p == 2
      if mod(rank, 2) != mod(length_p, 2)
        return false
      end
      n = (rank - length_p) // 2
      if mod(u, 4) != mod((-1)^(mod(n, 2)) * up, 4)
        return false
      end
      if rank == length_p
        a = QQ(1, 2)
        b = QQ(3, 2)
        diag = diagonal(gram_p)
        if  !((a in diag) || (b in diag))
          if mod(u, 8) != mod(up, 8)
            return false
          end
        end
      end
    end
  end
  if brown_invariant(T) != signature
    return false
  end
  return true
end


text:
"Read response code from a packet header"
respcode(resp) = resp[1]
"Read response type from a packet header"
resptype(resp) = resp[2]
"Read response message length from a packet header"
resplen(resp) = 256*resp[3] + resp[4]

"Read confirmation response. Usually zero. Could be a warning (positive number)"
respconf(resp) = ntoh(reinterpret(Int32, resp[5:8])[1])
"Read error code in error responses (type 128)"
resperr(resp) = ntoh(reinterpret(Int32, resp[5:8])[1])
function respdata(resp)
    nrows = 256*resp[5] + resp[6]
    ncols = 256*resp[7] + resp[8]
    return nrows, ncols
end

"Read 4 byte integer response from type 8 messages"
respsinglevali(resp) = ntoh(reinterpret(Int32, resp[5:8])[1])
"Read 4 byte float response from type 9 messages"
respsinglevalf(resp) = ntoh(reinterpret(Float32, resp[5:8])[1])

"Is the packet a confirmation packet?"
ispackconf(resp) = resptype(resp) == 4
"Is the packet an error packet?"
ispackerr(resp) = resptype(resp) == 128

"Is the packet a single value packet?"
ispacksingleval(resp) = resptype(resp) ∈ (8,9)
"Is the packet a single integer value packet?"
ispacksinglevali(resp) = resptype(resp) == 8
"Is the packet a single float value packet?"
ispacksinglevalf(resp) = resptype(resp) == 9

"Is the packet a stream data packet?"
ispackstreamdata(resp) = resptype(resp) ∈ (15, 17, 19)
"Is the packet a stream data packet with 4-byte IEEE floats?"
ispackstreamfloat(resp) = resptype(resp) == 19
"Is the packet a stream data packet with raw 2-byte binary numbers?"
ispackstreambin2(resp) = resptype(resp) == 16
"Is the packet a stream data packet with raw 3-byte binary numbers?"
ispackstreambin3(resp) = resptype(resp) == 17

"Return the number of rows of array data packet"
strpacknum(resp) = Int(ntoh(reinterpret(UInt16, resp[5:6])[1]))
"Return the number of columns of array data packet"
strpacklen(resp) = Int(ntoh(reinterpret(UInt16, resp[7:8])[1]))

"Is the packet an array data packet with 4-byte IEEE floating point numbers?"
ispackarray(resp) = resptype(resp) == 33

"Is the packet a valid packet type?"
ispacktypevalid(resp) = resptype(resp) ∈ (4, 8, 9, 16, 17, 19, 33, 128)

"Read 8 byte header from socket"
function readdtcheader!(io, buf::AbstractVector{UInt8})

    readbytes!(io, buf, 8)

    return resptype(resp)
end

ext: jl


text:
@testset "GPS L1" begin

    gpsl1 = GPSL1(use_gpu = Val(true))
    @test @inferred(get_center_frequency(gpsl1)) == 1.57542e9Hz
    @test @inferred(get_code_length(gpsl1)) == 1023
    @test @inferred(get_secondary_code_length(gpsl1)) == 1
    CUDA.@allowscalar @test @inferred(get_code(gpsl1, 0, 1)) == 1
    CUDA.@allowscalar @test @inferred(get_code(gpsl1, 0.0, 1)) == 1
    CUDA.@allowscalar @test @inferred(get_code_unsafe(gpsl1, 0.0, 1)) == 1
    @test @inferred(get_data_frequency(gpsl1)) == 50Hz
    @test @inferred(get_code_frequency(gpsl1)) == 1023e3Hz
    CUDA.@allowscalar @test gpsl1.codes[:,1] == L1_SAT1_CODE_GPU

end


text:
#=
Limpieza da datos para los plots

El objetivo de este código es obtener y ordenar
datos de COVID19 del ministerio de ciencias.

Cada archivo se ordena por keys principales
(por ejemplo, nombre+codigo comuna o region)
y sets de datos del mismo tipo (como casos diarios).

Muchos valores se repiten, como población y region,
porlo que son omitidos en los archivos.
=#

# TODO: funcion para convertir de tipo de datos una columna
# TODO: hacer columna de aumento junto a últimos casos
# TODO: usar mejor las dependencias

begin
    # Esto está horrible
    using Pkg
    try
        using DataFrames
    catch ArgumentError
        Pkg.add("DataFrames")
        using DataFrames
    end
    try
        using  CSV
    catch ArgumentError
        Pkg.add("CSV")
        using  CSV
    end
    try
        using  FilePaths
    catch ArgumentError
        Pkg.add("FilePaths")
        using  FilePaths
    end
end

function source_path(subpath::String)::String
    "https://raw.githubusercontent.com/MinCiencia/Datos-COVID19/master/output/" * subpath
end

function download_dataset(sourcepath, filename, path=joinpath("data", "input"))
    download(source_path(sourcepath), joinpath(path, filename))
end

function update_datasets!()
    download_dataset("producto1/Covid-19.csv", "producto1.csv")
    download_dataset("producto8/UCI.csv", "producto8.csv")
    download_dataset("producto25/CasosActualesPorComuna.csv", "producto25.csv")
    download_dataset("producto52/Camas_UCI.csv", "producto52.csv")
    download_dataset("producto65/PositividadPorComuna.csv", "producto65.csv")
    download_dataset("producto74/paso_a_paso.csv", "producto74.csv")
end

function rename_colum!(df::DataFrame, before::String, after::String)
    if in(before, names(df))
        rename!(df, Dict(Symbol(before) => Symbol(after)))
    end
end

function rename_cols!(df::DataFrame)
    rename_colum!(df, "Poblacion", "poblacion")
    rename_colum!(df, "Codigo comuna", "codigo")
    rename_colum!(df, "codigo_comuna", "codigo")
    rename_colum!(df, "Comuna", "nombre")
    rename_colum!(df, "comuna_residencia", "nombre")
end

"Casos acumulados por comuna (producto 1)"
function make_total_cases()
    outfile = let
        df = CSV.read("data/input/producto1.csv", DataFrame)
        # TODO: varias comunas les faltan días y se eliminan
        dropmissing!(df)
        rename_cols!(df)
        df = df[:, [3, 4, 6:end - 1...]] # La última fila es la tasa
        df[!, 3:end] = convert.(Int, df[:, 3:end])
        CSV.write("data/output/casos_incremental_comunas.csv", df)
    end
    let
        # Ultimos casos
        df = CSV.read(outfile, DataFrame)
        df = df[:, [1, 2, end]]
        rename!(df, Dict(last(names(df)) => "casos_totales"))
        CSV.write("data/output/ultimos_casos_incremental_comunas.csv", df)
    end
end

"Población"
function make_population()
    let
        # Se utiliza un archivo elegido arbitrariamente
        df = CSV.read("data/input/producto1.csv", DataFrame)
        df = df[:, [3, 4, 5]]
        dropmissing!(df)
        rename_cols!(df)
        df[!, 3] = convert.(Int, df[:, 3])
        CSV.write("data/output/poblacion_por_comuna.csv", df)
    end
end

"Casos activos por comuna (producto 25)"
function make_active_cases()
    outfile = let
        # Arreglos en el archivos de comunas
        df = CSV.read("data/input/producto25.csv", DataFrame)
        dropmissing!(df)
        rename_cols!(df)
        df = df[:, [3, 4, 6:end...]]
        df[!, 3:end] = convert.(Int, df[:, 3:end])
        CSV.write("data/output/casos_activos_comunas.csv", df)
    end
    let
        # Tabla de últimos casos activos por comuna
        df = CSV.read(outfile, DataFrame)
        df = df[:, [1, 2, end]]
        rename!(df, Dict(last(names(df)) => "casos_activos"))
        CSV.write("data/output/ultimos_casos_activos_comunas.csv", df)
    end
end

"Camas UCI por region (producto 8)"
function make_uci()
    let
        df = CSV.read("data/input/producto8.csv", DataFrame)
        df = df[:, [1, 2, 4:end...]]
        CSV.write("data/output/camas_uci_regiones.csv", df)
    end
    let
        # Ultimos datos de camas UCI
        df = CSV.read("data/input/producto8.csv", DataFrame)
        df = df[:, [1, end]]
        rename!(df, ["nombre", "camas_uci"])
        CSV.write("data/output/ultimas_camas_uci_regiones.csv", df)
    end
end

"Porcentage camas UCI por región (producto 52)"
function make_uci_porcentage()
    outfile = let
        df = CSV.read("data/input/producto52.csv", DataFrame)
        df = filter(row -> row.Region != "Total", df)
        g = groupby(df, 1)
        n = names(df)[3:end]
        # Esto asume que el orden de `x` es
        # 1. Camas habilitadas
        # 2. Camas ocupadas COVID-19
        # 3. Camas ocupadas no COVID-19
        df = combine(g, n .=> (d -> round(100 * (d[2] + d[3]) / d[1]; digits=2)) .=> n)
        CSV.write("data/output/porcentage_camas_uci_regiones.csv", df)
    end
    let
        df = CSV.read(outfile, DataFrame)
        df = df[:, [1, end]]
        rename!(df, Dict(last(names(df)) => "porcentage_uci"))
        CSV.write("data/output/ultimo_porcentage_camas_uci_regiones.csv", df)
    end
end

"Positividad por comuna (producto 65)"
function make_positivity()
    outfile = let
        df = CSV.read("data/input/producto65.csv", DataFrame)
        df = df[:, [3, 4, 6:end...]]
        rename_cols!(df)
        CSV.write("data/output/positividad_comunas.csv", df)
    end
    let
        # Solo última positividad
        df = CSV.read(outfile, DataFrame)
        df = df[:, [1, 2, end]]
        rename!(df, Dict(last(names(df)) => "positividad"))
        CSV.write("data/output/ultima_positividad_comunas.csv", df)
    end
end

"Plan paso a paso (producto 74)"
function make_step_by_step()
    # Estos datos se separan en zonas, donde cada región tiene
    # zona Urbana y Rural, o Total. Para simplificar esto, se
    # considerará el mínimo entre entre los valores de la zona de cada comuna
    outfile = let
        df = CSV.read("data/input/producto74.csv", DataFrame)
        df = df[:, 3:end]
        rename_cols!(df)
        df = combine(groupby(df, 1:2), names(df)[4:end] .=> minimum .=> names(df)[4:end])
        CSV.write("data/output/plan_paso_a_paso.csv", df)
    end
    let
        # Solo último
        df = CSV.read(outfile, DataFrame)
        df = df[:, [1, 2, end]]
        rename!(df, Dict(last(names(df)) => "paso_a_paso"))
        CSV.write("data/output/ultimo_plan_paso_a_paso.csv", df)
    end
end

@time begin
    # Download
    update_datasets!()
    # CleanUp
    make_active_cases()
    make_positivity()
    make_uci()
    make_uci_porcentage()
    make_total_cases()
    make_population()
    make_step_by_step()
end

max_stars_repo_name: benjavicente/covid-maps

max_issues_repo_name: benjavicente/covid-maps

max_forks_repo_name: benjavicente/covid-maps


text:
# Note that this script can accept some limited command-line arguments, run
# `julia build_tarballs.jl --help` to see a usage message.
using BinaryBuilder, Pkg

name = "libdrm"
version = v"2.4.103"

# Collection of sources required to complete build
sources = [
    ArchiveSource("https://dri.freedesktop.org/libdrm/libdrm-2.4.103.tar.xz", "3fe0affdba6460166a7323290c18cf68e9b59edcb520722826cb244e9cb50222"),
    DirectorySource("./bundled")
]

# Bash recipe for building across all platforms
script = raw"""
cd $WORKSPACE/srcdir
for f in ${WORKSPACE}/srcdir/patches/*.patch; do
    atomic_patch -p1 ${f}
done
cd libdrm-*
meson --cross-file=${MESON_TARGET_TOOLCHAIN} -Dudev=false -Dvalgrind=false build
ninja -C build install
"""

# These are the platforms we will build for by default, unless further
# platforms are passed in on the command line
platforms = filter(Sys.islinux, supported_platforms())

# The products that we will ensure are always built
products = [
    LibraryProduct("libdrm", :libdrm)
]

# Dependencies that must be installed before this package can be built
dependencies = [
    Dependency(PackageSpec(name="Xorg_libpciaccess_jll", uuid="a65dc6b1-eb27-53a1-bb3e-dea574b5389e"))
]

# Build the tarballs, and possibly a `build.jl` as well.
build_tarballs(ARGS, name, version, sources, script, platforms, products, dependencies)

max_stars_repo_name: waralex/Yggdrasil

max_issues_repo_name: waralex/Yggdrasil

max_forks_repo_name: waralex/Yggdrasil


text:
using Test, Random, StatsBase
using Zygote
using BetaVQE.VAN
using BetaVQE.VAN:bitarray, get_energy, free_energy, network

@testset "normalize" begin
    Random.seed!(2)
    nbits = 6
    nhiddens = [10,10]
    model = AutoRegressiveModel(nbits, nhiddens)
    configs = bitarray(collect(0:(1<<nbits-1)), nbits)
    logp = get_logp(model, configs)
    norm = sum(exp.(logp))

    @test isapprox(norm, 1.0, rtol=1e-5)
end

@testset "sample" begin
    Random.seed!(3)
    nbits = 4
    K = randn(nbits, nbits)
    K = (K+K')/2
    nsamples = 5000
    nhiddens = [100]
    β = 1.0
    model = AutoRegressiveModel(nbits, nhiddens)

    configs = bitarray(collect(0:(1<<nbits-1)), nbits)
    logp = get_logp(model, configs)
    f = sum(exp.(logp) .* (get_energy(K, configs) + get_logp(model, configs)))

    samples = gen_samples(model, nsamples)
    f_sample = free_energy(K, model, samples)
    @test Zygote.gradient(free_energy, K, model, samples)[2] isa NamedTuple
    @test isapprox(f, f_sample, rtol=1e-2)
end

@testset "autoregressive" begin
    Random.seed!(2)
    nbits = 6
    nbatchs = 4
    nhiddens = [10, 20, 30]
    model = AutoRegressiveModel(nbits, nhiddens)
    samples = rand(0:1, nbits, nbatchs)

    f(model, samples, n, b) = network(model, samples)[n, b]

    for n in 1:nbits
        for b in 1:nbatchs
            g = gradient(f, model, samples, n, b)[2]
            dependency = (g .!= 0)
            correct = BitArray( x< n && y==b  for x = 1:nbits, y = 1:nbatchs)
            @test all(dependency .<= correct)
        end
    end
end

@testset "gradscorefunction" begin
    Random.seed!(2)
    nbits = 6
    nbatchs = 10000
    nhiddens = [10, 20]
    model = AutoRegressiveModel(nbits, nhiddens)
    samples = gen_samples(model, nbatchs)

    score(model, samples) = mean(get_logp(model, samples))
    grad = gradient(score, model, samples)[1]
    δ = collect(Iterators.flatten((grad.W..., grad.b...)))
    @test all(isapprox.(δ, 0.0, atol=1e-2))
end


text:
function write_benchmarks(io::IO, bench::AbstractDict{String,<:AbstractDict})
    println(io, "Benchmark,File,Time(s)")
    for (b, d) in bench
        for (f, t) in d
            println(io, b, ',', f, ',', t)
        end
    end
end
function write_benchmarks(io::IO, bench::AbstractDict{String,Float64})
    println(io, "Benchmark,Time(s)")
    for (b, t) in bench
        println(io, b, ',', t)
    end
end

function write_benchmarks(filename::AbstractString, bench)
    open(filename, "w") do io
        write_benchmarks(io, bench)
    end
end


text:
# Initialize $JULIA_PKGDIR, in case this is the first time the test is run:
Pkg.init()

# Update all installed packages to reflect upstream changes:
Pkg.update()

# Install dependencies:
info("Pkg.add(PyCall)")
Pkg.add("PyCall")

# Show Julia information in verbose mode:
versioninfo(true)

max_stars_repo_name: tkf/pyjulia-testing-template

max_issues_repo_name: tkf/pyjulia-testing-template

max_forks_repo_name: tkf/pyjulia-testing-template


text:
eval(quote
    import .Polyhedra: polyhedron
    export polyhedron
    using .Polyhedra: HRep, VRep,
                      removehredundancy!, removevredundancy!
    import JuMP, GLPK

    function default_polyhedra_backend(P, N::Type{<:Number})
        if LazySets.dim(P) == 1
            return default_polyhedra_backend_1d(N)
        else
            return default_polyhedra_backend_nd(N)
        end
    end

    function default_polyhedra_backend_1d(N::Type{<:Number}, solver=nothing)
        return Polyhedra.IntervalLibrary{N}()
    end

    function default_polyhedra_backend_nd(N::Type{<:Number},
                                          solver=default_lp_solver_polyhedra(N))
        return Polyhedra.DefaultLibrary{N}(solver)
    end

    function default_lp_solver_polyhedra(N::Type{<:AbstractFloat};
                                         presolve::Bool=true)
        if presolve
            return JuMP.optimizer_with_attributes(GLPK.Optimizer,
                                                  "presolve" => GLPK.ON)
        else
            return JuMP.optimizer_with_attributes(GLPK.Optimizer)
        end
    end

    function default_lp_solver_polyhedra(N::Type{<:Rational};
                                         presolve::Bool=false)
        if presolve
            return JuMP.optimizer_with_attributes(
                () -> GLPK.Optimizer(method=GLPK.EXACT),
                "presolve" => GLPK.ON)
        else
            return JuMP.optimizer_with_attributes(
                () -> GLPK.Optimizer(method=GLPK.EXACT))
        end
    end
end)

eval(load_polyhedra_hpolytope())
eval(load_polyhedra_hpolyhedron())
eval(load_polyhedra_vpolytope())
eval(load_polyhedra_mesh())
eval(load_polyhedra_concretize_cpa())


text:
module CMAEvolutionStrategy
using LinearAlgebra, Printf, Statistics, Dates, Random

export minimize, xbest, fbest, population_mean

include("optimizer.jl")
include("print.jl")
include("stop.jl")
include("log.jl")
include("constraints.jl")
include("noise.jl")

"""
    xbest(result)

Extract input `x` that resulted in the lowest function value ever.
"""
xbest(o::Optimizer{<:Any, <:BasicLogger}) = transform(o.p.constraints, o.logger.xbest[end])
"""
    fbest(result)

Extract lowest function value ever evaluated.
"""
fbest(o::Optimizer{<:Any, <:BasicLogger}) = o.logger.fbest[end]
"""
    population_mean(result)

Extract the current mean of the optimizer.
"""
population_mean(o::Optimizer) = transform(o.p.constraints, o.p.mean)

function run!(o, f)
    start!(o.stop)
    while true
        y = sample(o.p)
        fvals = evaluate(o.p, f, compute_input(o.p, y))
        perm = sortperm(fvals)
        log!(o, y, fvals, perm)
        noise_handling!(o.p, f, y, fvals, perm)
        update!(o.p, y, perm)
        terminate!(o) && break
        if o.logger.verbosity > 0 &&
           (o.stop.it < 4 ||
            o.stop.it % 100 == 0 ||
            time() - o.logger.times[end] > 2)
           print_state(o)
       end
    end
    if o.logger.verbosity > 0
        print_state(o)
    end
    o
end
"""
    minimize(f, x0, s0;
             lower = nothing,
             upper = nothing,
             constraints = _constraints(lower, upper),
             noise_handling = nothing,
             popsize = 4 + floor(Int, 3*log(length(x0))),
             callback = (o, y, fvals, perm) -> nothing,
             parallel_evaluation = false,
             multi_threading = false,
             verbosity = 1,
             seed = rand(UInt),
             logger = BasicLogger(x0, verbosity = verbosity, callback = callback),
             maxtime = nothing,
             maxiter = nothing,
             maxfevals = nothing,
             stagnation = 100 + 100 * length(x0)^1.5/popsize,
             ftarget = nothing,
             xtol = nothing,
             ftol = 1e-11)

Minimize function `f` starting around `x0` with initial covariance `s0 * I`
under box constraints `lower .<= x0 .<= upper`, where `x0`, `lower` and `upper`
are vectors of the same length or `nothing`.

The result is an `Optimizer` object from which e.g. [`xbest`](@ref), [`fbest`](@ref)
or [`population_mean`](@ref) can be extracted.

If `parallel_evaluation = true`, the objective function `f` receives matrices
of `n` rows (`n = length(x0)`) and `popsize` columns and should return a vector of
length `popsize`. To use multi-threaded parallel evaluation of the objective function,
set `multi_threading = true` and start julia with multiple threads
(c.f. julia manual for the multi-threading setup).
"""
function minimize(f, x0, s0;
                  kwargs...)
    o = Optimizer(x0, s0; kwargs...)
    run!(o, f)
end
end # module

max_stars_repo_name: jbrea/CMAEvolutionStrategy

max_issues_repo_name: jbrea/CMAEvolutionStrategy


text:
using ScikitLearn.CrossValidation: cross_val_score
@sk_import naive_bayes: GaussianNB

function update_weights(data, e, closest_same, closest_other, weights,
						weights_mult, m, k, max_f_vals, min_f_vals, mu_vals, tinfo)

	# Compute ReliefF weights.
	for t = 1:size(data, 2)

		# Penalty term
		penalty = sum(abs.(e[t] .- closest_same[:, t])/(max_f_vals[t] .- min_f_vals[t] .+ eps(Float64)))

		# Reward term
		reward = sum(weights_mult .* (abs.(e[t] .- closest_other[:, t])/(max_f_vals[t] .- min_f_vals[t] .+ eps(Float64))))

		# Weights update
		weights[t] = weights[t] - penalty/(m*k) + reward/(m*k)
	end

	# Get maximal ReliefF weight and compute epsilon values.
	max_weight = maximum(weights)
	eps = (max_weight .- weights)./max_weight

	### Grid search for best temperature from previous step ###

	best_tinfo = tinfo
	idx_removed_feature = -1

	for tinfo_nxt = tinfo-0.3:0.1:tinfo+0.3

		# Compute weights for next value of tinfo.
		weights_nxt = eps .- tinfo.*mu_vals

		# Rank features.
		enumerated_weights = [weights_nxt; collect(1:size(weights_nxt, 2))[:,:]']
		rank = zeros(Int64, size(weights_nxt, 2))
		s = enumerated_weights[:, sortperm(enumerated_weights[1,:], rev=true)]
		rank[convert.(Int64, s[2, :])] = 1:size(weights_nxt, 2)

		# Remove lowest ranked feature.
		msk_rm = rank .!= length(weights_nxt)

		# Perform 5-fold cross validation.
		data_filt = data[:, msk_rm]

		# Compare to current maximal CV value.
		cv_val_nxt = Statistics.mean(cross_val_score(GaussianNB(), X, y; cv=5))
		# If CV value greater than current maximal, save current
		# CV score, tinfo and feature weights.
		if cv_val_nxt > max_cv_val
			# Set current tinfo value as best.
			best_tinfo = tinfo_nxt
			# Get index of removed feature.
			idx_removed_feature = findall(msk_rm)[1][2]
		end
	end

	###########################################################

	return idx_removed_feature, best_tinfo

end

# Todo: Assign lowest rank to feature that is evaporated in next step.
#

max_stars_repo_name: Architecton/diplomska-naloga-koda

max_issues_repo_name: Architecton/diplomska-naloga-koda

max_forks_repo_name: Architecton/diplomska-naloga-koda


text:
using Base.BinaryPlatforms

export AnyPlatform

"""
    AnyPlatform()

A special platform to be used to build platform-independent tarballs, like those
containing only header files.  [`FileProduct`](@ref) is the only product type
allowed with this platform.
"""
struct AnyPlatform <: AbstractPlatform end
Base.BinaryPlatforms.tags(p::AnyPlatform) = Dict{String,String}()
Base.BinaryPlatforms.triplet(::AnyPlatform) = "any"
Base.BinaryPlatforms.arch(::AnyPlatform) = "any"
Base.BinaryPlatforms.os(::AnyPlatform) = "any"
nbits(::AnyPlatform) = 64
proc_family(::AnyPlatform) = "any"
Base.show(io::IO, ::AnyPlatform) = print(io, "AnyPlatform")

"""
    abi_agnostic(p::AbstractPlatform)

Strip out any tags that are not the basic annotations like `libc` and `call_abi`.
"""
function abi_agnostic(p::Platform)
    keeps = ("libc", "call_abi", "os_version")
    filtered_tags = Dict(Symbol(k) => v for (k, v) in tags(p) if k ∈ keeps)
    return Platform(arch(p), os(p); filtered_tags...)
end
abi_agnostic(p::AnyPlatform) = p

"""
    platform_exeext(p::AbstractPlatform)

Get the executable extension for the given Platform.  Includes the leading `.`.
"""
platform_exeext(p::AbstractPlatform) = Sys.iswindows(p) ? ".exe" : ""

# Recursively test for key presence in nested dicts
function haskeys(d, keys...)
    for key in keys
        if !haskey(d, key)
            return false
        end
        d = d[key]
    end
    return true
end
function get_march_flags(arch::String, march::String, compiler::String)
    # First, check if it's in the `"common"`
    if haskeys(ARCHITECTURE_FLAGS, "common", arch, march)
        return ARCHITECTURE_FLAGS["common"][arch][march]
    end
    if haskeys(ARCHITECTURE_FLAGS, compiler, arch, march)
        return ARCHITECTURE_FLAGS[compiler][arch][march]
    end
    # If this march cannot be found, return no flags
    return String[]
end
# If `march` is `nothing`, that means get the "generic" flags
function get_march_flags(arch::String, march::Nothing, compiler::String)
    return get_march_flags(arch, first(get_all_march_names(arch)), compiler)
end
function get_all_arch_names()
    # We don't use Base.BinaryPlatforms.arch_march_isa_mapping here so that
    # we can experiment with adding new architectures in BB before they land in Julia Base.
    return unique(vcat(
        collect(keys(ARCHITECTURE_FLAGS["common"])),
        collect(keys(ARCHITECTURE_FLAGS["gcc"])),
        collect(keys(ARCHITECTURE_FLAGS["clang"])),
    ))
end
function get_all_march_names(arch::String)
    return unique(vcat(
        collect(keys(get(ARCHITECTURE_FLAGS["common"], arch, Dict{String,String}()))),
        collect(keys(get(ARCHITECTURE_FLAGS["gcc"], arch, Dict{String,String}()))),
        collect(keys(get(ARCHITECTURE_FLAGS["clang"], arch, Dict{String,String}()))),
    ))
end

# NOTE: This needs to be kept in sync with `ISAs_by_family` in `Base.BinaryPlatforms.CPUID`
# This will allow us to detect these names at runtime and select artifacts accordingly.
const ARCHITECTURE_FLAGS = Dict(
    # Many compiler flags are the same across clang and gcc, store those in "common"
    "common" => Dict(
        "i686" => Dict(
            "pentium4" => ["-march=pentium4", "-mtune=generic"],
            "prescott" => ["-march=prescott", "-mtune=prescott"],
        ),
        "x86_64" => Dict(
            # Better be always explicit about `-march` & `-mtune`:
            # https://lemire.me/blog/2018/07/25/it-is-more-complicated-than-i-thought-mtune-march-in-gcc/
            "x86_64" => ["-march=x86-64", "-mtune=generic"],
            "avx"    => ["-march=sandybridge", "-mtune=sandybridge"],
            "avx2"   => ["-march=haswell", "-mtune=haswell"],
            "avx512" => ["-march=skylake-avx512", "-mtune=skylake-avx512"],
        ),
        "armv6l" => Dict(
            # This is the only known armv6l chip that runs Julia, so it's the only one we care about.
            "arm1176jzfs" => ["-mcpu=arm1176jzf-s", "-mfpu=vfp", "-mfloat-abi=hard"],
        ),
        "armv7l" => Dict(
            # Base armv7l architecture, with the most basic of FPU's
            "armv7l"   => ["-march=armv7-a", "-mtune=generic-armv7-a", "-mfpu=vfpv3", "-mfloat-abi=hard"],
            # armv7l plus NEON and vfpv4, (Raspberry Pi 2B+, RK3328, most boards Elliot has access to)
            "neonvfpv4" => ["-march=armv7-a", "-mtune=cortex-a53", "-mfpu=neon-vfpv4", "-mfloat-abi=hard"],
        ),
        "aarch64" => Dict(
            # Base armv8.0-a architecture, tune for generic cortex-a57
            "armv8_0"  => ["-march=armv8-a", "-mtune=cortex-a57"],
        ),
        "powerpc64le" => Dict(
            "power8"  => ["-mcpu=power8", "-mtune=power8"],
            # Note that power9 requires GCC 6+, and we need CPUID for this
            #"power9"  => ["-mcpu=power9", "-mtune=power9"],
            # Eventually, we'll support power10, once we have compilers that support it.
            #"power10" => ["-mcpu=power10", "-mtune=power10"],
        )
    ),
    "gcc" => Dict(
        "aarch64" => Dict(
            # `clang`/`gcc` disagree on `rdm(a)`
            "armv8_1"            => ["-march=armv8-a+lse+crc+rdma", "-mtune=thunderx2t99"],
            # Note that these targets require gcc 9+
            "armv8_2_crypto"     => ["-march=armv8-a+lse+crc+rdma+aes+sha2", "-mtune=cortex-a76"],
            "armv8_4_crypto_sve" => ["-march=armv8-a+les+crc+rdma+aes+sha2+fp16fml+dotprod+sve", "-mtune=cortex-a76"]
        ),
    ),
    "clang" => Dict(
        "aarch64" => Dict(
            # `clang`/`gcc` disagree on `rdm` vs. `rdma`
            "armv8_1"            => ["-march=armv8-a+lse+crc+rdm", "-mtune=thunderx2t99"],
            # Note that these targets require clang 9+
            "armv8_2_crypto"     => ["-march=armv8-a+lse+crc+rdm+aes+sha2", "-mtune=cortex-a76"],
            "armv8_4_crypto_sve" => ["-march=armv8-a+les+crc+rdm+aes+sha2+fp16fml+dotprod+sve", "-mtune=cortex-a76"]
        ),
    ),
)
march(p::AbstractPlatform; default=nothing) = get(tags(p), "march", default)


text:
using Statistics
using Distributions
using ProgressMeter

#=
References
----------
    [1] Sobol, I. M. (2001).  "Global sensitivity indices for nonlinear
        mathematical models and their Monte Carlo estimates."  Mathematics
        and Computers in Simulation, 55(1-3):271-280,
        doi:10.1016/S0378-4754(00)00270-6.
    [2] Saltelli, A. (2002).  "Making best use of model evaluations to
        compute sensitivity indices."  Computer Physics Communications,
        145(2):280-297, doi:10.1016/S0010-4655(02)00280-1.
    [3] Saltelli, A., P. Annoni, I. Azzini, F. Campolongo, M. Ratto, and
        S. Tarantola (2010).  "Variance based sensitivity analysis of model
        output.  Design and estimator for the total sensitivity index."
        Computer Physics Communications, 181(2):259-270,
        doi:10.1016/j.cpc.2009.09.018.
=#

"""
    analyze(data::SobolData, model_output::AbstractArray{<:Number, S}; num_resamples::Union{Nothing, Int} = 1_000, conf_level::Union{Nothing, Number} = 0.95, progress_meter::Bool = true, N_override::Union{Nothing, Integer}=nothing) where S

Performs a Sobol Analysis on the `model_output` produced with the problem
defined by the information in `data` and returns the a dictionary of results
with the sensitivity indices and respective confidence intervals for each of the
parameters defined using the `num_resamples` and `conf_level` keyword args. If these
are Nothing than no confidence intervals will be calculated. The `progress_meter`
keyword argument indicates whether a progress meter will be displayed and defaults
to true. The `N_override` keyword argument allows users to override the `N` used in
a specific `analyze` call to analyze just a subset (useful for convergence graphs).
"""
function analyze(data::SobolData, model_output::AbstractArray{<:Number, S}; num_resamples::Union{Nothing, Int} = 1_000, conf_level::Union{Nothing, Number} = 0.95, progress_meter::Bool = true, N_override::Union{Nothing, Integer}=nothing) where S

    # handle confidence interval flag
    num_nothings = (num_resamples === nothing) + (conf_level === nothing)
    if num_nothings == 1
        error("Number of resamples is $num_resamples, while confidence level is $conf_level ... either none or both must be nothing")
    elseif num_nothings == 2
        conf_flag = false
    else
        conf_flag = true
    end

    # define constants
    calc_second_order = data.calc_second_order
    D = length(data.params) # number of uncertain parameters in problem

    # deal with overriding N
    if N_override === nothing
        N = data.N # number of samples
    else
        N_override > data.N ? error("N_override ($N_override) cannot be greater than original N used in sampling ($(data.N))") : nothing
        N = N_override # number of samples

        # reduce the output to just what should be considered for this N
        if data.calc_second_order
            lastrow = N * ((2 * D) + 2)
        else
            lastrow = N * (D + 2)
        end
        model_output = model_output[1:lastrow]
    end

    # values for CI calculations
    if conf_flag
        r = rand(1:N, N, num_resamples)
        Z = quantile(Normal(0.0, 1.0),1 - (1 - conf_level)/2) # calculate z* for CI
    end

    # normalize model output
    model_output = (model_output .- mean(model_output)) ./ std(model_output)

    # separate the model_output into results from matrices "A". "B" and "AB"
    A, B, AB, BA = split_output(model_output, N, D, calc_second_order)

    # preallocate arrays for indices
    firstorder = Array{Float64}(undef, D)
    totalorder = Array{Float64}(undef, D)
    calc_second_order ? secondorder =  fill!(Array{Union{Float64, Missing}}(undef, D, D), missing) : nothing

    # preallocate arrays for confidence intervals
    if conf_flag
        firstorder_conf = Array{Float64}(undef, D)
        totalorder_conf = Array{Float64}(undef, D)
        calc_second_order ? secondorder_conf =  fill!(Array{Union{Float64, Missing}}(undef, D, D), missing) : nothing
    end

    # set up progress meter
    counter = 0
    progress_meter ? p = Progress(D, counter, "Calculating indices for $D parameters ...") : nothing

    for i in 1:D

        # increment progress meter
        counter += 1
        progress_meter ? ProgressMeter.update!(p, counter) : nothing

        # first order and total order indices
        firstorder[i] = first_order(A, AB[:, i], B)[1] # array to scalar with [1]
        totalorder[i] = total_order(A, AB[:, i], B)[1] # array to scalar with [1]

        # first order and total order indice confidence intervals
        conf_flag ? firstorder_conf[i] = Z * std(first_order(A[r], AB[r, i], B[r])) : nothing
        conf_flag ? totalorder_conf[i] = Z * std(total_order(A[r], AB[r, i], B[r])) : nothing

        # second order indices
        if calc_second_order
            for j in (i+1):D
                secondorder[i, j] = second_order(A, AB[:, i], AB[:, j], BA[:, i], B)[1] # array to scalar with [1]
                conf_flag ? secondorder_conf[i,j] = Z * std(skipmissing(second_order(A[r], AB[r, i], AB[r, j], BA[r, i], B[r]))) : nothing
            end
        end
    end

    if calc_second_order
        if conf_flag
            results = Dict(
                :firstorder         => firstorder,
                :firstorder_conf    => firstorder_conf,
                :totalorder         => totalorder,
                :totalorder_conf    => totalorder_conf,
                :secondorder        => secondorder,
                :secondorder_conf   => secondorder_conf
            )
        else
            results = Dict(
                :firstorder         => firstorder,
                :totalorder         => totalorder,
                :secondorder        => secondorder,
            )
        end
    else
        if conf_flag
            results = Dict(
                :firstorder         => firstorder,
                :firstorder_conf    => firstorder_conf,
                :totalorder         => totalorder,
                :totalorder_conf    => totalorder_conf
            )
        else
            results = Dict(
                :firstorder         => firstorder,
                :totalorder         => totalorder,
            )
        end
    end
    return results
end

"""
    first_order(A::AbstractArray{<:Number, N}, AB::AbstractArray{<:Number, N}, B::AbstractArray{<:Number, N})

Calculate the first order sensitivity indices for model outputs given model outputs
separated out into `A`, `AB`, and `A` and normalize by the variance of `[A B]`. [Saltelli et al.,
2010 Table 2 eq (b)]
"""
function first_order(A::AbstractArray{<:Number, N}, AB::AbstractArray{<:Number, N}, B::AbstractArray{<:Number, N}) where N
    return (mean(B .* (AB .- A), dims = 1) ./ var(vcat(A, B), dims = 1, corrected = false))
end

"""
    second_order(A::AbstractArray{<:Number, N}, ABi::AbstractArray{<:Number, N}, ABj::AbstractArray{<:Number, N}, BAi::AbstractArray{<:Number, N}, B::AbstractArray{<:Number, N}) where N

Calculate the second order sensitivity index between two parameters for model outputs
given model outputs separated out into `A`, `AB`, `BA`, and `B` and normalize by
the variance of `[A B]`. [Saltelli et al. , 2002]
"""
function second_order(A::AbstractArray{<:Number, N}, ABi::AbstractArray{<:Number, N}, ABj::AbstractArray{<:Number, N}, BAi::AbstractArray{<:Number, N}, B::AbstractArray{<:Number, N}) where N

    Vj = (mean(BAi .* ABj .- A .* B, dims = 1) ./ var(vcat(A, B), dims = 1, corrected = false))
    Si = first_order(A, ABi, B)
    Sj = first_order(A, ABj, B)

    return Vj .- Si .- Sj
end

"""
    total_order(A::AbstractArray{<:Number, N}, AB::AbstractArray{<:Number, N}, B::AbstractArray{<:Number, N})

Calculate the total order sensitivity indices for model outputs given model outputs
separated out into `A`, `AB`, and `A` and normalize by the variance of `[A B]`. [Saltelli et al.,
2010 Table 2 eq (f)].
"""
function total_order(A::AbstractArray{<:Number, N}, AB::AbstractArray{<:Number, N}, B::AbstractArray{<:Number, N}) where N
    return (0.5 * mean((A .- AB).^2, dims = 1) ./ var(vcat(A, B), dims = 1, corrected = false))
end

"""
    split_output(model_output::AbstractArray{<:Number, S}, N, D, calc_second_order)

Separate the `model_outputs` into matrices "A", "B", "AB", and "BA" for calculation
of sensitvity indices and return those four matrices. If `calc_second_order` is
`False`, `BA` will be `nothing`.
"""
function split_output(model_output::AbstractArray{<:Number, S}, N, D, calc_second_order::Bool) where S

    if calc_second_order
        stepsize = 2 * D + 2
    else
        stepsize = D + 2
    end

    A = model_output[1:stepsize:end]
    B = model_output[stepsize:stepsize:end]

    #preallocate
    AB = Array{Float64}(undef, N, D)
    if calc_second_order
        BA = Array{Float64}(undef, N, D)
    else
        BA = nothing
    end

    for i in 1:D
        AB[:, i] = model_output[i+1:stepsize:end, :]
        if calc_second_order
            BA[:, i] = model_output[i + D + 1:stepsize:end, :]
        end
    end

    return A, B, AB, BA
end

max_stars_repo_name: lrennels/SAJulia

max_issues_repo_name: lrennels/SAJulia


text:
# Note that this script can accept some limited command-line arguments, run
# `julia build_tarballs.jl --help` to see a usage message.
using BinaryBuilder

name = "LibALSABuilder"
version = v"1.1.6"

# Collection of sources required to build LibALSABuilder
sources = [
    "ftp://ftp.alsa-project.org/pub/lib/alsa-lib-1.1.6.tar.bz2" =>
    "5f2cd274b272cae0d0d111e8a9e363f08783329157e8dd68b3de0c096de6d724",

]

# Bash recipe for building across all platforms
script = raw"""
cd $WORKSPACE/srcdir
cd alsa-lib-1.1.6/
./configure --prefix=$prefix --host=$target
make -j${nproc}
make install

"""

# These are the platforms we will build for by default, unless further
# platforms are passed in on the command line
platforms = [
    Linux(:i686, :glibc),
    Linux(:x86_64, :glibc),
    Linux(:aarch64, :glibc),
    Linux(:armv7l, :glibc, :eabihf),
    Linux(:powerpc64le, :glibc)
]

# The products that we will ensure are always built
products(prefix) = [
    LibraryProduct(prefix, "libasound", :libasound)
]

# Dependencies that must be installed before this package can be built
dependencies = [

]

# Build the tarballs, and possibly a `build.jl` as well.
build_tarballs(ARGS, name, version, sources, script, platforms, products, dependencies)

max_stars_repo_name: jpsamaroo/LibALSABuilder

max_issues_repo_name: jpsamaroo/LibALSABuilder

max_forks_repo_name: jpsamaroo/LibALSABuilder


text:
__precompile__()

module Ratios

import Base: convert, promote_rule, *, /, +, -, ^, ==, decompose

export SimpleRatio

struct SimpleRatio{T<:Integer} <: Real
    num::T
    den::T
end

convert(::Type{BigFloat}, r::SimpleRatio{S}) where {S} = BigFloat(r.num)/r.den
function convert(::Type{T}, r::SimpleRatio{S}) where {T<:AbstractFloat,S}
    P = promote_type(T,S)
    convert(T, convert(P, r.num)/convert(P, r.den))
end
convert(::Type{SimpleRatio{T}}, i::Integer) where {T<:Integer} = SimpleRatio{T}(convert(T, i), one(T))
convert(::Type{SimpleRatio{T}}, r::Rational{S}) where {T<:Integer, S<:Integer} = SimpleRatio(convert(T, r.num), convert(T, r.den))
convert(::Type{Rational{T}}, r::SimpleRatio{S}) where {T<:Integer, S<:Integer} = convert(T, r.num) // convert(T, r.den)

*(x::SimpleRatio, y::SimpleRatio) = SimpleRatio(x.num*y.num, x.den*y.den)
*(x::SimpleRatio, y::Bool) = SimpleRatio(x.num*y, x.den)
*(x::SimpleRatio, y::Integer) = SimpleRatio(x.num*y, x.den)
*(x::Bool, y::SimpleRatio) = SimpleRatio(x*y.num, y.den)
*(x::Integer, y::SimpleRatio) = SimpleRatio(x*y.num, y.den)
/(x::SimpleRatio, y::SimpleRatio) = SimpleRatio(x.num*y.den, x.den*y.num)
/(x::SimpleRatio, y::Integer) = SimpleRatio(x.num, x.den*y)
/(x::Integer, y::SimpleRatio) = SimpleRatio(x*y.den, y.num)
+(x::Integer, y::SimpleRatio) = SimpleRatio(x*y.den + y.num, y.den)
-(x::Integer, y::SimpleRatio) = SimpleRatio(x*y.den - y.num, y.den)
+(x::SimpleRatio, y::SimpleRatio) = SimpleRatio(x.num*y.den + x.den*y.num, x.den*y.den)
-(x::SimpleRatio, y::SimpleRatio) = SimpleRatio(x.num*y.den - x.den*y.num, x.den*y.den)
^(x::SimpleRatio, y::Integer) = SimpleRatio(x.num^y, x.den^y)

-(x::SimpleRatio{T}) where {T<:Signed} = SimpleRatio(-x.num, x.den)
-(x::SimpleRatio{T}) where {T<:Unsigned} = throw(VERSION < v"0.7.0-DEV.1269" ? OverflowError() : OverflowError("cannot negate unsigned number"))

promote_rule(::Type{SimpleRatio{T}}, ::Type{S}) where {T<:Integer,S<:Integer} = SimpleRatio{promote_type(T,S)}
promote_rule(::Type{SimpleRatio{T}}, ::Type{SimpleRatio{S}}) where {T<:Integer,S<:Integer} = SimpleRatio{promote_type(T,S)}
promote_rule(::Type{SimpleRatio{T}}, ::Type{S}) where {T<:Integer,S<:AbstractFloat} = promote_type(T,S)
promote_rule(::Type{SimpleRatio{T}}, ::Type{Rational{S}}) where {T<:Integer,S<:Integer} = Rational{promote_type(T,S)}

==(x::SimpleRatio, y::SimpleRatio) = x.num*y.den == x.den*y.num

==(x::SimpleRatio, y::Integer) = x.num == x.den*y
==(x::Integer, y::SimpleRatio) = x*y.den == y.num

function ==(x::AbstractFloat, q::SimpleRatio)
    if isfinite(x)
        (count_ones(q.den) == 1) & (x*q.den == q.num)
    else
        x == q.num/q.den
    end
end

==(q::SimpleRatio, x::AbstractFloat) = x == q

decompose(x::SimpleRatio) = x.num, 0, x.den

end


text:
# This file is auto-generated by AWSMetadata.jl
using AWS
using AWS.AWSServices: outposts
using AWS.Compat
using AWS.UUIDs

"""
    CreateOutpost()

Creates an Outpost.

# Required Parameters
- `Name`:
- `SiteId`:

# Optional Parameters
- `AvailabilityZone`:
- `AvailabilityZoneId`:
- `Description`:
- `Tags`: The tags to apply to the Outpost.
"""
create_outpost(Name, SiteId; aws_config::AWSConfig=global_aws_config()) = outposts("POST", "/outposts", Dict{String, Any}("Name"=>Name, "SiteId"=>SiteId); aws_config=aws_config)
create_outpost(Name, SiteId, args::AbstractDict{String, <:Any}; aws_config::AWSConfig=global_aws_config()) = outposts("POST", "/outposts", Dict{String, Any}(mergewith(_merge, Dict{String, Any}("Name"=>Name, "SiteId"=>SiteId), args)); aws_config=aws_config)

"""
    DeleteOutpost()

Deletes the Outpost.

# Required Parameters
- `OutpostId`:

"""
delete_outpost(OutpostId; aws_config::AWSConfig=global_aws_config()) = outposts("DELETE", "/outposts/$(OutpostId)"; aws_config=aws_config)
delete_outpost(OutpostId, args::AbstractDict{String, <:Any}; aws_config::AWSConfig=global_aws_config()) = outposts("DELETE", "/outposts/$(OutpostId)", args; aws_config=aws_config)

"""
    DeleteSite()

Deletes the site.

# Required Parameters
- `SiteId`:

"""
delete_site(SiteId; aws_config::AWSConfig=global_aws_config()) = outposts("DELETE", "/sites/$(SiteId)"; aws_config=aws_config)
delete_site(SiteId, args::AbstractDict{String, <:Any}; aws_config::AWSConfig=global_aws_config()) = outposts("DELETE", "/sites/$(SiteId)", args; aws_config=aws_config)

"""
    GetOutpost()

Gets information about the specified Outpost.

# Required Parameters
- `OutpostId`:

"""
get_outpost(OutpostId; aws_config::AWSConfig=global_aws_config()) = outposts("GET", "/outposts/$(OutpostId)"; aws_config=aws_config)
get_outpost(OutpostId, args::AbstractDict{String, <:Any}; aws_config::AWSConfig=global_aws_config()) = outposts("GET", "/outposts/$(OutpostId)", args; aws_config=aws_config)

"""
    GetOutpostInstanceTypes()

Lists the instance types for the specified Outpost.

# Required Parameters
- `OutpostId`:

# Optional Parameters
- `MaxResults`:
- `NextToken`:
"""
get_outpost_instance_types(OutpostId; aws_config::AWSConfig=global_aws_config()) = outposts("GET", "/outposts/$(OutpostId)/instanceTypes"; aws_config=aws_config)
get_outpost_instance_types(OutpostId, args::AbstractDict{String, <:Any}; aws_config::AWSConfig=global_aws_config()) = outposts("GET", "/outposts/$(OutpostId)/instanceTypes", args; aws_config=aws_config)

"""
    ListOutposts()

List the Outposts for your AWS account.

# Optional Parameters
- `MaxResults`:
- `NextToken`:
"""
list_outposts(; aws_config::AWSConfig=global_aws_config()) = outposts("GET", "/outposts"; aws_config=aws_config)
list_outposts(args::AbstractDict{String, Any}; aws_config::AWSConfig=global_aws_config()) = outposts("GET", "/outposts", args; aws_config=aws_config)

"""
    ListSites()

Lists the sites for the specified AWS account.

# Optional Parameters
- `MaxResults`:
- `NextToken`:
"""
list_sites(; aws_config::AWSConfig=global_aws_config()) = outposts("GET", "/sites"; aws_config=aws_config)
list_sites(args::AbstractDict{String, Any}; aws_config::AWSConfig=global_aws_config()) = outposts("GET", "/sites", args; aws_config=aws_config)


text:
using SearchablePDFs
SearchablePDFs.comonicon_install()


text:
# ---
# title: 525. Contiguous Array
# id: problem525
# author: Indigo
# date: 2021-06-03
# difficulty: Medium
# categories: Hash Table
# link: <https://leetcode.com/problems/contiguous-array/description/>
# hidden: true
# ---
#
# Given a binary array, find the maximum length of a contiguous subarray with
# equal number of 0 and 1.
#
# **Example 1:**
#
#
#
#     Input: [0,1]
#     Output: 2
#     Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
#
#
# **Example 2:**
#
#
#
#     Input: [0,1,0]
#     Output: 2
#     Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
#
#
# **Note:** The length of the given binary array will not exceed 50,000.
#
#
## @lc code=start
using LeetCode

function find_max_length(nums::Vector{Int})
    dc = Dict(0 => 0)
    res = acc = 0
    @inbounds for i in eachindex(nums)
        acc += nums[i] == 0 ? -1 : 1
        haskey(dc, acc) ? res = max(res, i - dc[acc]) : dc[acc] = i
    end
    return res
end
## @lc code=end