text:
#-------------------------------------------------------------------------------
# Flags hold auxilary information about tokens/nonterminals which the Kind
# doesn't capture in a nice way.
#
# TODO: Use `primitive type SyntaxFlags 16 end` rather than an alias?
const RawFlags = UInt16
const EMPTY_FLAGS = RawFlags(0)
const TRIVIA_FLAG = RawFlags(1<<0)
# Some of the following flags are head-specific and could probably be allowed
# to cover the same bits...
const INFIX_FLAG  = RawFlags(1<<1)
# Record whether syntactic operators were dotted
const DOTOP_FLAG = RawFlags(1<<2)
# Set when kind == K"String" was triple-delimited as with """ or ```
const TRIPLE_STRING_FLAG = RawFlags(1<<3)
# Set when a string or identifier needs "raw string" unescaping
const RAW_STRING_FLAG = RawFlags(1<<4)
# try-finally-catch
const TRY_CATCH_AFTER_FINALLY_FLAG = RawFlags(1<<5)
# Record whether operator has a suffix
const SUFFIXED_FLAG        = RawFlags(1<<6)

# Token-only flag
# Record whether a token had preceding whitespace
const PRECEDING_WHITESPACE_FLAG = RawFlags(1<<7)

# Flags holding the dimension of an nrow or other UInt8 not held in the source
const NUMERIC_FLAGS = RawFlags(RawFlags(0xff)<<8)
# Todo ERROR_FLAG = 0x8000 ?

function set_numeric_flags(n::Integer)
    f = RawFlags((n << 8) & NUMERIC_FLAGS)
    if numeric_flags(f) != n
        error("Numeric flags unable to hold large integer $n")
    end
    f
end

function numeric_flags(f::RawFlags)
    Int((f >> 8) % UInt8)
end

function remove_flags(n::RawFlags, fs...)
    RawFlags(n & ~(RawFlags((|)(fs...))))
end

# Return true if any of `test_flags` are set
has_flags(flags::RawFlags, test_flags) = (flags & test_flags) != 0

#-------------------------------------------------------------------------------
struct SyntaxHead
    kind::Kind
    flags::RawFlags
end

kind(head::SyntaxHead) = head.kind
flags(head::SyntaxHead) = head.flags

function Base.summary(head::SyntaxHead)
    untokenize(head, unique=false, include_flag_suff=false)
end

function untokenize(head::SyntaxHead; unique=true, include_flag_suff=true)
    str = is_error(kind(head)) ? "error" : untokenize(kind(head); unique=unique)
    if is_dotted(head)
        str = "."*str
    end
    # Ignore some flags:
    # DOTOP_FLAG is represented above with . prefix
    # PRECEDING_WHITESPACE_FLAG relates to the environment of this token
    suffix_flags = remove_flags(flags(head), DOTOP_FLAG, PRECEDING_WHITESPACE_FLAG)
    if include_flag_suff && suffix_flags != EMPTY_FLAGS
        str = str*"-"
        is_trivia(head)  && (str = str*"t")
        is_infix(head)   && (str = str*"i")
        has_flags(head, TRIPLE_STRING_FLAG) && (str = str*"s")
        has_flags(head, RAW_STRING_FLAG) && (str = str*"r")
        has_flags(head, TRY_CATCH_AFTER_FINALLY_FLAG) && (str = str*"f")
        is_suffixed(head) && (str = str*"S")
        n = numeric_flags(head)
        n != 0 && (str = str*string(n))
    end
    str
end

#-------------------------------------------------------------------------------
# Generic interface for types `T` which have kind and flags:
# 1. Define kind(::T) and flags(::T) directly
# 2. Define head(::T) to return a type like `SyntaxKind` for which `kind` and
#    `flags` are defined
kind(x)  = kind(head(x))
flags(x) = flags(head(x))

# Predicates based on kind() / flags()
is_error(x)  = is_error(kind(x))
has_flags(x, test_flags) = has_flags(flags(x), test_flags)
is_trivia(x) = has_flags(x, TRIVIA_FLAG)
is_infix(x)  = has_flags(x, INFIX_FLAG)
is_dotted(x) = has_flags(x, DOTOP_FLAG)
is_suffixed(x) = has_flags(x, SUFFIXED_FLAG)
is_decorated(x) = is_dotted(x) || is_suffixed(x)
preceding_whitespace(x) = has_flags(x, PRECEDING_WHITESPACE_FLAG)
numeric_flags(x) = numeric_flags(flags(x))

#-------------------------------------------------------------------------------
"""
`SyntaxToken` is a token covering a contiguous byte range in the input text.

We record only the `next_byte` here (the index of the next byte *after* the
token) to avoid duplication of data between neighbouring tokens. This is more
useful than recording the first byte, as it allows an initial fixed sentinel
token to be used for recording the first byte of the first real token.
"""
struct SyntaxToken
    head::SyntaxHead
    orig_kind::Kind
    next_byte::UInt32
end

function SyntaxToken(head::SyntaxHead, next_byte::Integer)
    SyntaxToken(head, kind(head), next_byte)
end

function Base.show(io::IO, tok::SyntaxToken)
    print(io, rpad(untokenize(tok.head, unique=false), 15), " |", tok.next_byte)
end

head(tok::SyntaxToken) = tok.head

#-------------------------------------------------------------------------------

"""
Range in the source text which will become a node in the tree. Can be either a
token (leaf node of the tree) or an interior node, depending on how the
start_mark compares to previous nodes.
"""
struct TaggedRange
    head::SyntaxHead # Kind,flags
    # The following field is used for one of two things:
    # - For leaf nodes it's an index in the tokens array
    # - For non-leaf nodes it points to the index of the first child
    first_token::UInt32
    last_token::UInt32
end

head(range::TaggedRange) = range.head

#-------------------------------------------------------------------------------
struct ParseStreamPosition
    token_index::UInt32  # Index of last token in output
    range_index::UInt32
end

const NO_POSITION = ParseStreamPosition(0, 0)

#-------------------------------------------------------------------------------
"""
ParseStream provides an IO interface for the parser. It
- Wraps the lexer with a lookahead buffer
- Removes insignificant whitespace and comment tokens, shifting them into the
  output implicitly (newlines may be significant depending on `skip_newlines`)
"""
mutable struct ParseStream
    # `textbuf` is a buffer of UTF-8 encoded text of the source code. This is a
    # natural representation as we desire random access and zero-copy parsing
    # of UTF-8 text from various containers, and unsafe_wrap(Vector{UInt8},
    # ...) allows us to use a Vector here.
    #
    # We want `ParseStream` to be concrete so that all `parse_*` functions only
    # need to be compiled once. Thus `textbuf` must not be parameterized here.
    textbuf::Vector{UInt8}
    # GC root for the object which owns the memory in `textbuf`. `nothing` if
    # the `textbuf` owner was unknown (eg, ptr,length was passed)
    text_root::Any
    # Lexer, transforming the input bytes into a token stream
    lexer::Tokenize.Lexers.Lexer{IOBuffer}
    # Lookahead buffer for already lexed tokens
    lookahead::Vector{SyntaxToken}
    lookahead_index::Int
    # Pool of stream positions for use as working space in parsing
    position_pool::Vector{Vector{ParseStreamPosition}}
    # Buffer of finalized tokens
    tokens::Vector{SyntaxToken}
    # Parser output as an ordered sequence of ranges, parent nodes after children.
    ranges::Vector{TaggedRange}
    # Parsing diagnostics (errors/warnings etc)
    diagnostics::Vector{Diagnostic}
    # Counter for number of peek()s we've done without making progress via a bump()
    peek_count::Int
    # (major,minor) version of Julia we're parsing this code for.
    # May be different from VERSION!
    version::Tuple{Int,Int}

    function ParseStream(text_buf::Vector{UInt8}, text_root, next_byte::Integer,
                         version::VersionNumber)
        io = IOBuffer(text_buf)
        seek(io, next_byte-1)
        lexer = Tokenize.Lexers.Lexer(io)
        # To avoid keeping track of the exact Julia development version where new
        # features were added or comparing prerelease strings, we treat prereleases
        # or dev versons as the release version using only major and minor version
        # numbers. This means we're inexact for old dev versions but that seems
        # like an acceptable tradeoff.
        ver = (version.major, version.minor)
        # Initial sentinel token containing the first byte of the first real token.
        sentinel = SyntaxToken(SyntaxHead(K"TOMBSTONE", EMPTY_FLAGS),
                               K"TOMBSTONE", next_byte)
        new(text_buf,
            text_root,
            lexer,
            Vector{SyntaxToken}(),
            1,
            Vector{Vector{ParseStreamPosition}}(),
            SyntaxToken[sentinel],
            Vector{TaggedRange}(),
            Vector{Diagnostic}(),
            0,
            ver)
    end
end

function ParseStream(text::Vector{UInt8}, index::Integer=1; version=VERSION)
    ParseStream(text, text, index, version)
end

# Buffer with unknown owner. Not exactly recommended, but good for C interop
function ParseStream(ptr::Ptr{UInt8}, len::Integer, index::Integer=1; version=VERSION)
    ParseStream(unsafe_wrap(Vector{UInt8}, ptr, len), nothing, index, version)
end

# Buffers originating from strings
function ParseStream(text::String, index::Integer=1; version=VERSION)
    ParseStream(unsafe_wrap(Vector{UInt8}, text),
                text, index, version)
end
function ParseStream(text::SubString, index::Integer=1; version=VERSION)
    # See also IOBuffer(SubString("x"))
    ParseStream(unsafe_wrap(Vector{UInt8}, pointer(text), sizeof(text)),
                text, index, version)
end
function ParseStream(text::AbstractString, index::Integer=1; version=VERSION)
    ParseStream(String(text), index; version=version)
end

# IO-based cases
function ParseStream(io::IOBuffer; version=VERSION)
    ParseStream(io.data, io, position(io)+1, version)
end
function ParseStream(io::Base.GenericIOBuffer; version=VERSION)
    textbuf = unsafe_wrap(Vector{UInt8}, pointer(io.data), length(io.data))
    ParseStream(textbuf, io, position(io)+1, version)
end
function ParseStream(io::IOStream; version=VERSION)
    textbuf = Mmap.mmap(io)
    ParseStream(textbuf, io, position(io)+1, version)
end
function ParseStream(io::IO; version=VERSION)
    textbuf = read(io)
    ParseStream(textbuf, textbuf, 1, version)
end

function Base.show(io::IO, mime::MIME"text/plain", stream::ParseStream)
    println(io, "ParseStream at position $(_next_byte(stream))")
end

function show_diagnostics(io::IO, stream::ParseStream, code)
    show_diagnostics(io, stream.diagnostics, code)
end

# We manage a pool of stream positions as parser working space
function acquire_positions(stream)
    if isempty(stream.position_pool)
        return Vector{ParseStreamPosition}()
    end
    pop!(stream.position_pool)
end

function release_positions(stream, positions)
    empty!(positions)
    push!(stream.position_pool, positions)
end

#-------------------------------------------------------------------------------
# Return true when a token was emitted last at stream position `pos`
function token_is_last(stream, pos)
    return pos.range_index == 0 ||
           pos.token_index > stream.ranges[pos.range_index].last_token
end

# Compute the first byte of a token at given index `i`
function token_first_byte(stream, i)
    stream.tokens[i-1].next_byte
end

function token_last_byte(stream::ParseStream, i)
    stream.tokens[i].next_byte - 1
end

function token_span(stream::ParseStream, i)
    stream.tokens[i].next_byte - stream.tokens[i-1].next_byte
end

function lookahead_token_first_byte(stream, i)
    i == 1 ? _next_byte(stream) : stream.lookahead[i-1].next_byte
end

function lookahead_token_last_byte(stream, i)
    stream.lookahead[i].next_byte - 1
end

#-------------------------------------------------------------------------------
# Stream input interface - the peek_* family of functions

# Buffer several tokens ahead
function _buffer_lookahead_tokens(lexer, lookahead)
    had_whitespace = false
    token_count = 0
    while true
        raw = Tokenize.Lexers.next_token(lexer)
        k = TzTokens.exactkind(raw)
        was_whitespace = k in (K"Whitespace", K"Comment", K"NewlineWs")
        had_whitespace |= was_whitespace
        f = EMPTY_FLAGS
        had_whitespace && (f |= PRECEDING_WHITESPACE_FLAG)
        raw.dotop      && (f |= DOTOP_FLAG)
        raw.suffix     && (f |= SUFFIXED_FLAG)
        push!(lookahead, SyntaxToken(SyntaxHead(k, f), raw.endbyte + 2))
        token_count += 1
        if k == K"EndMarker"
            break
        end
        if !was_whitespace
            # Buffer tokens in batches for lookahead. Generally we want a
            # moderate-size buffer to make sure we hit the fast path of peek(),
            # but not too large to avoid (a) polluting the processor cache and
            # (b) doing unnecessary work when not parsing the whole input.
            had_whitespace = false
            if token_count > 100
                break
            end
        end
    end
end

# Return the index of the next byte of the input
function _next_byte(stream)
    last(stream.tokens).next_byte
end

# Find the index of the next nontrivia token
@inline function _lookahead_index(stream::ParseStream, n::Integer, skip_newlines::Bool)
    # Much of the time we'll be peeking ahead a single token and have one or
    # zero whitespace tokens before the next token. The following code is an
    # unrolled optimized version for that fast path. Empirically it seems we
    # only hit the slow path about 5% of the time here.
    i = stream.lookahead_index
    @inbounds if n == 1 && i+2 <= length(stream.lookahead)
        if skip_newlines
            k = kind(stream.lookahead[i])
            if !(k == K"Whitespace" || k == K"Comment" || k == K"NewlineWs")
                return i
            end
            i += 1
            k = kind(stream.lookahead[i])
            if !(k == K"Whitespace" || k == K"Comment" || k == K"NewlineWs")
                return i
            end
        else
            k = kind(stream.lookahead[i])
            if !(k == K"Whitespace" || k == K"Comment")
                return i
            end
            i += 1
            k = kind(stream.lookahead[i])
            if !(k == K"Whitespace" || k == K"Comment")
                return i
            end
        end
    end
    # Fall through to the general case
    return __lookahead_index(stream, n, skip_newlines)
end

@noinline function __lookahead_index(stream, n, skip_newlines)
    i = stream.lookahead_index
    while true
        if i+1 > length(stream.lookahead)
            n_to_delete = stream.lookahead_index-1
            if n_to_delete > 0.9*length(stream.lookahead)
                Base._deletebeg!(stream.lookahead, n_to_delete)
                i -= n_to_delete
                stream.lookahead_index = 1
            end
            _buffer_lookahead_tokens(stream.lexer, stream.lookahead)
            continue
        end
        k = @inbounds kind(stream.lookahead[i])
        if !((k == K"Whitespace" || k == K"Comment") ||
             (k == K"NewlineWs" && skip_newlines))
            if n == 1
                return i
            end
            n -= 1
        end
        i += 1
    end
end

@noinline function _parser_stuck_error(stream)
    # Optimization: emit unlikely errors in a separate function
    error("The parser seems stuck at byte $(_next_byte(stream))")
end

"""
    peek(stream [, n=1]; skip_newlines=false)

Look ahead in the stream `n` tokens, returning the token kind. Comments and
non-newline whitespace are skipped automatically. Whitespace containing a
single newline is returned as kind `K"NewlineWs"` unless `skip_newlines` is
true.
"""
function Base.peek(stream::ParseStream, n::Integer=1;
                   skip_newlines::Bool=false, skip_whitespace=true)
    kind(peek_token(stream, n; skip_newlines=skip_newlines, skip_whitespace=skip_whitespace))
end

"""
    peek_token(stream [, n=1])

Like `peek`, but return the full token information rather than just the kind.
"""
function peek_token(stream::ParseStream, n::Integer=1;
                    skip_newlines=false, skip_whitespace=true)
    stream.peek_count += 1
    if stream.peek_count > 100_000
        _parser_stuck_error(stream)
    end
    i = _lookahead_index(stream, n, skip_newlines)
    if !skip_whitespace
        i = stream.lookahead_index
    end
    return @inbounds head(stream.lookahead[i])
end

struct FullToken
    head::SyntaxHead
    first_byte::UInt32
    last_byte::UInt32
end

head(t::FullToken) = t.head
first_byte(t::FullToken) = t.first_byte
last_byte(t::FullToken) = t.last_byte
span(t::FullToken) = 1 + last_byte(t) - first_byte(t)

function peek_full_token(stream::ParseStream, n::Integer=1;
                         skip_newlines=false, skip_whitespace=true)
    stream.peek_count += 1
    if stream.peek_count > 100_000
        _parser_stuck_error(stream)
    end
    i = _lookahead_index(stream, n, skip_newlines)
    if !skip_whitespace
        i = stream.lookahead_index
    end
    t = stream.lookahead[i]

    FullToken(head(t), lookahead_token_first_byte(stream, i),
              lookahead_token_last_byte(stream, i))
end

"""
    peek_behind(ps; skip_trivia=true)
    peek_behind(ps, pos::ParseStreamPosition)

Return information about a span which was previously inserted into the output,
defaulting to the most previous nontrivia node when `skip_trivia` is true, or
at the provided position `pos`.

Retroactively inspecting or modifying the parser's output can be confusing, so
using this function should be avoided where possible.
"""
function peek_behind(stream::ParseStream, pos::ParseStreamPosition)
    if token_is_last(stream, pos) && !isempty(stream.tokens)
        t = stream.tokens[pos.token_index]
        return (kind=kind(t),
                flags=flags(t),
                orig_kind=t.orig_kind,
                is_leaf=true)
    elseif !isempty(stream.ranges)
        r = stream.ranges[pos.range_index]
        return (kind=kind(r),
                flags=flags(r),
                orig_kind=K"None",
                is_leaf=false)
    else
        internal_error("Can't peek behind at start of stream")
    end
end

function peek_behind(stream::ParseStream; skip_trivia::Bool=true)
    pos = position(stream)
    if !skip_trivia || !token_is_last(stream, pos)
        return peek_behind(stream, pos)
    else
        token_index = lastindex(stream.tokens)
        range_index = lastindex(stream.ranges)
        last_token_in_nonterminal = isempty(stream.ranges) ? 0 :
                                    stream.ranges[range_index].last_token
        while token_index > last_token_in_nonterminal
            t = stream.tokens[token_index]
            if !is_trivia(t) && kind(t) != K"TOMBSTONE"
                break
            end
            token_index -= 1
        end
        if token_index > 0
            return peek_behind(stream, ParseStreamPosition(token_index, range_index))
        else
            internal_error("Can't peek behind at start of stream")
        end
    end
end

#-------------------------------------------------------------------------------
# Stream output interface - the `bump_*` and `emit_*` family of functions
#
# Though note bump() really does both input and output

# Bump up until the `n`th token
# flags and remap_kind are applied to any non-trivia tokens
function _bump_until_n(stream::ParseStream, n::Integer, flags, remap_kind=K"None")
    if n < stream.lookahead_index
        return
    end
    for i in stream.lookahead_index:n
        tok = stream.lookahead[i]
        k = kind(tok)
        if k == K"EndMarker"
            break
        end
        f = flags | remove_flags((@__MODULE__).flags(tok), PRECEDING_WHITESPACE_FLAG)
        is_trivia = k ∈ (K"Whitespace", K"Comment", K"NewlineWs")
        is_trivia && (f |= TRIVIA_FLAG)
        outk = (is_trivia || remap_kind == K"None") ? k : remap_kind
        h = SyntaxHead(outk, f)
        push!(stream.tokens, SyntaxToken(h, kind(tok), tok.next_byte))
    end
    stream.lookahead_index = n + 1
    # Defuse the time bomb
    stream.peek_count = 0
end

"""
    bump(stream [, flags=EMPTY_FLAGS];
         skip_newlines=false, error, remap_kind)

Shift the current token from the input to the output, adding the given flags.
"""
function bump(stream::ParseStream, flags=EMPTY_FLAGS; skip_newlines=false,
              error=nothing, remap_kind::Kind=K"None")
    emark = position(stream)
    _bump_until_n(stream, _lookahead_index(stream, 1, skip_newlines), flags, remap_kind)
    if !isnothing(error)
        emit(stream, emark, K"error", flags, error=error)
    end
    # Return last token location in output if needed for reset_node!
    return position(stream)
end

"""
Bump comments and whitespace tokens preceding the next token

**Skips newlines** by default.  Set skip_newlines=false to avoid that.
"""
function bump_trivia(stream::ParseStream, flags=EMPTY_FLAGS;
                     skip_newlines=true, error=nothing)
    emark = position(stream)
    _bump_until_n(stream, _lookahead_index(stream, 1, skip_newlines) - 1, EMPTY_FLAGS)
    if !isnothing(error)
        emit(stream, emark, K"error", flags, error=error)
    end
    return position(stream)
end

"""
Bump an invisible zero-width token into the output

This is useful when surrounding syntax implies the presence of a token.  For
example, `2x` means `2*x` via the juxtoposition rules.
"""
function bump_invisible(stream::ParseStream, kind, flags=EMPTY_FLAGS;
                        error=nothing)
    b = _next_byte(stream)
    h = SyntaxHead(kind, flags)
    push!(stream.tokens, SyntaxToken(h, b))
    if !isnothing(error)
        _emit_diagnostic(stream, b, b-1, error=error)
    end
    stream.peek_count = 0
    return position(stream)
end

"""
Bump several tokens, gluing them together into a single token

This is for use in special circumstances where the parser needs to resolve
lexing ambiguities. There's no special whitespace handling — bump any
whitespace if necessary with bump_trivia.
"""
function bump_glue(stream::ParseStream, kind, flags, num_tokens)
    i = stream.lookahead_index
    h = SyntaxHead(kind, flags)
    push!(stream.tokens, SyntaxToken(h, stream.lookahead[i+1].next_byte))
    stream.lookahead_index += num_tokens
    stream.peek_count = 0
    return position(stream)
end

"""
    bump_split(stream, token_spec1, [token_spec2 ...])

Bump the next token, splitting it into several pieces

Tokens are defined by a number of `token_spec` of shape `(nbyte, kind, flags)`.
The number of input bytes of the last spec is taken from the remaining bytes of
the input token, with the associated `nbyte` ignored.

This is a hack which helps resolves the occasional lexing ambiguity. For
example
* Whether .+ should be a single token or the composite (. +) which is used for
  standalone operators.
* Whether ... is splatting (most of the time) or three . tokens in import paths

TODO: Are these the only cases?  Can we replace this general utility with a
simpler one which only splits preceding dots?
"""
function bump_split(stream::ParseStream, split_spec...)
    tok = stream.lookahead[stream.lookahead_index]
    stream.lookahead_index += 1
    b = _next_byte(stream)
    for (i, (nbyte, k, f)) in enumerate(split_spec)
        h = SyntaxHead(k, f)
        b = (i == length(split_spec)) ? tok.next_byte : b + nbyte
        push!(stream.tokens, SyntaxToken(h, kind(tok), b))
    end
    stream.peek_count = 0
    # Returning position(stream) like the other bump* methods would be
    # ambiguous here; return nothing instead.
    nothing
end

function _reset_node_head(x, k, f)
    h = SyntaxHead(isnothing(k) ? kind(x)  : k,
                   isnothing(f) ? flags(x) : f)
end

"""
Reset kind or flags of an existing node in the output stream

This is a hack, but in some limited occasions the trailing syntax may change
the kind or flags of a token in a way which would require unbounded lookahead
in a recursive descent parser. Modifying the output with reset_node! is useful
in those cases.
"""
function reset_node!(stream::ParseStream, pos::ParseStreamPosition;
                     kind=nothing, flags=nothing)
    if token_is_last(stream, pos)
        t = stream.tokens[pos.token_index]
        stream.tokens[pos.token_index] = SyntaxToken(_reset_node_head(t, kind, flags),
                                                     t.orig_kind, t.next_byte)
    else
        r = stream.ranges[pos.range_index]
        stream.ranges[pos.range_index] = TaggedRange(_reset_node_head(r, kind, flags),
                                                     r.first_token, r.last_token)
    end
end

"""
Move `numbytes` from the range at output position `pos+1` to the output
position `pos`. If the donor range becomes empty, mark it dead with
K"TOMBSTONE" and return `true`, otherwise return `false`.

Hack alert! This is used only for managing the complicated rules related to
dedenting triple quoted strings.
"""
function steal_token_bytes!(stream::ParseStream, pos::ParseStreamPosition, numbytes)
    i = pos.token_index
    t1 = stream.tokens[i]
    t2 = stream.tokens[i+1]

    t1_next_byte = t1.next_byte + numbytes
    stream.tokens[i] = SyntaxToken(t1.head, t1.orig_kind, t1_next_byte)

    t2_is_empty = t1_next_byte == t2.next_byte
    head2 = t2_is_empty ? SyntaxHead(K"TOMBSTONE", EMPTY_FLAGS) : t2.head
    stream.tokens[i+1] = SyntaxToken(head2, t2.orig_kind, t2.next_byte)
    return t2_is_empty
end

function Base.position(stream::ParseStream)
    ParseStreamPosition(lastindex(stream.tokens), lastindex(stream.ranges))
end

"""
    emit(stream, mark, kind, flags = EMPTY_FLAGS; error=nothing)

Emit a new text span into the output which covers source bytes from `mark` to
the end of the most recent token which was `bump()`'ed. The starting `mark`
should be a previous return value of `position()`.
"""
function emit(stream::ParseStream, mark::ParseStreamPosition, kind::Kind,
              flags::RawFlags = EMPTY_FLAGS; error=nothing)
    first_token = mark.token_index + 1
    range = TaggedRange(SyntaxHead(kind, flags), first_token, length(stream.tokens))
    if !isnothing(error)
        # The first child must be a leaf, otherwise ranges would be improperly
        # nested.
        fbyte = token_first_byte(stream, first_token)
        lbyte = token_last_byte(stream, lastindex(stream.tokens))
        _emit_diagnostic(stream, fbyte, lbyte, error=error)
    end
    push!(stream.ranges, range)
    return position(stream)
end

function _emit_diagnostic(stream::ParseStream, fbyte, lbyte; kws...)
    push!(stream.diagnostics, Diagnostic(fbyte, lbyte; kws...))
    return nothing
end

"""
Emit a diagnostic at the position of the next token

If `whitespace` is true, the diagnostic is positioned on the whitespace before
the next token. Otherwise it's positioned at the next token as returned by `peek()`.

TODO: Rename? This doesn't emit normal tokens into the output event list!
"""
function emit_diagnostic(stream::ParseStream; whitespace=false, kws...)
    i = _lookahead_index(stream, 1, true)
    begin_tok_i = i
    end_tok_i = i
    if whitespace
        # It's the whitespace which is the error. Find the range of the current
        # whitespace.
        begin_tok_i = stream.lookahead_index
        end_tok_i = is_whitespace(stream.lookahead[i]) ?
                    i : max(stream.lookahead_index, i - 1)
    end
    fbyte = lookahead_token_first_byte(stream, begin_tok_i)
    lbyte = lookahead_token_last_byte(stream, end_tok_i)
    _emit_diagnostic(stream, fbyte, lbyte; kws...)
    return nothing
end

function emit_diagnostic(stream::ParseStream, mark::ParseStreamPosition; kws...)
    _emit_diagnostic(stream, token_first_byte(stream, mark.token_index),
                     _next_byte(stream) - 1; kws...)
end

function emit_diagnostic(stream::ParseStream, r::NTuple{2,ParseStreamPosition}; kws...)
    emit_diagnostic(stream, first(r), last(r); kws...)
end

function emit_diagnostic(stream::ParseStream, mark::ParseStreamPosition,
                         end_mark::ParseStreamPosition; kws...)
    fbyte = token_first_byte(stream, mark.token_index)
    lbyte = token_first_byte(stream, end_mark.token_index) - 1
    _emit_diagnostic(stream, fbyte, lbyte; kws...)
end

#-------------------------------------------------------------------------------
# Tree construction from the list of text ranges held by ParseStream

# API for extracting results from ParseStream

"""
    build_tree(::Type{NodeType}, stream::ParseStream;
               wrap_toplevel_as_kind=nothing, kws...)

Construct a tree with `NodeType` nodes from a ParseStream using depth-first
traversal. `NodeType` must have the constructors

    NodeType(head::SyntaxHead, span::Integer)
    NodeType(head::SyntaxHead, span::Integer, children::Vector{NodeType})

A single node which covers the input is expected, but if the ParseStream has
multiple nodes at the top level, `wrap_toplevel_as_kind` may be used to wrap
them in a single node.

The tree here is constructed depth-first, but it would also be possible to use
a bottom-up tree builder interface similar to rust-analyzer. (In that case we'd
traverse the list of ranges backward rather than forward.)
"""
function build_tree(::Type{NodeType}, stream::ParseStream;
                    wrap_toplevel_as_kind=nothing, kws...) where NodeType
    stack = Vector{NamedTuple{(:first_token,:node),Tuple{Int,NodeType}}}()

    tokens = stream.tokens
    ranges = stream.ranges
    i = firstindex(tokens)
    j = firstindex(ranges)
    while true
        last_token = j <= lastindex(ranges) ?
                     ranges[j].last_token : lastindex(tokens)
        # Process tokens to nodes for all tokens used by the next internal node
        while i <= last_token
            t = tokens[i]
            if kind(t) == K"TOMBSTONE"
                i += 1
                continue # Ignore removed tokens
            end
            node = NodeType(head(t), token_span(stream, i))
            push!(stack, (first_token=i, node=node))
            i += 1
        end
        if j > lastindex(ranges)
            break
        end
        # Process internal nodes which end at the current position
        while j <= lastindex(ranges)
            r = ranges[j]
            if r.last_token != last_token
                break
            end
            if kind(r) == K"TOMBSTONE"
                j += 1
                continue
            end
            # Collect children from the stack for this internal node
            k = length(stack) + 1
            while k > 1 && r.first_token <= stack[k-1].first_token
                k -= 1
            end
            children = (stack[n].node for n = k:length(stack))
            node = NodeType(head(r), children)
            resize!(stack, k-1)
            push!(stack, (first_token=r.first_token, node=node))
            j += 1
        end
    end
    if length(stack) == 1
        return only(stack).node
    elseif !isnothing(wrap_toplevel_as_kind)
        # Mostly for debugging
        children = (x.node for x in stack)
        return NodeType(SyntaxHead(wrap_toplevel_as_kind, EMPTY_FLAGS), children)
    else
        error("Found multiple nodes at top level")
    end
end

"""
    sourcetext(stream::ParseStream; steal_textbuf=true)

Return the source text being parsed by this `ParseStream` as a UTF-8 encoded
string.

If `steal_textbuf==true`, this is permitted to steal the content of the
stream's text buffer. Note that this leaves the `ParseStream` in an invalid
state for further parsing.
"""
function sourcetext(stream::ParseStream; steal_textbuf=false)
    if stream.text_root isa AbstractString && codeunit(stream.text_root) == UInt8
        return stream.text_root
    elseif steal_textbuf
        return String(stream.textbuf)
    else
        # Safe default for other cases is to copy the buffer. Technically this
        # could possibly be avoided in some situations, but might have side
        # effects such as mutating stream.text_root or stealing the storage of
        # stream.textbuf
        return String(copy(stream.textbuf))
    end
end

"""
    textbuf(stream)

Return the `Vector{UInt8}` text buffer being parsed by this `ParseStream`.
"""
textbuf(stream) = stream.textbuf

first_byte(stream::ParseStream) = first(stream.tokens).next_byte # Use sentinel token
last_byte(stream::ParseStream) = _next_byte(stream)-1
any_error(stream::ParseStream) = any_error(stream.diagnostics)

function Base.empty!(stream::ParseStream)
    t = last(stream.tokens)
    empty!(stream.tokens)
    # Restore sentinel token
    push!(stream.tokens, SyntaxToken(SyntaxHead(K"TOMBSTONE",EMPTY_FLAGS),
                                     K"TOMBSTONE", t.next_byte))
    empty!(stream.ranges)
end


text:
module LMDB

    @isdefined(Docile) && eval(:(@document))

    import Base: open, close, getindex, setindex!, put!, reset,
                 isopen, count, delete!, keys, get, show, convert, show
    import Base.Iterators: drop

    depsfile = joinpath(dirname(@__FILE__), "..", "deps", "deps.jl")
    if isfile(depsfile)
        include(depsfile)
    else
        error("LMDB not properly installed. Please run Pkg.build(\"LMDB\")")
    end

    export Environment, create, open, close, sync, set!, unset!, getindex, setindex!, path, info, show,
           Transaction, start, abort, commit, reset, renew, environment,
           DBI, drop, delete!, keys, get, put!,
           Cursor, count, transaction, database,
           isflagset, isopen,
           LMDBError, CursorOps

    include("common.jl")
    include("env.jl")
    include("txn.jl")
    include("dbi.jl")
    include("cur.jl")
end

ext: jl


text:
# one parameter predicates

"""Returns nonzero iff the midpoint and radius of x are both finite floating-point numbers, i.e. not infinities or NaN."""
function isfinite{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_is_finite), Int, (Ptr{T},), &x)
end

"""isnan or isinf"""
function notfinite{T<:ArbFloat}(x::T)
    return 0 == ccall(@libarb(arb_is_finite), Int, (Ptr{ArbFloat{P}},), &x)
end

function isnan{T<:ArbFloat}(x::T)
    P = precision(T)
    return isnan(convert(ArfFloat{P},x))
end
function notnan{T<:ArbFloat}(x::T)
    P = precision(T)
    return notnan(convert(ArfFloat{P},x))
end

function isinf{T<:ArbFloat}(x::T)
    P = precision(T)
    return isinf(convert(ArfFloat{P},x))
end
function notinf{T<:ArbFloat}(x::T)
    P = precision(T)
    return notinf(convert(ArfFloat{P},x))
end

function isposinf{T<:ArbFloat}(x::T)
    P = precision(T)
    return isposinf(convert(ArfFloat{P},x))
end
function notposinf{T<:ArbFloat}(x::T)
    P = precision(T)
    return notposinf(convert(ArfFloat{P},x))
end

function isneginf{T<:ArbFloat}(x::T)
    P = precision(T)
    return isneginf(convert(ArfFloat{P},x))
end
function notneginf{T<:ArbFloat}(x::T)
    P = precision(T)
    return notneginf(convert(ArfFloat{P},x))
end

"""midpoint(x) and radius(x) are zero"""
function iszero{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_is_zero), Int, (Ptr{T},), &x)
end
"""true iff midpoint(x) or radius(x) are not zero"""
function notzero{T<:ArbFloat}(x::T)
    return 0 == ccall(@libarb(arb_is_zero), Int, (Ptr{T},), &x)
end
notzero{T<:Real}(x::T) = (x != zero(T))

"""true iff zero is not within [upperbound(x), lowerbound(x)]"""
function nonzero{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_is_nonzero), Int, (Ptr{T},), &x)
end
nonzero{T<:Real}(x::T) = (x != zero(T))

"""true iff midpoint(x) is one and radius(x) is zero"""
function isone{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_is_one), Int, (Ptr{T},), &x)
end
isone{T<:Real}(x::T) = (x == one(T))

"""true iff midpoint(x) is not one or midpoint(x) is one and radius(x) is nonzero"""
function notone{T<:ArbFloat}(x::T)
    return 0 == ccall(@libarb(arb_is_one), Int, (Ptr{T},), &x)
end
notone{T<:Real}(x::T) = (x != one(T))

"""true iff radius is zero"""
function isexact{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_is_exact), Int, (Ptr{T},), &x)
end
"""true iff radius is nonzero"""
function notexact{T<:ArbFloat}(x::T)
    return 0 == ccall(@libarb(arb_is_exact), Int, (Ptr{T},), &x)
end

isexact{T<:Integer}(x::T) = true
notexact{T<:Integer}(x::T) = false

"""true iff midpoint(x) is an integer and radius(x) is zero"""
function isinteger{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_is_int), Int, (Ptr{T},), &x)
end
"""true iff midpoint(x) is not an integer or radius(x) is nonzero"""
function notinteger{T<:ArbFloat}(x::T)
    return 0 == ccall(@libarb(arb_is_int), Int, (Ptr{T},), &x)
end

isinteger{T<:Integer}(x::T) = true
notinteger{T<:Integer}(x::T) = false

"""true iff lowerbound(x) is positive"""
function ispositive{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_is_positive), Int, (Ptr{T},), &x)
end

"""true iff upperbound(x) is negative"""
function isnegative{T<:ArbFloat}(x::T)
    return  0 != ccall(@libarb(arb_is_negative), Int, (Ptr{T},), &x)
end

"""true iff upperbound(x) is zero or negative"""
function notpositive{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_is_nonpositive), Int, (Ptr{T},), &x)
end
excludesPositive{P}(x::ArbFloat{P}) = notpositive(x)

"""true iff lowerbound(x) is zero or positive"""
function notnegative{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_is_nonnegative), Int, (Ptr{T},), &x)
end
excludesNegative{P}(x::ArbFloat{P}) = notnegative(x)

# two parameter predicates

"""true iff midpoint(x)==midpoint(y) and radius(x)==radius(y)"""
function areequal{T<:ArbFloat}(x::T, y::T)
    return 0 != ccall(@libarb(arb_equal), Int, (Ptr{T}, Ptr{T}), &x, &y)
end

"""true iff midpoint(x)!=midpoint(y) or radius(x)!=radius(y)"""
function notequal{T<:ArbFloat}(x::T, y::T)
    return 0 == ccall(@libarb(arb_equal), Int, (Ptr{T}, Ptr{T}), &x, &y)
end

"""true iff x and y have a common point"""
function overlap{T<:ArbFloat}(x::T, y::T)
    return 0 != ccall(@libarb(arb_overlaps), Int, (Ptr{T}, Ptr{T}), &x, &y)
end

"""true iff x and y have no common point"""
function donotoverlap{T<:ArbFloat}(x::T, y::T)
    return 0 == ccall(@libarb(arb_overlaps), Int, (Ptr{T}, Ptr{T}), &x, &y)
end

"""true iff x spans (covers) all of y"""
function contains{T<:ArbFloat}(x::T, y::T)
    return 0 != ccall(@libarb(arb_contains), Int, (Ptr{T}, Ptr{T}), &x, &y)
end

"""true iff y spans (covers) all of x"""
function iscontainedby{T<:ArbFloat}(x::T, y::T)
    return 0 != ccall(@libarb(arb_contains), Int, (Ptr{T}, Ptr{T}), &y, &x)
end

"""true iff x does not span (cover) all of y"""
function doesnotcontain{T<:ArbFloat}(x::T, y::T)
    return 0 != ccall(@libarb(arb_contains), Int, (Ptr{T}, Ptr{T}), &x, &y)
end

"""true iff y does not span (cover) all of x"""
function isnotcontainedby{T<:ArbFloat}(x::T, y::T)
    return 0 == ccall(@libarb(arb_contains), Int, (Ptr{T}, Ptr{T}), &y, &x)
end

"""true if it is quite likely that the arguments indicate the same value"""
function approxeq{T<:ArbFloat}(x::T, y::T)
    z =
        if contains(x,y)
           true
        elseif contains(y,x)
           true
        else
           x = tidy(x)
           y = tidy(y)
           contains(x,y) || contains(y,x)
        end
    return z
end

(≊){T<:ArbFloat}(x::T, y::T) = approxeq(x,y)
for F in (:overlap, :donotoverlap, :contains, :doesnotcontain, :iscontainedby, :isnotcontainedby, :approxeq)
  @eval ($F){P,Q}(x::ArbFloat{P}, y::ArbFloat{Q}) = ($F)(promote(x,y)...)
end

"""true iff x contains an integer"""
function includesAnInteger{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_contains_int), Int, (Ptr{T},), &x)
end

"""true iff x does not contain an integer"""
function excludesIntegers{T<:ArbFloat}(x::T)
    return 0 == ccall(@libarb(arb_contains_int), Int, (Ptr{T},), &x)
end

"""true iff x contains zero"""
function includesZero{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_contains_int), Int, (Ptr{T},), &x)
end

"""true iff x does not contain zero"""
function excludesZero{T<:ArbFloat}(x::T)
    return 0 == ccall(@libarb(arb_contains_int), Int, (Ptr{T},), &x)
end

"""true iff x contains a positive value"""
function includesPositive{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_contains_positive), Int, (Ptr{T},), &x)
end

"""true iff x contains a negative value"""
function includesNegative{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_contains_negative), Int, (Ptr{T},), &x)
end

"""true iff x contains a nonpositive value"""
function includesNonpositive{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_contains_nonpositive), Int, (Ptr{T},), &x)
end

"""true iff x contains a nonnegative value"""
function includesNonnegative{T<:ArbFloat}(x::T)
    return 0 != ccall(@libarb(arb_contains_nonnegative), Int, (Ptr{ArbFloat{T}},), &x)
end


text:
using Plots

# example code taken from
# https://docs.juliaplots.org/latest/tutorial/#Changing-the-Plotting-Series-1

x = 1:10
y = rand(10)

gr() # We will continue onward using the GR backend
p = plot(x, y, seriestype = :scatter, title = "My Scatter Plot")
savefig(p, "tutorial_plot.png")

# animated plot. Code taken from:
#

p = plot([sin, cos], zeros(0), leg = false)
anim = Animation()
for x = range(0, stop = 10π, length = 100)
    push!(p, x, Float64[sin(x), cos(x)])
    frame(anim)
end
gif(anim, "anim_sine.gif", fps=15)


text:
immutable RandIntSampler  # for generating Int samples in [0, K-1]
    a::Int
    Ku::Uint
    U::Uint

    RandIntSampler(K::Int) = (Ku = uint(K); new(1, Ku, div(typemax(Uint), Ku) * Ku))
    RandIntSampler(a::Int, b::Int) = (Ku = uint(b-a+1); new(a, Ku, div(typemax(Uint), Ku) * Ku))
end

function rand(s::RandIntSampler)
    x = rand(Uint)
    while x >= s.U
        x = rand(Uint)
    end
    s.a + int(rem(x, s.Ku))
end

randi(K::Int) = rand(RandIntSampler(K))
randi(a::Int, b::Int) = rand(RandIntSampler(a, b))


text:
using OdinSon
import PyPlot: subplots, matplotlib
using PyCall
@pyimport matplotlib as mpl
@pyimport copy as pycopy

# Utilities
# A simple function from seaborn that displays color palettes
function palplot(pal, psize=1)
    # set the grids to be like the seaborn default: "darkgrid" which gives nice white gridlines
    old_style = pycopy.copy(matplotlib["rcParams"])
    style_kw = Dict(
    "axes.facecolor" => "#EAEAF2",
    "axes.edgecolor" => NC"white",
    "axes.linewidth" => 0,
    "grid.color" => NC"white",
    "axes.grid" => true,
    # hide the ticks
    "xtick.major.size" => 0,
    "ytick.major.size" => 0,
    "xtick.minor.size" => 0,
    "ytick.minor.size" => 0
    )
    matplotlib["rcParams"][:update](style_kw)

    n = length(pal)
    (f, ax) = subplots(1, 1, figsize=(n*psize, psize))
    ax[:imshow](
        reshape(1:n, 1, n),
        cmap=mpl.colors[:ListedColormap](pal),
        interpolation="nearest",
        aspect="auto"
    )
    ax[:set_xticks]((1:n) - 0.5)
    ax[:set_yticks]([-0.5, 0.5])
    ax[:set_xticklabels]([])
    ax[:set_yticklabels]([])

    # restore the original plot settings
    matplotlib["rcParams"][:update](old_style)

    return nothing
end

palplot(OdinSon.SEABORN_PALETTES[:deep])
plot([1, 2, 3])

max_stars_repo_name: gabrielgellner/OdinSon

max_issues_repo_name: gabrielgellner/OdinSon

max_forks_repo_name: gabrielgellner/OdinSon


text:
module Nodes

import ..AbstractModel, ..train!, ..predict

export AbstractNode,
    AbstractClassificationNode,
    AbstractRegressionNode,
    DictNode,
    AccNode,
    RegressionNode,
    GeneralizedRegressionNode

# TODO: There is nothing preventing different sized inputs
abstract type AbstractNode <: AbstractModel end
abstract type AbstractClassificationNode <: AbstractNode end
abstract type AbstractRegressionNode <: AbstractNode end

# Generic methods

function train!(node::N, X::T) where {N <: AbstractClassificationNode,T <: AbstractMatrix{Bool}}
    for x in eachrow(X)
        train!(node, x)
    end
end

# TODO: This is implicitly requiring that a AbstractClassificationNode has a `memory` field
#       and a `default` field. It might be better to enforce this through traits.
function predict(node::N, X::T; b::Int=0) where {N <: AbstractClassificationNode,T <: AbstractVector{Bool}}
    return get(node.memory, X, node.default) > b
end

function predict(node::N, X::T; kargs...) where {N <: AbstractNode,T <: AbstractMatrix{Bool}}
    return [predict(node, x; kargs...) for x in eachrow(X)]
end

function train!(node::N, X::T, y::AbstractVector{Float64}) where {N <: AbstractRegressionNode,T <: AbstractMatrix{Bool}}
    for (x, target) in Iterators.zip(eachrow(X), y)
        train!(node, x, target)
    end
end

function predict(node::N, X::T) where {N <: AbstractRegressionNode,T <: AbstractVector{Bool}}
    return get(node.memory, X, node.default)
end

# If both BitVectors and BoolVectors hash to the same value when they have the same
# content, does it matter which type I choose as key for the underlying dictionary?
# I should check if both DictNode{BitVector} and DictNode{Vector{Bool}} accept any
# instance of AbstractVector{Bool}. If that's the case, I should get rid of the
# type parameter and enforce the use of one of the types. Does it matter which one
# I choose? Is there an impact in performance and/or memory usage?
struct DictNode{K <: AbstractVector{Bool}} <: AbstractClassificationNode
    default::Int8
    memory::Dict{K,Int8}
end

DictNode{T}(;default=zero(Int8)) where {T <: AbstractVector{Bool}} = DictNode{T}(default, Dict{T,Int8}())

DictNode(;default=zero(Int8)) = DictNode{Vector{Bool}}(;default)

function train!(node::DictNode, X::T) where {T <: AbstractVector{Bool}}
    node.memory[X] = 1

    nothing
end

################################################################################
struct AccNode <: AbstractClassificationNode
    default::Int64
    memory::Dict{Vector{Bool},Int64}
end

AccNode(;default=zero(Int64)) = AccNode(default, Dict{Vector{Bool},Int64}())

function train!(node::AccNode, X::T) where {T <: AbstractVector{Bool}}
    node.memory[X] = get(node.memory, X, node.default) + 1

    nothing
end

################################################################################
struct RegressionNode <: AbstractRegressionNode
    γ::Float64
    default::Tuple{Int,Float64}
    memory::Dict{Vector{Bool},Tuple{Int,Float64}}

    function RegressionNode(γ, default, memory)
        if !(0.0 ≤ γ ≤ 1.0)
            throw(DomainError(γ, "`γ` must lie in the [0, 1] interval"))
        end

        new(γ, default, memory)
    end
end

RegressionNode(;γ=1.0, default=(zero(Int), zero(Float64))) = RegressionNode(γ, default, Dict{Vector{Bool},Tuple{Int,Float64}}())

function train!(node::RegressionNode, X::T, y::Float64) where {T <: AbstractVector{Bool}}
    count, sum = get(node.memory, X, node.default)

    node.memory[X] = (count + 1, node.γ * sum + y)

    nothing
end

################################################################################
# TODO: Enforce α to be greater than zero
struct GeneralizedRegressionNode <: AbstractRegressionNode
    α::Float64
    default::Tuple{Int,Float64}
    memory::Dict{Vector{Bool},Tuple{Int,Float64}}
end

GeneralizedRegressionNode(;α::Float64, default=(zero(Int), zero(Float64))) = GeneralizedRegressionNode(α, default, Dict{Vector{Bool},Tuple{Int,Float64}}())

# TODO: Make stepsize function that takes in a node and returns its appropriate α
function train!(node::GeneralizedRegressionNode, X::T, y::Float64) where {T <: AbstractVector{Bool}}
    count, estimate = get(node.memory, X, node.default)

    node.memory[X] = (count + 1, estimate + node.α * (y - estimate))

    nothing
end

end

max_stars_repo_name: RafaelFK/ramnet

max_issues_repo_name: RafaelFK/ramnet

max_forks_repo_name: RafaelFK/ramnet


text:
function search_frequency(rest_ν, ν)
  min_i = 1
  min_Δ = Inf
  for (i, value) in enumerate(ν)
    current_Δ = abs(value - rest_ν)
    (min_Δ, min_i) = current_Δ < min_Δ ? (current_Δ, i) : (min_Δ, min_i)
  end
  return min_Δ, min_i
end

"""Loops through two vectors A and B, searching for the best matches
for between them.

Matches are only considered if the difference of the values meet
a preliminary threshold, as a fraction of the value of A.

This is the preferred method of matching the catalog and obs. frequencies,
as it means you only run the loop once.

Returns a list of index pairs of A and B.
"""
function intersect_frequencies(A::Vector{T}, B::Vector{S}; thres=1f-4) where {T<:Real,S<:Real}
  matches = []
  # preallocate up to the length of the rest frequencies
  sizehint!(matches, length(A))
  for (i, rest_value) in enumerate(A)
    to_match = rest_value * thres
    best_diff = Inf
    best_match = nothing
    for (j, obs_value) in enumerate(B)
      diff = abs(rest_value - obs_value)
      if diff <= to_match && diff < best_diff
        best_diff = diff
        best_match = [i, j]
      end
      # if the diff increases from the best diff, we've passed it
      if diff > best_diff
        push!(matches, best_match)
        break
      end
    end
  end
  return matches
end

#function extract_windows(rest_ν, obs::Observation, vlsr; thres=1f-4,)
#  matches = intersect_frequencies(rest_ν, obs.frequency; thres=thres)
#end


text:
# Set up
import TrajectoryOptimization._solve

function pendulum_benchmarks()
    group = BenchmarkGroup()
    stat_group = BenchmarkGroup()

    stats = Dict("iterations"=>0, "setup_time"=>0.0, "c_max"=>Float64, "major iterations"=>0.0, "cost"=>Float64[])
    stats = BenchmarkGroup(["stats"],stats)

    # Params
    disable_logging(Logging.Warn)
    N = 501
    integration = :rk3
    model = Dynamics.pendulum[1]
    n,m = model.n, model.m

    # Objective
    x0 = [0; 0.]
    xf = [pi; 0] # (ie, swing up)
    Q = 1e-3*Diagonal(I,n)
    Qf = 100.0*Diagonal(I,n)
    R = 1e-2*Diagonal(I,m)
    tf = 5.
    obj_uncon = LQRObjective(Q, R, Qf, tf, x0, xf)

    u_min = [-3]
    u_max = [3]
    x_min = [-5;-5]
    x_max = [10; 10]
    obj_con = ConstrainedObjective(obj_uncon, u_min=u_min, u_max=u_max, x_min=x_min, x_max=x_max) # constrained objective

    # Unconstrained
    solver_uncon = Solver(model, obj_uncon, N=N, integration=integration)
    U0 = ones(m,N)

    stat_group["unconstrained"] = deepcopy(stats)
    group["unconstrained"] = @benchmarkable _solve($solver_uncon, $U0, bmark_stats=$stat_group["unconstrained"])

    # Constrained
    solver_con = Solver(model, obj_con, N=N, integration=integration)
    stat_group["constrained"] = deepcopy(stats)
    group["constrained"] = @benchmarkable _solve($solver_con, $U0, bmark_stats=$stat_group["constrained"])

    return group, stat_group
end


text:
module SymbolMaps
export SymbolMap, submap
export integral!, derivative!

import Base./
using OneVision

const symbol_path_cache = Dict{Tuple{Symbol, Symbol}, Symbol}()
function symbol_path(s1::Symbol, s2::Symbol)::Symbol
    @get!(symbol_path_cache, (s1,s2), Symbol(string(s1, "/", s2)))
end

"""
Append the symbol `s2` to symbol `s1`.
"""
@inline function /(s1::Symbol, s2::Symbol)
    symbol_path(s1, s2)
end

@kwdef struct SymbolMap
    base_path::Symbol = :/
    data::Dict{Symbol,Any} = Dict{Symbol,Any}()
end

Base.getindex(m::SymbolMap, path::Symbol) = m.data[m.base_path / path]
Base.setindex!(m::SymbolMap, v, path::Symbol) =
    m.data[m.base_path / path] = v
Base.get!(m::SymbolMap, path::Symbol, default) =
    get!(m.data, m.base_path / path, default)
Base.get(m::SymbolMap, path::Symbol, default) =
    get(m.data, m.base_path / path, default)

"""
Creat a restricted view of the orginal SymbolMap.
"""
function submap(m::SymbolMap, path::Symbol)::SymbolMap
    SymbolMap(m.base_path / path, m.data)
end

function integral!(m::SymbolMap, path::Symbol, t::T, e::E)::E where {T,E}
    r = get(m, path, nothing)
    if r === nothing
        (m[path] = (t, zero(E)))[2]
    else
        (t0, v0) = r::Tuple{T,E}
        @assert(t > t0, "`integral!` with the path `$path` shouldn't be called multiple
                times in a single time step. (t = $t)")
        Δt = t - t0
        (m[path] = (t, v0 + e * Δt))[2]
    end
end

function derivative!(m::SymbolMap, path::Symbol, t::T, e::E)::E where {T,E}
    r = get(m, path, nothing)
    if r === nothing
        (m[path] = (t, zero(E)))[2]
    else
        (t0, v0) = r::Tuple{T,E}
        @assert(t > t0, "`derivative!` with the path `$path` shouldn't be called multiple
                times in a single time step. (t = $t)")
        Δt = t - t0
        (m[path] = (t, v0 + e / Δt))[2]
    end
end

end # module SymbolMaps


text:
load("debug.jl")

module TestInstrument
using Base, Debug
import Debug.trap

trap(line, file) = println("trap: line = $line, file = $(repr(file))")

code = quote
    for i=1:3
        println(i)
    end
end

icode = instrument(code)
println(icode)

eval(icode)

end


text:
"""

A fast language can be beat
by a slow one `if` the code in the slow language solves the problem
more efficiently
 (if slower is uses a  smarter, better Algorithm )

takeaway: Implementation:
1. Language
2. Solution Strategy

You can also get the opposite

In a slow language , the converse can also be true

A poor algorithm might run faster than a good algorithm
(due to language limitations): #unlike Julia (doesn't have overhead, has optimization)
Tim Holy: the actual `impractice performance` you get from a language that doesn't do the Optimziations(julia does ) depends upon
what's Built-in for you
basically relies on people having written  `the things` that your particular Implementation requires
in a way that allows it to run quickly
invariably, you'll find certain concepts are efficient
other construcs arent' efficient
[some examples would change your impression on how the best way to solve a problem is]

Certain constructs are implemented efficiently
(Certain other constructs are not )

"""

"""Big-O Notation @22:34

you may notice there's a little work outside the Innermost loop
Point of Big-O
freedom to ignore terms that are less imprtant
me: I have to digress, it's a measure of complexity , as implied by demonstrating an inner-loop i.e. raising the already complex complexity
-Tim: "you might object", say  you're ignoring certain things  !
"""

for i = i:m
    s=0              # happens `m` times  - little work before time
    for j = 1:n
        s += M[i,j] * v[j] # happens `m*n` times

    end
    out[i] = s          # happens `m` times  # little work after time
end
#=more accurately, the running time is `a*m + b*m*n`, where a &b are constants # the actual running time
(since inner-loop runs m*n times )

Takeaway: Pay attention to the things that grow most quickly
so O(mn)
this algorithm is big-O -            a lisence to ignore small ones, yet focus on big ones that matter
=#

"""Key Rules about memory @41:38

1. Computers have multiple layers of caches
2. the fastest caches have only ~1/10^6 of storage of main memory
3. Main memory gets transferred to cache in small chuncks of adjacent memory (cache line)
4. Performace is Better If you Exploit what you have in cache before flushing it & swapping in new Memory
5. CPUs try to Predict what Chunck will be Needed next & start fetching it before

Tip: `LoopVectorization` will Reorder Your Loops & Make Other changes that help not Slow Code become "fast"
"""

"""Know the Costs & Benefits of Threading

A `Thread.@threads` has an overhead of a few microseconds.
equivalnet to 1000s of computations
(Reverse threding for sizable jobs)

- In cases where threads can work independently. it's sometimes possible to get an `~n` fold speedup from `n` threads

Communicating between threads can be a source of bugs &/or slowdowns

sum values of vector v
threaded loop (without it would look the same as normal loops) - enable us to Distribute the work
"""

function threadedsum(v)
    s = 0
    Threads.@threads for i in eachindex(v)
        s = s + v[i] #readout old value, then increments with next item on the list, store result back in s again
    end
    return s
end

#Define v
@time v = rand(1:5, 10^4) #0.000105 seconds (2allocations:78.203KiB)

@time threadedsum(v) # 0.092380 seconds (93.25 k allocations: 5.186 MiB, 99.55% compilation time)
# 30144
@time sum(v) # 0.017116 seconds (262 allocations: 13.641 KiB, 96.04% compilation time)

"""Race-condition

one of common things to happen (me:is it because not locking the common working memory? ) - possible
multiple working threads

3 working fast
1 of them gets interrupted
it gets that core, to do sth else
then it comes back,  picks off execution, where it left off

read out a v. old value of s
we don't know its' refreshed
then overwrite the value you had before
this causes it to drop many terms of v

sum (subset (value of v) )

Bugs arise from one thread being overwritted by another thread

1 way :
prevent 1 thread from accessing s

caled blocks new texes, atomic operation (happening in time )
in this case

problem blocking (& its generalizations)
while one
one thread holding lock, other (simply) has to wait - until the first one is done
(that delays the thread )
Unfavorable circumstances that take way way longer than a simple implentation
Solution:
by giving each threads to Maintin their counter

"""
function threadedsum2(v)
    spartial = zeros(Int, Threads.nthreads()) # s = 0 #allocates a n(counter) = to n(threads)
    Threads.@threads for i in eachindex(v)
        #s = s + v[i] #readout old value, then increments with next item on the list, store result back in s again
        spartial[Threads.threadid()] += v[i]  # each counter implements just its own counter
    end
    return sum(spartial) #return sum of 4 values Accumulated by each thread
end

@time threadedsum2(v) # 0.000087 seconds (9allocations:736bytes)

sum(v)

"""Other opportunities in parallelism

1. GPU Computing: julia can generate native code for GPUs (see JuliaGPU)
2. Distributed computing clusters
- each server is working on the portion of the same problem

cluseter computing is supported by julia support library (& other packages in julia ecosystem)

-Caution: in slow languages, sometimes people reach almost unthinkingly for parallelism
So if you're coming from a slow language, you may essentially reach parallelism almost inflexible
You get most out of it optimizing single mode
You'll iron out any performance gotchas (wasts lots of time ) -regardless if you parallize it
-Julia's advantage , you don't need parallelism to get the speed you need

Then, if you have done all that , really taken a serious look at your code
Good algorithm,
Implemented it well, using Idiomatic Julia ( & if it's still not passing up)
Then  that's the time to reach for parallelism
It's a well justified choice (in that circumstance )
But think it's worth emphasizing how important it is to

1.First, try to optimize simpler implementation -that's all you need- for many practical problems
2.When you Parallelize it, you'll get a Better Result - for having done so

good notes:

it's important to use julia well, because you can handicap your code (tell me about it)
and there's consequences of your performance quite severe if you do so

the goodside: there aren't many things you have to know in order to write good idiomatic julia code
you can then use julia pragmatic experience -testing differnet thing out-to quickly develop intuition about
what makes a good algorithm
it's a more reliable ally to your inituition
it really helps you grow as a programmer

Next steps :

1. Algorithms & data structures: Hash tables, Heaps, Priority Queues, et al.
2. extending knowledge of idiomatic Julia: read package code & Julia's `Base` Module
3. learning more about threading & High-performance computing

This course is a taste of lots of things that Prof. Tim Holy found useful
There's a lot out there - many fish in the sea
Tastes offered is just a basis
Exploration is a v. worthwhile experience
Active maintainer: continously spending time  as an
Odds are: v. good! you can get accustumed tuturing from more experienced julia development

max_stars_repo_path: Tutorial/Tim Holy/Algorithms.jl

max_stars_repo_name: adamwillisMastery/DeepLearner

max_issues_repo_path: Tutorial/Tim Holy/Algorithms.jl

max_issues_repo_name: adamwillisMastery/DeepLearner

max_forks_repo_path: Tutorial/Tim Holy/Algorithms.jl

max_forks_repo_name: adamwillisXanax/DeepLearner


text:
for (op, i) in ((:two,:2), (:three,:3), (:four, :4))
  @eval begin
    function ($op)(::Type{ArbFloat{P}}) where {P}
        z = initializer(ArbFloat{P})
        ccall(@libarb(arb_set_si), Cvoid, (Ref{ArbFloat{P}}, Int), z, $i)
        return z
    end
    ($op)(::Type{ArbFloat}) = ($op)(ArbFloat{precision(ArbFloat)})
  end
end

weakcopy(x::ArbFloat{P}) where {P} = WeakRef(x)

for fn in (:copy, :deepcopy)
  @eval begin
    function ($fn)(x::ArbFloat{P}) where {P}
        z = initializer(ArbFloat{P})
        ccall(@libarb(arb_set), Cvoid, (Ref{ArbFloat{P}}, Ref{ArbFloat{P}}), z, x)
        return z
    end
  end
end

function copyradius(target::T, source::T) where {T <: ArbFloat}
    z = deepcopy(target)
    z.radius_exponentOf2 = source.radius_exponentOf2
    z.radius_significand = source.radius_significand
    return z
end

function copymidpoint(target::T, source::T) where {T <: ArbFloat}
    z = deepcopy(target)
    z.exponentOf2  = source.exponentOf2
    z.nwords_sign  = source.nwords_sign
    z.significand1 = source.significand1
    z.significand2 = source.significand2
    return z
end

function bounds(lower::T, upper::T) where {T <: ArbFloat}
    lowerlo, lowerhi = bounds(lower)
    upperlo, upperhi = bounds(upper)
    lo = lowerlo <= upperlo ? lowerlo : upperlo
    hi = lowerhi >= upperhi ? lowerhi : upperhi
    # rad = (hi - lo) * 0.5
    mid = hi*0.5 + lo*0.5
    rad = hi - mid
    r = Float32(rad)
    dr = 0.5 * eps(r)
    z = midpoint_radius(mid, r)
    tstlo, tsthi = bounds(z)
    while (tstlo > lo) || (tsthi < hi)
        z = midpoint_radius(mid, r+dr)
        tstlo, tsthi = bounds(z)
    end
    return z
end

"""
Rounds x to a number of bits equal to the accuracy of x (as indicated by its radius), plus a few guard bits.
The resulting ball is guaranteed to contain x, but is more economical if x has less than full accuracy.
(from arb_trim documentation)
"""
function trim(x::ArbFloat{P}) where {P}
    z = initializer(ArbFloat{P})
    ccall(@libarb(arb_trim), Cvoid, (Ref{ArbFloat{P}}, Ref{ArbFloat{P}}), z, x)
    return z
end

"""
Rounds x to a clean estimate of x as a point value.
"""
function tidy(x::T) where {T <: ArbFloat}
    s = smartarbstring(x)
    return (T)(s)
end

function decompose(x::T) where {T <: ArbFloat}
    # decompose x as num * 2^pow / den
    # num, pow, den = decompose(x)
    P = precision(T)
    bfprec=precision(BigFloat)
    setprecision(BigFloat,P)
    bf = convert(BigFloat, x)
    n,p,d = decompose(bf)
    setprecision(BigFloat,bfprec)
    return n,p,d
end

function modf(x::ArbFloat{P}) where {P}
    isneg = signbit(x)
    y = abs(x)
    ipart = trunc(y)
    fpart = y - ipart
    if isneg
        ipart = -ipart
        fpart = -fpart
    end
    return (fpart, ipart)
end

function fmod(fpart::ArbFloat{P}, ipart::ArbFloat{P}) where {P}
    return ipart + fpart
end

integerpart(x::ArbFloat{P}) where {P} = trunc(x)
fractionalpart(x::ArbFloat{P}) where {P} = x - trunc(x)
decimalpart(x::ArbFloat{P}) where {P} = smartvalue(fractionalpart(x))

function smartmodf(x::ArbFloat{P}) where {P}
    isneg = signbit(x)
    y = abs(x)
    ipart = trunc(y)
    fpart = smartvalue(y - ipart)
    if isneg
        ipart = -ipart
        fpart = -fpart
    end
    return (fpart, ipart)
end


text:
# Command: Switch to Patent Frame
"""
	parent_frame!(session::Session)::Nothing

The Switch to Parent Frame command sets the current browsing context for future commands to the parent of the current browsing context.
"""
function parent_frame!(session::Session)
    @unpack addr, id = session
    response = HTTP.post(
        "$addr/session/$id/frame/parent",
        [("Content-Type" => "application/json; charset=utf-8")],
    )
    @assert response.status == 200
end


text:
@testset "Maximum flow" begin
    #### Graphs for testing
    graphs = [
    # Graph with 8 vertices
    (8,
    [
    (1,2,10),(1,3,5),(1,4,15),(2,3,4),(2,5,9),
    (2,6,15),(3,4,4),(3,6,8),(4,7,16),(5,6,15),
    (5,8,10),(6,7,15),(6,8,10),(7,3,6),(7,8,10)
    ],
    1,8, # source/target
    3,   # answer for default capacity
    28,  # answer for custom capacity
    15,5 # answer for restricted capacity/restriction
    ),

    # Graph with 6 vertices
    (6,
    [
    (1,2,9),(1,3,9),(2,3,10),(2,4,8),(3,4,1),
    (3,5,3),(5,4,8),(4,6,10),(5,6,7)
    ],
    1,6, # source/target
    2,   # answer for default capacity
    12,  # answer for custom capacity
    8,5  # answer for restricted capacity/restriction
    )
    ]

    for (nvertices,flow_edges,s,t,fdefault,fcustom,frestrict,caprestrict) in graphs
        flow_graph = DiGraph(nvertices)
        for g in testdigraphs(flow_graph)
            capacity_matrix = zeros(Int,nvertices,nvertices)
            for e in flow_edges
                u,v,f = e
                add_edge!(g,u,v)
                capacity_matrix[u,v] = f
            end

            # Test DefaultCapacity
            d = @inferred(LightGraphs.DefaultCapacity(g))
            T = eltype(d)
            @test typeof(d) <: AbstractMatrix{T}
            @test d[s,t] == 0
            @test size(d) == (nvertices,nvertices)
            @test typeof(transpose(d)) <: LightGraphs.DefaultCapacity
            @test typeof(ctranspose(d)) <: LightGraphs.DefaultCapacity

            # Test all algorithms - type instability in PushRelabel #553
            for ALGO in [EdmondsKarpAlgorithm, DinicAlgorithm, BoykovKolmogorovAlgorithm, PushRelabelAlgorithm]
                @test maximum_flow(g,s,t,algorithm=ALGO())[1] == fdefault
                @test maximum_flow(g,s,t,capacity_matrix,algorithm=ALGO())[1] == fcustom
                @test maximum_flow(g,s,t,capacity_matrix,algorithm=ALGO(),restriction=caprestrict)[1] == frestrict
            end
        end
    end
end

max_stars_repo_name: AsileBcd/JohnsonCycles

max_issues_repo_name: AsileBcd/JohnsonCycles

max_forks_repo_name: AsileBcd/JohnsonCycles


text:
# Licensed to the Apache Software Foundation (ASF) under one
# or more contributor license agreements.  See the NOTICE file
# distributed with this work for additional information
# regarding copyright ownership.  The ASF licenses this file
# to you under the Apache License, Version 2.0 (the
# "License"); you may not use this file except in compliance
# with the License.  You may obtain a copy of the License at
#
#   http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing,
# software distributed under the License is distributed on an
# "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
# KIND, either express or implied.  See the License for the
# specific language governing permissions and limitations
# under the License.

# An explicitly unrolled LSTM with fixed sequence length.
using MXNet

#--LSTMState
struct LSTMState
  c :: mx.SymbolicNode
  h :: mx.SymbolicNode
end
#--/LSTMState

#--LSTMParam
struct LSTMParam
  i2h_W :: mx.SymbolicNode
  h2h_W :: mx.SymbolicNode
  i2h_b :: mx.SymbolicNode
  h2h_b :: mx.SymbolicNode
end
#--/LSTMParam

#--lstm_cell
function lstm_cell(data::mx.SymbolicNode, prev_state::LSTMState, param::LSTMParam;
                   num_hidden::Int=512, dropout::Real=0, name::Symbol=gensym())

  if dropout > 0
    data = mx.Dropout(data, p=dropout)
  end

  i2h = mx.FullyConnected(data, weight=param.i2h_W, bias=param.i2h_b,
                          num_hidden=4num_hidden, name=Symbol(name, "_i2h"))
  h2h = mx.FullyConnected(prev_state.h, weight=param.h2h_W, bias=param.h2h_b,
                          num_hidden=4num_hidden, name=Symbol(name, "_h2h"))

  gates = mx.SliceChannel(i2h + h2h, num_outputs=4, name=Symbol(name, "_gates"))

  in_gate     = mx.Activation(gates[1], act_type=:sigmoid)
  in_trans    = mx.Activation(gates[2], act_type=:tanh)
  forget_gate = mx.Activation(gates[3], act_type=:sigmoid)
  out_gate    = mx.Activation(gates[4], act_type=:sigmoid)

  next_c = (forget_gate .* prev_state.c) + (in_gate .* in_trans)
  next_h = out_gate .* mx.Activation(next_c, act_type=:tanh)

  return LSTMState(next_c, next_h)
end
#--/lstm_cell

#--LSTM-part1
function LSTM(n_layer::Int, seq_len::Int, dim_hidden::Int, dim_embed::Int, n_class::Int;
              dropout::Real=0, name::Symbol=gensym(), output_states::Bool=false)

  # placeholder nodes for all parameters
  embed_W = mx.Variable(Symbol(name, "_embed_weight"))
  pred_W  = mx.Variable(Symbol(name, "_pred_weight"))
  pred_b  = mx.Variable(Symbol(name, "_pred_bias"))

  layer_param_states = map(1:n_layer) do i
    param = LSTMParam(mx.Variable(Symbol(name, "_l$(i)_i2h_weight")),
                      mx.Variable(Symbol(name, "_l$(i)_h2h_weight")),
                      mx.Variable(Symbol(name, "_l$(i)_i2h_bias")),
                      mx.Variable(Symbol(name, "_l$(i)_h2h_bias")))
    state = LSTMState(mx.Variable(Symbol(name, "_l$(i)_init_c")),
                      mx.Variable(Symbol(name, "_l$(i)_init_h")))
    (param, state)
  end
  #...
  #--/LSTM-part1

  #--LSTM-part2
  # now unroll over time
  outputs = mx.SymbolicNode[]
  for t = 1:seq_len
    data   = mx.Variable(Symbol(name, "_data_$t"))
    label  = mx.Variable(Symbol(name, "_label_$t"))
    hidden = mx.FullyConnected(data, weight=embed_W, num_hidden=dim_embed,
                               no_bias=true, name=Symbol(name, "_embed_$t"))

    # stack LSTM cells
    for i = 1:n_layer
      l_param, l_state = layer_param_states[i]
      dp = i == 1 ? 0 : dropout # don't do dropout for data
      next_state = lstm_cell(hidden, l_state, l_param, num_hidden=dim_hidden, dropout=dp,
                             name=Symbol(name, "_lstm_$t"))
      hidden = next_state.h
      layer_param_states[i] = (l_param, next_state)
    end

    # prediction / decoder
    if dropout > 0
      hidden = mx.Dropout(hidden, p=dropout)
    end
    pred = mx.FullyConnected(hidden, weight=pred_W, bias=pred_b, num_hidden=n_class,
                             name=Symbol(name, "_pred_$t"))
    smax = mx.SoftmaxOutput(pred, label, name=Symbol(name, "_softmax_$t"))
    push!(outputs, smax)
  end
  #...
  #--/LSTM-part2

  #--LSTM-part3
  # append block-gradient nodes to the final states
  for i = 1:n_layer
    l_param, l_state = layer_param_states[i]
    final_state = LSTMState(mx.BlockGrad(l_state.c, name=Symbol(name, "_l$(i)_last_c")),
                            mx.BlockGrad(l_state.h, name=Symbol(name, "_l$(i)_last_h")))
    layer_param_states[i] = (l_param, final_state)
  end

  # now group all outputs together
  if output_states
    outputs = outputs ∪ [x[2].c for x in layer_param_states] ∪
                        [x[2].h for x in layer_param_states]
  end
  return mx.Group(outputs...)
end
#--/LSTM-part3

# Negative Log-likelihood
mutable struct NLL <: mx.AbstractEvalMetric
  nll_sum  :: Float64
  n_sample :: Int

  NLL() = new(0.0, 0)
end

function mx.update!(metric::NLL, labels::Vector{<:mx.NDArray}, preds::Vector{<:mx.NDArray})
  @assert length(labels) == length(preds)
  nll = 0.0
  for (label, pred) in zip(labels, preds)
    @mx.nd_as_jl ro=(label, pred) begin
      nll -= sum(log.(max.(broadcast_getindex(pred, round.(Int,label+1), 1:length(label)), 1e-20)))
    end
  end

  nll = nll / length(labels)
  metric.nll_sum += nll
  metric.n_sample += length(labels[1])
end

function mx.get(metric :: NLL)
  nll  = metric.nll_sum / metric.n_sample
  perp = exp(nll)
  return [(:NLL, nll), (:perplexity, perp)]
end

function mx.reset!(metric :: NLL)
  metric.nll_sum  = 0.0
  metric.n_sample = 0
end

max_stars_repo_name: Vikas-kum/incubator-mxnet

max_issues_repo_name: Vikas-kum/incubator-mxnet

max_forks_repo_name: Vikas-kum/incubator-mxnet


text:
#=
dists.jl - Prior distributions and their moments (Author: Julian Johs)
need to calculate mean and standard deviation of used distributions to use them in Dynare

beta_moments calculates mean and standard deviation of Beta distribution
giving plot as argument plots the distribution

beta_solve uses beta_moments to calculate parameters α and β for given
mean and standard deviation - this should give you a feeling for what Dynare does
beta_solve takes 2 real numbers as inputs

the same applies for the functions for the Gamma distribution
=#
using Distributions, StatsPlots, NLsolve

function beta_moments(params::Tuple{Real, Real}; plot=nothing)#; plot::Bool=false
    α = params[1]
    β = params[2]
    dist = Beta(α, β)
    mu = mean(dist)
    sig = std(dist)
    if plot !== nothing
        display(plot(dist)) # you can comment this out
     end
    return (mu, sig)
end
beta_moments(α::Real, β::Real; args...) = beta_moments((α, β); args...)
beta_moments(params::AbstractArray{<:Real, 1}; args...) = beta_moments((params[1], params[2]); args...)

function beta_solve(m::Real, s::Real)
    solver = nlsolve(params -> beta_moments(params) .- (m, s), [1.0, 1.0])
    return solver.zero
end
beta_solve(params::AbstractArray{<:Real, 1}) = beta_solve(params[1], params[2])
beta_solve(params::Tuple{Vararg{<:Real}}) = beta_solve(params[1], params[2])

function gamma_moments(params::Tuple{Real, Real}; plot=nothing)
    α = params[1]
    β = params[2]
    dist = Gamma(α, β)
    mu = mean(dist)
    sig = std(dist)
    if plot !== nothing
        display(plot(dist)) # you can comment this out
    end
    return (mu, sig)
end
gamma_moments(α::Real, β::Real; args...) = gamma_moments((α, β); args...)
gamma_moments(params::AbstractArray{<:Real, 1}; args...) = gamma_moments((params[1], params[2]); args...)

function gamma_solve(m::Real, s::Real)
    solver = nlsolve(params -> gamma_moments(params) .- (m, s), [1.0, 1.0])
    return solver.zero
end
gamma_solve(params::AbstractArray{<:Real, 1}) = gamma_solve(params[1], params[2])
gamma_solve(params::Tuple{Vararg{<:Real}}) =    gamma_solve(params[1], params[2])

function invgamma_moments(params::Tuple{Real, Real}; plot=nothing)
    α = params[1]
    β = params[2]
    dist = InverseGamma(α, β)
    mu = mean(dist)
    sig = std(dist)
    if plot !== nothing
        display(plot(dist)) # you can comment this out
    end
    return (mu, sig)
end
invgamma_moments(α::Real, β::Real; args...) = invgamma_moments((α, β); args...)
invgamma_moments(params::AbstractArray{<:Real, 1}; args...) = invgamma_moments((params[1], params[2]); args...)

function invgamma_solve(m::Real, s::Real; ftol=1e-12)
    solver = nlsolve(params -> invgamma_moments(params) .- (m, s), [2.1, 0.2])
    return solver.zero
end
invgamma_solve(params::AbstractArray{<:Real, 1}) = invgamma_solve(params[1], params[2])
invgamma_solve(params::Tuple{Vararg{<:Real}}) =    invgamma_solve(params[1], params[2])


text:
"""
    FunctionizeBridge{T}

The `FunctionizeBridge` converts a `VariableIndex` objective into a
`ScalarAffineFunction{T}` objective.
"""
struct FunctionizeBridge{T} <: AbstractBridge end

function bridge_objective(
    ::Type{FunctionizeBridge{T}},
    model::MOI.ModelLike,
    func::MOI.VariableIndex,
) where {T}
    F = MOI.ScalarAffineFunction{T}
    MOI.set(model, MOI.ObjectiveFunction{F}(), convert(F, func))
    return FunctionizeBridge{T}()
end

function supports_objective_function(
    ::Type{<:FunctionizeBridge},
    ::Type{MOI.VariableIndex},
)
    return true
end

function MOIB.added_constrained_variable_types(::Type{<:FunctionizeBridge})
    return Tuple{Type}[]
end

function MOIB.added_constraint_types(::Type{<:FunctionizeBridge})
    return Tuple{Type,Type}[]
end

function MOIB.set_objective_function_type(
    ::Type{FunctionizeBridge{T}},
) where {T}
    return MOI.ScalarAffineFunction{T}
end

# Attributes, Bridge acting as a model
MOI.get(::FunctionizeBridge, ::MOI.NumberOfVariables)::Int64 = 0

function MOI.get(::FunctionizeBridge, ::MOI.ListOfVariableIndices)
    return MOI.VariableIndex[]
end

# No variables or constraints are created in this bridge so there is nothing to
# delete.
MOI.delete(model::MOI.ModelLike, bridge::FunctionizeBridge) = nothing

function MOI.set(
    ::MOI.ModelLike,
    ::MOI.ObjectiveSense,
    ::FunctionizeBridge,
    ::MOI.OptimizationSense,
)
    # `FunctionizeBridge` is sense agnostic, therefore, we don't need to change
    # anything.
    return
end

function MOI.get(
    model::MOI.ModelLike,
    attr::MOIB.ObjectiveFunctionValue{MOI.VariableIndex},
    ::FunctionizeBridge{T},
) where {T}
    F = MOI.ScalarAffineFunction{T}
    return MOI.get(model, MOIB.ObjectiveFunctionValue{F}(attr.result_index))
end

function MOI.get(
    model::MOI.ModelLike,
    ::MOI.ObjectiveFunction{MOI.VariableIndex},
    ::FunctionizeBridge{T},
) where {T}
    F = MOI.ScalarAffineFunction{T}
    func = MOI.get(model, MOI.ObjectiveFunction{F}())
    return convert(MOI.VariableIndex, func)
end


text:
include("adaptive_parameters.jl")
include("center_of_mass.jl")

mutable struct ECA <: AbstractParameters
    η_max::Float64
    K::Int
    N::Int
    N_init::Int
    p_exploit::Float64
    p_bin::Float64
    p_cr::Array{Float64}
    ε::Float64
    adaptive::Bool
    resize_population::Bool
end

"""
    ECA(;
        η_max = 2.0,
        K = 7,
        N = 0,
        N_init = N,
        p_exploit = 0.95,
        p_bin = 0.02,
        p_cr = Float64[],
        adaptive = false,
        resize_population = false,
        information = Information(),
        options = Options()
    )

Parameters for the metaheuristic ECA: step-size `η_max`,`K` is number of vectors to
generate the center of mass, `N` is the population size.

# Example

```jldoctest
julia> f(x) = sum(x.^2)
f (generic function with 1 method)

julia> optimize(f, [-1 -1 -1; 1 1 1.0], ECA())
+=========== RESULT ==========+
  iteration: 1429
    minimum: 3.3152400000000004e-223
  minimizer: [4.213750597785841e-113, 5.290977430907081e-112, 2.231685329262638e-112]
    f calls: 29989
 total time: 0.1672 s
+============================+

julia> optimize(f, [-1 -1 -1; 1 1 1.0], ECA(N = 10, η_max = 1.0, K = 3))
+=========== RESULT ==========+
  iteration: 3000
    minimum: 0.000571319
  minimizer: [-0.00017150889316537758, -0.007955828028420616, 0.022538733289139145]
    f calls: 30000
 total time: 0.1334 s
+============================+
```

"""
function ECA(;
    η_max::Float64 = 2.0,
    K::Int = 7,
    N::Int = 0,
    N_init::Int = N,
    p_exploit::Float64 = 0.95,
    p_bin::Float64 = 0.02,
    p_cr::Array{Float64} = Float64[],
    ε::Float64 = 0.0,
    adaptive::Bool = false,
    resize_population::Bool = false,
    information = Information(),
    options = Options(),
)

    N_init = N

    parameters = ECA(
        η_max,
        K,
        N,
        N_init,
        p_exploit,
        p_bin,
        p_cr,
        ε,
        adaptive,
        resize_population,
    )
    Algorithm(
        parameters,
        information = information,
        options = options,
    )

end

function update_state!(
    status,
    parameters::ECA,
    problem::AbstractProblem,
    information::Information,
    options::Options,
    args...;
    kargs...
)
    K = parameters.K
    I = randperm(parameters.N)
    D = size(problem.bounds, 2)

    parameters.adaptive && (Mcr_fail = zeros(D))

    stop = false
    a = problem.bounds[1, :]
    b = problem.bounds[2, :]

    if options.parallel_evaluation
        X_next = zeros(parameters.N, length(a))
    end

    # For each elements in Population
    for i = 1:parameters.N
        p = status.f_calls / options.f_calls_limit

        # current
        x = status.population[i].x

        # generate U masses
        U = getU(status.population, parameters.K, I, i, parameters.N)

        # generate center of mass
        c, u_worst, u_best = center(U)

        # stepsize
        η = parameters.η_max * rand()

        # u: worst element in U
        u = U[u_worst].x

        # current-to-center/bin
        if p < parameters.p_exploit
            # u: worst element in U
            u = U[u_worst].x
            # current-to-center/bin
            y = x .+ η .* (c .- u)
        else
            # current-to-best/bin
            y = x .+ η .* (minimizer(status) .- c)
        end

        # binary crossover
        y, M_current = crossover(U[u_best].x, y, parameters.p_cr)
        evo_boundary_repairer!(y, c, problem.bounds)

        if options.parallel_evaluation
            X_next[i,:] = y
            continue
        end

        sol = create_solution(y, problem)

        # replace worst element
        if is_better(sol, status.population[i])
            wi = argworst(status.population)
            status.population[wi] = sol
            if is_better(sol, status.best_sol)
                status.best_sol = sol
            end
        else
            parameters.adaptive && (Mcr_fail += M_current)
        end

        stop_criteria!(status, parameters, problem, information, options)
        status.stop && break
    end

    if status.stop
        return
    end

    if options.parallel_evaluation
        new_solutions = create_solutions(X_next, problem)
        append!(status.population, new_solutions)
        environmental_selection!(status.population, parameters)
        status.best_sol = get_best(status.population)
    end

    status.f_calls = problem.f_calls

    if parameters.adaptive
        parameters.p_cr =
            adaptCrossover(parameters.p_cr, Mcr_fail / parameters.N)
    end

    resize_population!(status, parameters, options)

end

function resize_population!(status, parameters::ECA, options)
    if !parameters.resize_population
        return
    end

    p = status.f_calls / options.f_calls_limit

    K = parameters.K

    # new size
    parameters.N = 2K .+ round(Int, (1 - p) * (parameters.N_init .- 2K))

    if parameters.N < 2K
        parameters.N = 2K
    end

    status.population = resizePop!(status.population, parameters.N, K)
end

function environmental_selection(population, parameters::ECA)
    @assert length(population) == 2*parameters.N

    new_solutions = population[parameters.N+1:end]
    population = population[1:parameters.N]

    survivals = collect(1:length(population))

    for (i, sol) in enumerate(new_solutions)
        if !is_better(sol, population[i])
            continue
        end
        wi = argworst(population)
        survivals[wi] = parameters.N + i
        population[wi] = sol
    end
    return survivals
end

function environmental_selection!(population, parameters::ECA)
    I = environmental_selection(population, parameters)
    ignored = ones(Bool, length(population))
    ignored[I] .= false
    deleteat!(population, ignored)
end

function initialize!(
        status,
        parameters::ECA,
        problem::AbstractProblem,
        information::Information,
        options::Options,
        args...;
        kargs...
    )
    D = size(problem.bounds, 2)

    if parameters.N <= parameters.K
        parameters.N = parameters.K * D
    end

    if options.f_calls_limit == 0
        options.f_calls_limit = 10000D
        options.debug &&
            @warn( "f_calls_limit increased to $(options.f_calls_limit)")
    end

    if options.iterations == 0
        options.iterations = div(options.f_calls_limit, parameters.N) + 1
    end

    N_init = parameters.N

    if parameters.adaptive
        parameters.p_cr = rand(D)
    else
        parameters.p_cr = parameters.p_bin .* ones(D)
    end

    # initialize!(problem, nothing, parameters, status, information, options)
    st = gen_initial_state(problem,parameters,information,options, status)
    st

end

function final_stage!(
    status,
    parameters::ECA,
    problem::AbstractProblem,
    information::Information,
    options::Options,
    args...;
    kargs...
    )
    status.final_time = time()
end


text:
@testset "sum_tree" begin
    t = SumTree(8)

    @test capacity(t) == 8

    for i = 1:4
        push!(t, i)
    end

    @test length(t) == 4
    @test size(t) == (4,)

    for i = 5:16
        push!(t, i)
    end

    @test length(t) == 8
    @test size(t) == (8,)
    @test t == 9:16

    t[:] .= 1
    @test t == ones(8)
    @test all([RL.Utils.get(t, v)[1] == i for (i, v) in enumerate(0.5:1.0:8)])

    empty!(t)
    @test capacity(t) == 8
    @test length(t) == 0
end


text:
# This file is a part of SolidStateDetectors.jl, licensed under the MIT License (MIT).
using Test

# using CUDAKernels # Uncomment this line in order to run all tests on (CUDA) GPU
using SolidStateDetectors

using SpecialFunctions
using StaticArrays
using StatsBase
using Tables, TypedTables
using Unitful

T = Float32
device_array_type = (@isdefined CUDAKernels) ? CUDAKernels.CUDA.CuArray : Array

@testset "Comparison to analytic solutions" begin
    include("comparison_to_analytic_solutions.jl")
end

@testset "SOR GPU Backend" begin
    include("SOR_GPU_Backend.jl")
end

@testset "ConstructiveSolidGeometry" begin
    include("ConstructiveSolidGeometry/CSG_IO.jl")
    include("ConstructiveSolidGeometry/CSG_primitives.jl")
end

T = Float32

@testset "Test real detectors" begin
    @testset "Simulate example detector: Inverted Coax" begin
        sim = Simulation{T}(SSD_examples[:InvertedCoax])
        simulate!(sim, convergence_limit = 1e-6, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)
        evt = Event(CartesianPoint.([CylindricalPoint{T}(20e-3, deg2rad(10), 10e-3 )]))
        simulate!(evt, sim, Δt = 1e-9, max_nsteps = 10000)
        signalsum = T(0)
        for i in 1:length(evt.waveforms)
            signalsum += abs(ustrip(evt.waveforms[i].value[end]))
        end
        signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
        @info signalsum
        @test isapprox( signalsum, T(2), atol = 5e-3 )
        nt = NamedTuple(sim)
        @test sim == Simulation(nt)
    end
    @testset "Simulate example detector: Inverted Coax (in cryostat)" begin
        sim = Simulation{T}(SSD_examples[:InvertedCoaxInCryostat])
        simulate!(sim, convergence_limit = 1e-6, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)
        evt = Event(CartesianPoint.([CylindricalPoint{T}(20e-3, deg2rad(10), 10e-3 )]))
        simulate!(evt, sim, Δt = 1e-9, max_nsteps = 10000)
        signalsum = T(0)
        for i in 1:length(evt.waveforms)
            signalsum += abs(ustrip(evt.waveforms[i].value[end]))
        end
        signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
        @info signalsum
        @test isapprox( signalsum, T(2), atol = 5e-3 )
    end
    # @testset "Simulate example detector: Coax" begin
    #     sim = Simulation{T}(SSD_examples[:Coax])
    #     calculate_electric_potential!(sim, convergence_limit = 1e-6, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)
    #     calculate_electric_field!(sim)
    #     calculate_weighting_potential!(sim, 1, convergence_limit = 1e-6, refinement_limits = [0.2, 0.1], verbose = false)
    #     calculate_weighting_potential!(sim, 2, convergence_limit = 1e-6, refinement_limits = [0.2, 0.1], verbose = false)
    #     for i in 3:19
    #         calculate_weighting_potential!(sim, i, convergence_limit = 5e-6, refinement_limits = [0.2], verbose = false)
    #     end
    #     evt = Event(CartesianPoint.([CylindricalPoint{T}(20e-3, deg2rad(30), 12e-3 )]))
    #     simulate!(evt, sim, Δt = 5e-10, max_nsteps = 10000)
    #     signalsum = T(0)
    #     for i in 1:length(evt.waveforms)
    #         signalsum += abs(ustrip(evt.waveforms[i].value[end]))
    #     end
    #     signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
    #     @info signalsum
    #     @test isapprox( signalsum, T(2), atol = 5e-3 )
    # end
    @testset "Simulate example detector: BEGe" begin
        sim = Simulation{T}(SSD_examples[:BEGe])
        calculate_electric_potential!(sim, convergence_limit = 1e-6, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)
        calculate_electric_field!(sim)
        calculate_weighting_potential!(sim, 1, convergence_limit = 1e-6, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)
        for i in 2:5
            calculate_weighting_potential!(sim, i, convergence_limit = 5e-6, device_array_type = device_array_type, refinement_limits = [0.2], verbose = false)
        end
        evt = Event(CartesianPoint.([CylindricalPoint{T}(20e-3, deg2rad(10), 20e-3 )]))
        simulate!(evt, sim, Δt = 1e-9, max_nsteps = 10000)
        signalsum = T(0)
        for i in 1:length(evt.waveforms)
            signalsum += abs(ustrip(evt.waveforms[i].value[end]))
        end
        signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
        @info signalsum
        @test isapprox( signalsum, T(2), atol = 5e-3 )
        nt = NamedTuple(sim)
        @test sim == Simulation(nt)
    end
    @testset "Simulate example detector: HexagonalPrism" begin
        sim = Simulation{T}(SSD_examples[:Hexagon])
        simulate!(sim, convergence_limit = 1e-6, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)
        evt = Event([CartesianPoint{T}(0, 5e-4, 1e-3)])
        simulate!(evt, sim, Δt = 1e-9, max_nsteps = 10000)
        signalsum = T(0)
        for i in 1:length(evt.waveforms)
            signalsum += abs(ustrip(evt.waveforms[i].value[end]))
        end
        signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
        @info signalsum
        @test isapprox( signalsum, T(2), atol = 5e-3 )
    end
    @testset "Simulate example detector: CGD" begin
        sim = Simulation{T}(SSD_examples[:CGD])
        simulate!(sim, convergence_limit = 1e-6, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)
        evt = Event([CartesianPoint{T}(0,2e-3,0)])
        simulate!(evt, sim, Δt = 1e-9, max_nsteps = 10000)
        signalsum = T(0)
        for i in 1:length(evt.waveforms)
            signalsum += abs(ustrip(evt.waveforms[i].value[end]))
        end
        signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
        @info signalsum
        @test isapprox( signalsum, T(2), atol = 5e-3 )
        nt = NamedTuple(sim)
        @test sim == Simulation(nt)
    end
    @testset "Simulate example detector: Spherical" begin
        sim = Simulation{T}(SSD_examples[:Spherical])
        simulate!(sim, convergence_limit = 1e-5, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)
        evt = Event([CartesianPoint{T}(0,0,0)])
        simulate!(evt, sim)
        signalsum = T(0)
        for i in 1:length(evt.waveforms)
            signalsum += abs(ustrip(evt.waveforms[i].value[end]))
        end
        signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
        @info signalsum
        @test isapprox( signalsum, T(2), atol = 5e-3 )
    end
    @testset "Simulate example detector: Toroidal" begin
        sim = Simulation{T}(SSD_examples[:CoaxialTorus])
        SolidStateDetectors.apply_initial_state!(sim, ElectricPotential)
        simulate!(sim, convergence_limit = 1e-5, device_array_type = device_array_type, refinement_limits = [0.2, 0.1, 0.05, 0.02, 0.01],
            max_tick_distance = 0.5u"mm", verbose = false)
        evt = Event([CartesianPoint{T}(0.0075,0,0)])
        simulate!(evt, sim, Δt = 1e-9, max_nsteps = 10000)
        signalsum = T(0)
        for i in 1:length(evt.waveforms)
            signalsum += abs(ustrip(evt.waveforms[i].value[end]))
        end
        signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
        @info signalsum
        @test isapprox( signalsum, T(2), atol = 5e-3 )
    end
    @testset "Simulate example detector: SigGen PPC" begin
        sim = Simulation{T}(SSD_examples[:SigGen])
        simulate!(sim, convergence_limit = 1e-6, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)
        evt = Event(CartesianPoint.([CylindricalPoint{T}(20e-3, deg2rad(10), 10e-3 )]))
        simulate!(evt, sim, Δt = 1e-9, max_nsteps = 10000)
        signalsum = T(0)
        for i in 1:length(evt.waveforms)
            signalsum += abs(ustrip(evt.waveforms[i].value[end]))
        end
        signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
        @info signalsum
        @test isapprox( signalsum, T(2), atol = 5e-3 )
    end
end

@testset "Diffusion and Self-Repulsion" begin
    sim = Simulation{T}(SSD_examples[:InvertedCoax])
    simulate!(sim, convergence_limit = 1e-5, device_array_type = device_array_type, refinement_limits = [0.2, 0.1, 0.05], verbose = false)

    pos = CartesianPoint{T}(0.02,0,0.05); Edep = 1u"eV"
    nbcc = NBodyChargeCloud(pos, Edep, 40, radius = T(0.0005), number_of_shells = 2)

    evt = Event(nbcc)
    simulate!(evt, sim, self_repulsion = true, diffusion = true)
    signalsum = T(0)
    for i in 1:length(evt.waveforms)
        signalsum += abs(ustrip(evt.waveforms[i].value[end]))
    end
    signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
    @info signalsum
    @test isapprox( signalsum, T(2), atol = 5e-3 )
end

@testset "Table Simulation" begin
    sim = Simulation{T}(SSD_examples[:InvertedCoax])
    simulate!(sim, convergence_limit = 1e-5, device_array_type = device_array_type, refinement_limits = [0.2, 0.1], verbose = false)

    evt_table = Table(
        evtno = Int32[1],
        detno = Int32[1],
        thit = [T[0] * u"s"],
        edep = [T[1] * u"eV"],
        pos = [[SVector{3, T}.(0.01, 0.01, 0.01) * u"m"]]
    )
    contact_charge_signals = simulate_waveforms(
        evt_table,
        sim,
        max_nsteps = 4000,
        Δt = 1u"ns",
        number_of_carriers = 20,
        number_of_shells = 2,
        verbose = false);
    signalsum = T(0)
    for i in 1:length(contact_charge_signals.waveform)
        signalsum += abs(ustrip(contact_charge_signals.waveform[i].value[end]))
    end
    signalsum *= inv(ustrip(SolidStateDetectors._convert_internal_energy_to_external_charge(sim.detector.semiconductor.material)))
    @test isapprox( signalsum, T(2), atol = 5e-3 )
end

@testset "ADLChargeDriftModel" begin
    include("ADLChargeDriftModel.jl")
end

@testset "IO" begin
    sim = Simulation(SSD_examples[:InvertedCoax])

    calculate_electric_potential!(sim, verbose = false, device_array_type = device_array_type)
    nt = NamedTuple(sim)
    @test sim == Simulation(nt)

    calculate_electric_field!(sim)
    nt = NamedTuple(sim)
    @test sim == Simulation(nt)

    calculate_weighting_potential!(sim, 1, verbose = false, device_array_type = device_array_type)
    nt = NamedTuple(sim)
    @test sim == Simulation(nt)

    for i in findall(ismissing.(sim.weighting_potentials)) calculate_weighting_potential!(sim, i, verbose = false, device_array_type = device_array_type) end
    nt = NamedTuple(sim)
    @test sim == Simulation(nt)
end


text:
const Point4f = Point{4,Float32}

struct PosColor{P<:Point,C<:Colorant}
    position::P
    color::C
end

struct PosUV{P<:Point,UV<:Point{2}}
    position::P
    uv::UV
end

# type piracy
@nospecialize
Vulkan.Format(::Type{Point{1,Float32}}) = FORMAT_R32_SFLOAT
Vulkan.Format(::Type{Point{2,Float32}}) = FORMAT_R32G32_SFLOAT
Vulkan.Format(::Union{Type{Point{3,Float32}},RGB{Float32}}) = FORMAT_R32G32B32_SFLOAT
Vulkan.Format(::Union{Type{Point{4,Float32}},RGBA{Float32}}) = FORMAT_R32G32B32A32_SFLOAT
Vulkan.Format(::Type{RGB{Float16}}) = FORMAT_R16G16B16_SFLOAT
Vulkan.Format(::Type{RGBA{Float16}}) = FORMAT_R16G16B16A16_SFLOAT
@specialize