text:
#=
You run an e-commerce website and want to record the last N order ids in a log. Implement a data structure to accomplish this, with the following API:

    record(order_id): adds the order_id to the log
    get_last(i): gets the ith last element from the log. i is guaranteed to be smaller than or equal to N.

You should be as efficient with time and space as possible.
=#

using Test
include("Solutions/problem16_log_orderID.jl")

for i in 1:10
    record(i)
end

@test length(log) == N
@test get_last(2) == 9

max_stars_repo_name: DominiqueCaron/daily-coding-problem

max_issues_repo_name: DominiqueCaron/daily-coding-problem

max_forks_repo_name: DominiqueCaron/daily-coding-problem


text:
export vectorize,⊙,≂,clip,rasterPlot,activity,ξ,sigmoid,heaviside,delta

function vectorize(str)
  str=replace(str,".*","*")
  str=replace(str,"./","/")
  str=replace(str,".^","^")
  str=replace(str,"*",".*")
  str=replace(str,"/","./")
  str=replace(str,"^",".^")
  return str
end

function ⊙(A,B)
  A*B
end

function ≂(a,b)
  (abs(a-b)<=net.dt/2)?true:false
end
@vectorize_2arg(Number,≂)

function clip(x,a,b)
  heaviside(x-a)-heaviside(x-b)
end

function rasterPlot(net)
  t=[]
  neuron=[]
  for n=1:length(net.tSpike)
    append!(t,net.tSpike[n])
    append!(neuron,n*ones(length(net.tSpike[n])))
  end
  t=convert(Array{Float64},t)
  neuron=convert(Array{Float64},neuron)
  idx=find(t.>0)
  t=t[idx]
  neuron=neuron[idx]
  return t,neuron
end

function edge2center(edge)
dx=edge[2]-edge[1]
center=edge[1:end-1]+dx
end

function activity(net)
  t,~=rasterPlot(net)
  edge,counts=hist(t)
  rate=counts/(edge[2]-edge[1])
  ratemax=maximum(rate)
  center=edge2center([edge;])
  return center,rate
end

function ξ(t::Number)
  √net.dt*randn(net.N)
end
function η(t::Number)
  √net.dt*randn()
end

function sigmoid(x)
  y=1./(1+exp(-x))
end

function heaviside(x)
0.5*(1+sign(x))
end

function delta(x)
δx=1e-3
(heavisid(x+δx/2)-heavisid(x-δx/2))/δx
end

function delta(x,δx)
(heavisid(x+δx/2)-heavisid(x-δx/2))/δx
end

function print(ex...)
    # println(ex...)
end

ext: jl


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

const Cstring_NULL = convert(Cstring, Ptr{UInt8}(C_NULL))

const OID_RAWSZ = 20
const OID_HEXSZ = OID_RAWSZ * 2
const OID_MINPREFIXLEN = 4

immutable Oid
    val::NTuple{OID_RAWSZ, UInt8}
    Oid(val::NTuple{OID_RAWSZ, UInt8}) = new(val)
end
Oid() = Oid(ntuple(i->zero(UInt8), OID_RAWSZ))

immutable TimeStruct
    time::Int64     # time in seconds from epoch
    offset::Cint    # timezone offset in minutes
end
TimeStruct() = TimeStruct(zero(Int64), zero(Cint))

immutable SignatureStruct
    name::Ptr{UInt8}  # full name of the author
    email::Ptr{UInt8} # email of the author
    when::TimeStruct  # time when the action happened
end
SignatureStruct() = SignatureStruct(Ptr{UInt8}(0),
                                    Ptr{UInt8}(0),
                                    TimeStruct())

immutable StrArrayStruct
   strings::Ptr{Cstring}
   count::Csize_t
end
StrArrayStruct() = StrArrayStruct(Ptr{Cstring}(C_NULL), zero(Csize_t))
function Base.finalize(sa::StrArrayStruct)
    sa_ptr = Ref(sa)
    ccall((:git_strarray_free, :libgit2), Void, (Ptr{StrArrayStruct},), sa_ptr)
    return sa_ptr[]
end

immutable Buffer
    ptr::Ptr{Cchar}
    asize::Csize_t
    size::Csize_t
end
Buffer() = Buffer(Ptr{Cchar}(C_NULL), zero(Csize_t), zero(Csize_t))
function Base.finalize(buf::Buffer)
    buf_ptr = Ref(buf)
    ccall((:git_buf_free, :libgit2), Void, (Ptr{Buffer},), buf_ptr)
    return buf_ptr[]
end

"Abstract credentials payload"
abstract AbstractCredentials

"Checks if credentials were used"
checkused!(p::AbstractCredentials) = true
checkused!(p::Void) = false
"Resets credentials for another use"
reset!(p::AbstractCredentials, cnt::Int=3) = nothing

immutable CheckoutOptions
    version::Cuint

    checkout_strategy::Cuint

    disable_filters::Cint
    dir_mode::Cuint
    file_mode::Cuint
    file_open_flags::Cint

    notify_flags::Cuint
    notify_cb::Ptr{Void}
    notify_payload::Ptr{Void}

    progress_cb::Ptr{Void}
    progress_payload::Ptr{Void}

    paths::StrArrayStruct

    baseline::Ptr{Void}
    baseline_index::Ptr{Void}

    target_directory::Cstring
    ancestor_label::Cstring
    our_label::Cstring
    their_label::Cstring

    perfdata_cb::Ptr{Void}
    perfdata_payload::Ptr{Void}
end
CheckoutOptions(; checkout_strategy::Cuint = Consts.CHECKOUT_SAFE,
                  disable_filters::Cint = zero(Cint),
                  dir_mode::Cuint = Cuint(0), # Cuint(0o755),
                  file_mode::Cuint = Cuint(0), #Cuint(0o644),
                  file_open_flags::Cint = zero(Cint),
                  notify_flags::Cuint = Consts.CHECKOUT_NOTIFY_NONE,
                  notify_cb::Ptr{Void} = Ptr{Void}(0),
                  notify_payload::Ptr{Void} = Ptr{Void}(0),
                  progress_cb::Ptr{Void} = Ptr{Void}(0),
                  progress_payload::Ptr{Void} = Ptr{Void}(0),
                  paths::StrArrayStruct = StrArrayStruct(),
                  baseline::Ptr{Void} = Ptr{Void}(0),
                  baseline_index::Ptr{Void} = Ptr{Void}(0),
                  target_directory::Cstring = Cstring_NULL,
                  ancestor_label::Cstring = Cstring_NULL,
                  our_label::Cstring = Cstring_NULL,
                  their_label::Cstring = Cstring_NULL,
                  perfdata_cb::Ptr{Void} = Ptr{Void}(0),
                  perfdata_payload::Ptr{Void} = Ptr{Void}(0)) =
    CheckoutOptions(one(Cuint),
                    checkout_strategy,
                    disable_filters,
                    dir_mode,
                    file_mode,
                    file_open_flags,
                    notify_flags,
                    notify_cb,
                    notify_payload,
                    progress_cb,
                    progress_payload,
                    paths,
                    baseline,
                    baseline_index,
                    target_directory,
                    ancestor_label,
                    our_label,
                    their_label,
                    perfdata_cb,
                    perfdata_payload)

immutable RemoteCallbacks
    version::Cuint
    sideband_progress::Ptr{Void}
    completion::Ptr{Void}
    credentials::Ptr{Void}
    certificate_check::Ptr{Void}
    transfer_progress::Ptr{Void}
    update_tips::Ptr{Void}
    pack_progress::Ptr{Void}
    push_transfer_progress::Ptr{Void}
    push_update_reference::Ptr{Void}
    push_negotiation::Ptr{Void}
    transport::Ptr{Void}
    payload::Ptr{Void}
end
RemoteCallbacks(; sideband_progress::Ptr{Void} = C_NULL,
                  completion::Ptr{Void} = C_NULL,
                  credentials::Ptr{Void} = C_NULL,
                  certificate_check::Ptr{Void} = C_NULL,
                  transfer_progress::Ptr{Void} = C_NULL,
                  update_tips::Ptr{Void} = C_NULL,
                  pack_progress::Ptr{Void} = C_NULL,
                  push_transfer_progress::Ptr{Void} = C_NULL,
                  push_update_reference::Ptr{Void} = C_NULL,
                  push_negotiation::Ptr{Void} = C_NULL,
                  transport::Ptr{Void} = C_NULL,
                  payload::Ptr{Void} = C_NULL) =
    RemoteCallbacks(one(Cuint),
                    sideband_progress,
                    completion,
                    credentials,
                    certificate_check,
                    transfer_progress,
                    update_tips,
                    pack_progress,
                    push_transfer_progress,
                    push_update_reference,
                    push_negotiation,
                    transport,
                    payload)

function RemoteCallbacks(credentials::Ptr{Void}, payload::Ref{Nullable{AbstractCredentials}})
    RemoteCallbacks(credentials=credentials_cb(), payload=pointer_from_objref(payload))
end

if LibGit2.version() >= v"0.24.0"
    immutable FetchOptions
        version::Cuint
        callbacks::RemoteCallbacks
        prune::Cint
        update_fetchhead::Cint
        download_tags::Cint
        custom_headers::StrArrayStruct
    end
    FetchOptions(; callbacks::RemoteCallbacks = RemoteCallbacks(),
                   prune::Cint = Consts.FETCH_PRUNE_UNSPECIFIED,
                   update_fetchhead::Cint = one(Cint),
                   download_tags::Cint = Consts.REMOTE_DOWNLOAD_TAGS_AUTO,
                   custom_headers::StrArrayStruct = StrArrayStruct()) =
        FetchOptions(one(Cuint),
                     callbacks,
                     prune,
                     update_fetchhead,
                     download_tags,
                     custom_headers)
else
    immutable FetchOptions
        version::Cuint
        callbacks::RemoteCallbacks
        prune::Cint
        update_fetchhead::Cint
        download_tags::Cint
    end
    FetchOptions(; callbacks::RemoteCallbacks = RemoteCallbacks(),
                   prune::Cint = Consts.FETCH_PRUNE_UNSPECIFIED,
                   update_fetchhead::Cint = one(Cint),
                   download_tags::Cint = Consts.REMOTE_DOWNLOAD_TAGS_AUTO) =
        FetchOptions(one(Cuint),
                     callbacks,
                     prune,
                     update_fetchhead,
                     download_tags)
end

immutable CloneOptions
    version::Cuint
    checkout_opts::CheckoutOptions
    fetch_opts::FetchOptions
    bare::Cint
    localclone::Cint
    checkout_branch::Cstring
    repository_cb::Ptr{Void}
    repository_cb_payload::Ptr{Void}
    remote_cb::Ptr{Void}
    remote_cb_payload::Ptr{Void}
end
CloneOptions(; checkout_opts::CheckoutOptions = CheckoutOptions(),
               fetch_opts::FetchOptions = FetchOptions(),
               bare::Cint = zero(Cint),
               localclone::Cint = Consts.CLONE_LOCAL_AUTO,
               checkout_branch::Cstring = Cstring_NULL,
               repository_cb::Ptr{Void} = Ptr{Void}(0),
               repository_cb_payload::Ptr{Void} = Ptr{Void}(0),
               remote_cb::Ptr{Void} = Ptr{Void}(0),
               remote_cb_payload::Ptr{Void} = Ptr{Void}(0)) =
    CloneOptions(one(Cuint),
                 checkout_opts,
                 fetch_opts,
                 bare,
                 localclone,
                 checkout_branch,
                 repository_cb,
                 repository_cb_payload,
                 remote_cb,
                 remote_cb_payload)

# git diff option struct
if LibGit2.version() >= v"0.24.0"
    immutable DiffOptionsStruct
        version::Cuint
        flags::UInt32

        # options controlling which files are in the diff
        ignore_submodules::Cint
        pathspec::StrArrayStruct
        notify_cb::Ptr{Void}
        progress_cb::Ptr{Void}
        payload::Ptr{Void}

        # options controlling how the diff text is generated
        context_lines::UInt32
        interhunk_lines::UInt32
        id_abbrev::UInt16
        max_size::Int64
        old_prefix::Cstring
        new_prefix::Cstring
    end
    DiffOptionsStruct(; flags::UInt32 = Consts.DIFF_NORMAL,
                        ignore_submodules::Cint = Cint(Consts.SUBMODULE_IGNORE_UNSPECIFIED),
                        pathspec::StrArrayStruct = StrArrayStruct(),
                        notify_cb::Ptr{Void} = C_NULL,
                        progress_cb::Ptr{Void} = C_NULL,
                        notify_payload::Ptr{Void} = C_NULL,
                        context_lines::UInt32 = UInt32(3),
                        interhunk_lines::UInt32 = zero(UInt32),
                        id_abbrev::UInt16 = UInt16(7),
                        max_size::Int64 = Int64(512*1024*1024), #zero(Int64), #512Mb
                        old_prefix::Cstring = Cstring_NULL,
                        new_prefix::Cstring = Cstring_NULL) =
        DiffOptionsStruct(Consts.DIFF_OPTIONS_VERSION,
                          flags,
                          ignore_submodules,
                          pathspec,
                          notify_cb,
                          progress_cb,
                          notify_payload,
                          context_lines,
                          interhunk_lines,
                          id_abbrev,
                          max_size,
                          old_prefix,
                          new_prefix)
else
    immutable DiffOptionsStruct
        version::Cuint
        flags::UInt32

        # options controlling which files are in the diff
        ignore_submodules::Cint
        pathspec::StrArrayStruct
        notify_cb::Ptr{Void}
        payload::Ptr{Void}

        # options controlling how the diff text is generated
        context_lines::UInt32
        interhunk_lines::UInt32
        id_abbrev::UInt16
        max_size::Int64
        old_prefix::Cstring
        new_prefix::Cstring
    end
    DiffOptionsStruct(; flags::UInt32 = Consts.DIFF_NORMAL,
                        ignore_submodules::Cint = Cint(Consts.SUBMODULE_IGNORE_UNSPECIFIED),
                        pathspec::StrArrayStruct = StrArrayStruct(),
                        notify_cb::Ptr{Void} = C_NULL,
                        notify_payload::Ptr{Void} = C_NULL,
                        context_lines::UInt32 = UInt32(3),
                        interhunk_lines::UInt32 = zero(UInt32),
                        id_abbrev::UInt16 = UInt16(7),
                        max_size::Int64 = Int64(512*1024*1024), #zero(Int64), #512Mb
                        old_prefix::Cstring = Cstring_NULL,
                        new_prefix::Cstring = Cstring_NULL) =
        DiffOptionsStruct(Consts.DIFF_OPTIONS_VERSION,
                          flags,
                          ignore_submodules,
                          pathspec,
                          notify_cb,
                          notify_payload,
                          context_lines,
                          interhunk_lines,
                          id_abbrev,
                          max_size,
                          old_prefix,
                          new_prefix)
end

immutable DiffFile
    id::Oid
    path::Cstring
    size::Int64
    flags::UInt32
    mode::UInt16
end
DiffFile() = DiffFile(Oid(), Cstring_NULL, Int64(0), UInt32(0), UInt16(0))

immutable DiffDelta
    status::Cint
    flags::UInt32
    similarity::UInt16
    nfiles::UInt16
    old_file::DiffFile
    new_file::DiffFile
end
DiffDelta() = DiffDelta(Cint(0), UInt32(0), UInt16(0), UInt16(0), DiffFile(), DiffFile())

# TODO: double check this when libgit2 v0.25.0 is released
if LibGit2.version() >= v"0.25.0"
    immutable MergeOptions
        version::Cuint
        flags::Cint
        rename_threshold::Cuint
        target_limit::Cuint
        metric::Ptr{Void}
        recursion_limit::Cuint
        default_driver::Cstring
        file_favor::Cint
        file_flags::Cuint
    end
    MergeOptions(; flags::Cint = Cint(0),
                   rename_threshold::Cuint = Cuint(50),
                   target_limit::Cuint = Cuint(200),
                   metric::Ptr{Void} = C_NULL,
                   recursion_limit::Cuint = Cuint(0),
                   default_driver::Cstring = Cstring_NULL,
                   file_favor::Cint = Cint(Consts.MERGE_FILE_FAVOR_NORMAL),
                   file_flags::Cuint = Cuint(Consts.MERGE_FILE_DEFAULT)) =
        MergeOptions(one(Cuint),
                     flags,
                     rename_threshold,
                     target_limit,
                     metric,
                     recursion_limit,
                     default_driver,
                     file_favor,
                     file_flags)
elseif LibGit2.version() >= v"0.24.0"
    immutable MergeOptions
        version::Cuint
        flags::Cint
        rename_threshold::Cuint
        target_limit::Cuint
        metric::Ptr{Void}
        recursion_limit::Cuint
        file_favor::Cint
        file_flags::Cuint
    end
    MergeOptions(; flags::Cint = Cint(0),
                   rename_threshold::Cuint = Cuint(50),
                   target_limit::Cuint = Cuint(200),
                   metric::Ptr{Void} = C_NULL,
                   recursion_limit::Cuint = Cuint(0),
                   file_favor::Cint = Cint(Consts.MERGE_FILE_FAVOR_NORMAL),
                   file_flags::Cuint = Cuint(Consts.MERGE_FILE_DEFAULT)) =
        MergeOptions(one(Cuint),
                     flags,
                     rename_threshold,
                     target_limit,
                     metric,
                     recursion_limit,
                     file_favor,
                     file_flags)
else
    immutable MergeOptions
        version::Cuint
        flags::Cint
        rename_threshold::Cuint
        target_limit::Cuint
        metric::Ptr{Void}
        file_favor::Cint
        file_flags::Cuint
    end
    MergeOptions(; flags::Cint = Cint(0),
                   rename_threshold::Cuint = Cuint(50),
                   target_limit::Cuint = Cuint(200),
                   metric::Ptr{Void} = C_NULL,
                   file_favor::Cint = Cint(Consts.MERGE_FILE_FAVOR_NORMAL),
                   file_flags::Cuint = Cuint(Consts.MERGE_FILE_DEFAULT)) =
        MergeOptions(one(Cuint),
                     flags,
                     rename_threshold,
                     target_limit,
                     metric,
                     file_favor,
                     file_flags)
end

if LibGit2.version() >= v"0.24.0"
    immutable PushOptions
        version::Cuint
        parallelism::Cint
        callbacks::RemoteCallbacks
        custom_headers::StrArrayStruct
    end
    PushOptions(; parallelism::Cint=one(Cint),
                  callbacks::RemoteCallbacks=RemoteCallbacks(),
                  custom_headers::StrArrayStruct = StrArrayStruct()) =
        PushOptions(one(Cuint),
                    parallelism,
                    callbacks,
                    custom_headers)
else
    immutable PushOptions
        version::Cuint
        parallelism::Cint
        callbacks::RemoteCallbacks
    end
    PushOptions(; parallelism::Cint=one(Cint),
                  callbacks::RemoteCallbacks=RemoteCallbacks()) =
        PushOptions(one(Cuint),
                    parallelism,
                    callbacks)
end

immutable IndexTime
    seconds::Int64
    nanoseconds::Cuint
    IndexTime() = new(zero(Int64), zero(Cuint))
end

immutable IndexEntry
    ctime::IndexTime
    mtime::IndexTime

    dev::UInt32
    ino::UInt32
    mode::UInt32
    uid::UInt32
    gid::UInt32
    file_size::Int64

    id::Oid

    flags::UInt16
    flags_extended::UInt16

    path::Ptr{UInt8}
end
IndexEntry() = IndexEntry(IndexTime(),
                          IndexTime(),
                          UInt32(0),
                          UInt32(0),
                          UInt32(0),
                          UInt32(0),
                          UInt32(0),
                          Int64(0),
                          Oid(),
                          UInt16(0),
                          UInt16(0),
                          Ptr{UInt8}(0))
Base.show(io::IO, ie::IndexEntry) = print(io, "IndexEntry($(string(ie.id)))")

if LibGit2.version() >= v"0.24.0"
    immutable RebaseOptions
        version::Cuint
        quiet::Cint
        inmemory::Cint
        rewrite_notes_ref::Cstring
        merge_opts::MergeOptions
        checkout_opts::CheckoutOptions
    end
    RebaseOptions(; quiet::Cint = Cint(1),
                    inmemory::Cint = Cint(0),
                    rewrite_notes_ref::Cstring = Cstring_NULL,
                    merge_opts::MergeOptions = MergeOptions(),
                    checkout_opts::CheckoutOptions = CheckoutOptions()) =
        RebaseOptions(one(Cuint), quiet, inmemory, rewrite_notes_ref, merge_opts, checkout_opts)
else
    immutable RebaseOptions
        version::Cuint
        quiet::Cint
        rewrite_notes_ref::Cstring
        checkout_opts::CheckoutOptions
    end
    RebaseOptions(; quiet::Cint = Cint(1),
                    rewrite_notes_ref::Cstring = Cstring_NULL,
                    checkout_opts::CheckoutOptions = CheckoutOptions()) =
        RebaseOptions(one(Cuint), quiet, rewrite_notes_ref, checkout_opts)
end

immutable RebaseOperation
    optype::Cint
    id::Oid
    exec::Cstring
end
RebaseOperation() = RebaseOperation(Cint(0), Oid(), Cstring_NULL)
Base.show(io::IO, rbo::RebaseOperation) = print(io, "RebaseOperation($(string(rbo.id)))")

immutable StatusOptions
    version::Cuint
    show::Cint
    flags::Cuint
    pathspec::StrArrayStruct
end
StatusOptions(; show::Cint = Consts.STATUS_SHOW_INDEX_AND_WORKDIR,
                flags::Cuint = Consts.STATUS_OPT_INCLUDE_UNTRACKED |
                               Consts.STATUS_OPT_RECURSE_UNTRACKED_DIRS |
                               Consts.STATUS_OPT_RENAMES_HEAD_TO_INDEX |
                               Consts.STATUS_OPT_SORT_CASE_SENSITIVELY,
                pathspec::StrArrayStruct = StrArrayStruct()) =
    StatusOptions(one(Cuint),
                  show,
                  flags,
                  pathspec)

immutable StatusEntry
    status::Cuint
    head_to_index::Ptr{DiffDelta}
    index_to_workdir::Ptr{DiffDelta}
end
StatusEntry() = StatusEntry(Cuint(0), C_NULL, C_NULL)

immutable FetchHead
    name::String
    url::String
    oid::Oid
    ismerge::Bool
end

# Abstract object types
abstract AbstractGitObject
Base.isempty(obj::AbstractGitObject) = (obj.ptr == C_NULL)

abstract GitObject <: AbstractGitObject
function Base.finalize(obj::GitObject)
    if obj.ptr != C_NULL
        ccall((:git_object_free, :libgit2), Void, (Ptr{Void},), obj.ptr)
        obj.ptr = C_NULL
    end
end

# Common types
for (typ, ref, sup, fnc) in (
            (:GitRemote,     :Void, :AbstractGitObject, :(:git_remote_free)),
            (:GitRevWalker,  :Void, :AbstractGitObject, :(:git_revwalk_free)),
            (:GitConfig,     :Void, :AbstractGitObject, :(:git_config_free)),
            (:GitReference,  :Void, :AbstractGitObject, :(:git_reference_free)),
            (:GitDiff,       :Void, :AbstractGitObject, :(:git_diff_free)),
            (:GitIndex,      :Void, :AbstractGitObject, :(:git_index_free)),
            (:GitRepo,       :Void, :AbstractGitObject, :(:git_repository_free)),
            (:GitAnnotated,  :Void, :AbstractGitObject, :(:git_annotated_commit_free)),
            (:GitRebase,     :Void, :AbstractGitObject, :(:git_rebase_free)),
            (:GitStatus,     :Void, :AbstractGitObject, :(:git_status_list_free)),
            (:GitBranchIter, :Void, :AbstractGitObject, :(:git_branch_iterator_free)),
            (:GitTreeEntry,  :Void, :AbstractGitObject, :(:git_tree_entry_free)),
            (:GitSignature,  :SignatureStruct, :AbstractGitObject, :(:git_signature_free)),
            (:GitAnyObject,  :Void, :GitObject, nothing),
            (:GitCommit,     :Void, :GitObject, nothing),
            (:GitBlob,       :Void, :GitObject, nothing),
            (:GitTree,       :Void, :GitObject, nothing),
            (:GitTag,        :Void, :GitObject, nothing)
        )

    @eval type $typ <: $sup
        ptr::Ptr{$ref}
        function $typ(ptr::Ptr{$ref})
            @assert ptr != C_NULL
            obj = new(ptr)
            return obj
        end
    end

    if fnc !== nothing
        @eval function Base.finalize(obj::$typ)
            if obj.ptr != C_NULL
                ccall(($fnc, :libgit2), Void, (Ptr{$ref},), obj.ptr)
                obj.ptr = C_NULL
            end
        end
    end

end

# Structure has the same layout as SignatureStruct
type Signature
    name::String
    email::String
    time::Int64
    time_offset::Cint
end

""" Resource management helper function
"""
function with(f::Function, obj)
    try
        f(obj)
    finally
        finalize(obj)
    end
end

with{T}(f::Function, ::Type{T}, args...) = with(f, T(args...))

function with_warn{T}(f::Function, ::Type{T}, args...)
    obj = T(args...)
    try
        with(f, obj)
    catch err
        warn("$(string(T)) thrown exception: $err")
    end
end

function getobjecttype{T<:GitObject}(::Type{T})
    return if T == GitCommit
        Consts.OBJ_COMMIT
    elseif T == GitTree
        Consts.OBJ_TREE
    elseif T == GitBlob
        Consts.OBJ_BLOB
    elseif T == GitTag
        Consts.OBJ_TAG
    elseif T == GitAnyObject
        Consts.OBJ_ANY
    else
        throw(GitError(Error.Object, Error.ENOTFOUND, "Type $T is not supported"))
    end
end

function getobjecttype(obj_type::Cint)
    return if obj_type == Consts.OBJ_COMMIT
        GitCommit
    elseif obj_type == Consts.OBJ_TREE
        GitTree
    elseif obj_type == Consts.OBJ_BLOB
        GitBlob
    elseif obj_type == Consts.OBJ_TAG
        GitTag
    elseif obj_type == Consts.OBJ_ANY
        GitAnyObject
    else
        throw(GitError(Error.Object, Error.ENOTFOUND, "Object type $obj_type is not supported"))
    end
end

import Base.securezero!

"Credentials that support only `user` and `password` parameters"
type UserPasswordCredentials <: AbstractCredentials
    user::String
    pass::String
    prompt_if_incorrect::Bool    # Whether to allow interactive prompting if the credentials are incorrect
    count::Int                   # authentication failure protection count
    function UserPasswordCredentials(u::AbstractString,p::AbstractString,prompt_if_incorrect::Bool=false)
        c = new(u,p,prompt_if_incorrect,3)
        finalizer(c, securezero!)
        return c
    end
    UserPasswordCredentials(prompt_if_incorrect::Bool=false) = UserPasswordCredentials("","",prompt_if_incorrect)
end

function securezero!(cred::UserPasswordCredentials)
    securezero!(cred.user)
    securezero!(cred.pass)
    cred.count = 0
    return cred
end

"SSH credentials type"
type SSHCredentials <: AbstractCredentials
    user::String
    pass::String
    pubkey::String
    prvkey::String
    usesshagent::String  # used for ssh-agent authentication
    prompt_if_incorrect::Bool    # Whether to allow interactive prompting if the credentials are incorrect
    count::Int

    function SSHCredentials(u::AbstractString,p::AbstractString,prompt_if_incorrect::Bool=false)
        c = new(u,p,"","","Y",prompt_if_incorrect,3)
        finalizer(c, securezero!)
        return c
    end
    SSHCredentials(prompt_if_incorrect::Bool=false) = SSHCredentials("","",prompt_if_incorrect)
end
function securezero!(cred::SSHCredentials)
    securezero!(cred.user)
    securezero!(cred.pass)
    securezero!(cred.pubkey)
    securezero!(cred.prvkey)
    cred.count = 0
    return cred
end

"Credentials that support caching"
type CachedCredentials <: AbstractCredentials
    cred::Dict{String,AbstractCredentials}
    count::Int            # authentication failure protection count
    CachedCredentials() = new(Dict{String,AbstractCredentials}(),3)
end

"Checks if credentials were used or failed authentication, see `LibGit2.credentials_callback`"
function checkused!(p::Union{UserPasswordCredentials, SSHCredentials})
    p.count <= 0 && return true
    p.count -= 1
    return false
end
reset!(p::Union{UserPasswordCredentials, SSHCredentials}, cnt::Int=3) = (p.count = cnt; p)
reset!(p::CachedCredentials) = (foreach(reset!, values(p.cred)); p)

"Obtain the cached credentials for the given host+protocol (credid), or return and store the default if not found"
get_creds!(collection::CachedCredentials, credid, default) = get!(collection.cred, credid, default)
get_creds!(creds::AbstractCredentials, credid, default) = creds
get_creds!(creds::Void, credid, default) = default
function get_creds!(creds::Ref{Nullable{AbstractCredentials}}, credid, default)
    if isnull(creds[])
        creds[] = Nullable{AbstractCredentials}(default)
        return default
    else
        get_creds!(Base.get(creds[]), credid, default)
    end
end

function securezero!(p::CachedCredentials)
    foreach(securezero!, values(p.cred))
    return p
end

max_stars_repo_name: habemus-papadum/julia

max_issues_repo_name: habemus-papadum/julia

max_forks_repo_name: habemus-papadum/julia


text:
# Module with different test cases to simulate with the Main_1dSim.jl script.

module TestCases
export three_points_1d, two_points_1d, three_points_2d, two_points_2d, random_point_cloud, cloud_1d, cloud_1d_full
function three_points_1d(x_max, dx, dv)
    pts = [0.5*x_max-0.5*dx, 0.5*x_max, 0.5*x_max + 0.5*dx]
    weights = [1.0; 1.0; 1.0]
    velocities = [0.0 ; dv; 0.0]
    thetas = [pts'; velocities']
    return (thetas, weights)
end
function two_points_1d(x_max, dx, dv)
    pts = [0.5*x_max - 0.5*dx, 0.5*x_max + 0.5 * dx]
    weights = [0.5, 0.5]
    velocities = [-dv/2, dv/2]
    thetas = [pts'; velocities']
    return (thetas, weights)
end
function three_points_2d(x_max, dx, dv, direction="x")
    eps = dx / 10
    pts_x = [0.5*x_max-0.5*dx, 0.5*x_max, 0.5*x_max + 0.5*dx]
    pts_y = [0.5*x_max, 0.5*x_max, 0.5*x_max]
    weights = [1.0; 1.0; 1.0]
    velocities_x = [0.0 ; dv; 0.0]
    velocities_y = [0.0 ; 0.0; 0.0]
    if direction == "x"
        thetas = [pts_x'; pts_y'; velocities_x'; velocities_y']
    else
        thetas = [pts_y'; pts_x'; velocities_y'; velocities_x']
    end
    return (thetas, weights)
end
function two_points_2d(x_max, dx, dv)
    pts_x = [0.5*x_max - 0.5*dx, 0.5*x_max + 0.5 * dx]
    pts_y = [0.5*x_max, 0.5*x_max]
    weights = [1.0, 1.0]
    velocities_x = [-dv/2 ; dv/2]
    velocities_y = [0.0 ; 0.0]
    thetas = [pts_x'; pts_y'; velocities_x'; velocities_y']
    return (thetas, weights)
end
function random_point_cloud(dx)
    pts = dx + (1.0-3*dx)*rand()
    pts = [0.0; pts; pts+dx; 1.0]
    is_valid = (pt, pts) -> pt > dx &&
    pt < 1-dx &&
    minimum(abs(pts[2:end-1] - pt)) > dx
    while maximum(mod(pts - circshift(pts, 1), 1.0)) > 2*dx
        new_pt = rand()
        while !is_valid(new_pt, pts)
            new_pt = rand()
        end
        pts = sort([pts; new_pt])
    end
    return pts[2:end-1]
end
function random_position_and_velocity(dx, dv)
    pts = dx + (1.0 - 2*dx) * rand()
    velocities = (1.0 - dv) * rand()
    velocities = velocities
    is_valid = (pt, vel, pts, vels) -> pt > dx &&
    pt < 1-dx &&
    (minimum(abs(pts - pt)) > dx ||
     minimum(abs(vels - vel)) > dv)
    while((maximum([abs(v1-v2) for v1 in velocities, v2 in velocities]) > 2*dv &&
           maximum([abs(x1-x2) for x1 in pts, x2 in pts]) > 2*dx) || length(velocities) == 1)
        new_pt = rand()
        new_vel = rand()
        iter = 0
        notFound = false;
        while !is_valid(new_pt, new_vel, pts, velocities)
            new_pt = rand()
            new_vel = rand()
            iter = iter + 1
            if (iter > 100)
                notFound = true;
                break;
            end
        end
        if (notFound)
            break;
        end
        pts = [pts; new_pt]
        velocities = [velocities; new_vel]
        if (length(pts) > 10)
            break;
        end
    end
    return (pts, velocities)
end
function cloud_1d(x_max, v_max, dx, dv)
    (pts, velocities) = random_position_and_velocity(dx/x_max, dv/(2*v_max))
    weights = ones(size(pts))
    thetas = [x_max * pts'; v_max - 2*v_max*velocities']
    return (thetas, weights)
end
function cloud_1d(x_max, v_max, n)
    pts = x_max * rand(n)
    velocities =  v_max - 2*v_max*rand(n)
    thetas = [pts'; velocities']
    weights = ones(size(pts))
    return (thetas, weights)
end
function cloud_1d_full(x_max,v_max,K,tau,n)
# We generate random particles, uniform on the rectangle [0,x_max]x[-v_max,v_max]
# under the condition of belonging to the set Omega.
    pts = rand(0)
    velocities = rand(0)
    while size(pts)[1]<n
	newPts = rand()*x_max
	newVel = (rand()-0.5)*2*v_max
	if newPts + K*tau*abs(newVel) <= x_max && newPts - K*tau*abs(newVel) >= 0
	   push!(pts,newPts)
	   push!(velocities,newVel)
	end
    end
    thetas = [pts'; velocities']
    weights = ones(size(pts))
    return (thetas, weights)
end
function cloud_1d_full(x_max,v_max,w_min,w_max,K,tau,n)
# As before, with random weights.
    pts = rand(0)
    velocities = rand(0)
    while size(pts)[1]<n
	newPts = rand()*x_max
	newVel = (rand()-0.5)*2*v_max
	if newPts + K*tau*abs(newVel) <= x_max && newPts - K*tau*abs(newVel) >= 0
	   push!(pts,newPts)
	   push!(velocities,newVel)
	end
    end
    thetas = [pts'; velocities']
    weights = w_min + rand(size(pts))*(w_max-w_min)
    return (thetas, weights)
end
function two_groups_1d(x_max, dx, dv)
    pts_1 = x_max * random_point_cloud(dx/x_max)
    pts_2 = x_max * random_point_cloud(dx/x_max)
    pts = [pts_1; pts_2]
    velocities = [-dv/2*ones(size(pts_1)); dv/2*ones(size(pts_2))]
    weights = ones(size(pts))
    thetas = [pts'; velocities']
    return (thetas, weights)
end
function two_groups_2d(x_max, dx, dy, dv)
    pts_1 = x_max * random_point_cloud(dx/x_max)
    pts_2 = x_max * random_point_cloud(dx/x_max)
    pts_x = [pts_1; pts_2]
    pts_y = [0.5*x_max * ones(size(pts_1)) + dy/2; 0.5*x_max * ones(size(pts_2)) - dy/2]
    velocities_y = [zeros(size(pts_1)); zeros(size(pts_2))]
    velocities_x = [-dv/2*ones(size(pts_1)); dv/2*ones(size(pts_2))]
    weights = ones(size(pts_x))
    thetas = [pts_x'; pts_y'; velocities_x'; velocities_y']
    return (thetas, weights)
end
function aligned_1d(x_max, dx, n)
    pts = dx * (1:n)
    velocities = zeros(size(pts))
    thetas = [pts'; velocities']
    weights = ones(size(pts))
    return (thetas, weights)
end
end


text:
@testset "477.total-hamming-distance.jl" begin
    @test total_hamming_distance([4, 14, 2]) == 6
    @test total_hamming_distance([4, 14, 4]) == 4
end


text:
module Shoot_module
    include("load2_module.jl")
    using .Load2_module

    mutable struct Shoot_module_variables
        dx::Float64
        eps::Float64
        grid_num::Int64
        usethread::Bool
        v0::Float64
        vmax::Float64
        xmin::Float64
        xf::Float64
        xmax::Float64
        load2_param::Load2_module.Load2_module_param
        load2_val::Load2_module.Load2_module_variables
    end
end


text:
#!/usr/bin/env julia --color=yes

using ArgParse

using JLD
using Multilane
using POMDPs
using MCTS
using DataFrames
using DataFramesMeta
using Plots
using StatPlots

exception = nothing

s = ArgParseSettings()

@add_arg_table s begin
    "--show", "-s"
        help = "show results; print stats and solvers"
        action = :store_true
    "--unicode", "-u"
        help = "show unicode plot"
        action = :store_true
    "--plot", "-p"
        help = "plot paretto curves"
        action = :store_true
    "--spreadsheet"
        help = "[NOT IMPLEMENTED] save stats as a csv in /tmp/ and open with xdg-open"
        action = :store_true
    "filename"
        help = "file name"
        nargs = '*'
    "--solvers"
        help = "solvers to be included"
        nargs = '+'
    "--tests"
        help = "tests to be included"
        nargs = '+'
    "--save-combined"
        help = "save results to a new file"
        action = :store_true
    "--check-crashes"
        help = "print out simulations that have crashes"
        action = :store_true
    "--list", "-l"
        help = "list note and test keys"
        action = :store_true
end

args = parse_args(ARGS, s)

if length(args["filename"]) > 0
    filename = first(args["filename"])
else
    files = readdir(".")
    latest = 0.0
    latest_file = ""
    for f in files
        if ctime(f) > latest
            latest = ctime(f)
            latest_file = f
        end
    end
    println("loading from most recent file: $latest_file")
    filename = latest_file
end

results = load(filename)

if args["list"]
    println("$filename note:")
    println(get(results, "note", "<none>"))
end

for f in args["filename"][2:end]
    new_results = load(f)
    try
        results = merge_results!(results, new_results)
    catch ex
        warn("Careful merge of data failed, there may be inconsistent data")
        results = merge_results!(results, new_results, careful=false)
    end
    if args["list"]
        println("$filename note:")
        println(get(results, "note", "<none>"))
    end
end

stats = results["stats"]

mean_performance = by(stats, [:solver_key, :lambda, :problem_key, :solver_problem_key, :test_key]) do df
    DataFrame(steps_in_lane=mean(df[:steps_in_lane]),
              nb_brakes=mean(df[:nb_brakes]),
              time_to_lane=mean(df[:time_to_lane]),
              steps=mean(df[:steps]),
              )
end

solvers = args["solvers"]
if isempty(solvers)
    solvers = unique(mean_performance[:solver_key])
end
tests = args["tests"]
if isempty(tests)
    tests = unique(mean_performance[:test_key])
end

if args["list"]
    println()
    println("Avaialable Tests:")
    for t in unique(mean_performance[:test_key])
        println(t)
    end
    println()
end

mean_performance = @where(mean_performance,
                          collect(Bool[s in solvers for s in :solver_key]))
mean_performance = @where(mean_performance,
                          collect(Bool[t in tests for t in :test_key]))

# @show mean_performance

mean_performance[:brakes_per_sec] = mean_performance[:nb_brakes]./mean_performance[:time_to_lane]

if args["show"]
    println(mean_performance)
    println()
    println(results["param_table"])
end

if args["unicode"] || args["plot"]
    try
        if args["unicode"]
            unicodeplots()
        else
            pyplot()
            # plotlyjs()
            # pgfplots()
        end
        if haskey(results, "tests")
            for g in groupby(mean_performance, :test_key)
                if size(g,1) > 1
                    plot!(g, :time_to_lane, :nb_brakes, group=:test_key)
                else
                    scatter!(g, :time_to_lane, :nb_brakes, group=:test_key)
                end
            end
            gui()
        else # old way, before test sets
            for g in groupby(mean_performance, :solver_key)
                if size(g,1) > 1
                    plot!(g, :time_to_lane, :nb_brakes, group=:solver_key)
                else
                    scatter!(g, :time_to_lane, :nb_brakes, group=:solver_key)
                end
            end
            gui()
        end
    catch ex
        warn("Plot could not be displayed:")
        println(ex)
        exception = ex
        # rethrow(ex)
    end
end

if args["save-combined"]
    filename = string("combined_", Dates.format(Dates.now(),"u_d_HH_MM"), ".jld")
    save(filename, results)
    println("combined results saved to $filename")
end

if nothing !== (exception)
    rethrow(exception)
end


text:
using StatsBase                 # just for sample()
using AssociationRules
# testing a-priori algorithm
transactions = [sample(1:10, 5, replace = false) for x in 1:100_000]
fk = frequent(transactions, 0.1)

groceries = ["milk", "bread", "eggs", "apples", "oranges", "beer"]
transactions = [sample(groceries, 4, replace = false) for x in 1:1000]
fk = frequent(transactions, 0.1)

rules1 = apriori(transactions, 0.1, 0.4, false);        # false for only single-item consequents
display(rules1)

# reading data from .csv
adult_data = readcsv("../data/adult.csv", skipstart = 1)
adult_trans = make_transactions(adult_data[1:1000, :])  # take only sub-set of data for convenience
rules2 = apriori(adult_trans, 0.2, 0.8)
display(rules2)

# testing SPADE algorithm
zaki_data = readcsv("../data/zaki_data.csv", skipstart = 1)
seqs = make_sequences(zaki_data, sid_col = 2, eid_col = 3, item_col = 1)
@time res = spade(seqs, 0.2, 20);

@assert length(res[1]) == 8
@assert length(res[2]) == 57
@assert length(res[3]) == 191
@assert length(res[4]) == 444
@assert length(res[5]) == 743
@assert length(res[6]) == 897
@assert length(res[7]) == 784

# testing SPADE algorithm with subset of Zaki data
zaki_data = readcsv("../data/zaki_subset_data.csv", skipstart = 1)
seqs2 = make_sequences(zaki_data, sid_col = 2, eid_col = 3, item_col = 1)
@time res2 = spade(seqs2, 0.2, 6);


text:
__precompile__()

module FEFunctions

###################
# Utility functions

export scalartype

scalartype(::Type{Any}) = throw(MethodError(scalartype, (Any,)))
scalartype(t::DataType) = scalartype(super(t))
scalartype(x) = scalartype(typeof(x))
scalartype{T <: Number}(::Type{T}) = T

###############
# Vec functions

using FixedSizeArrays
scalartype{D,T}(::Type{Vec{D,T}}) = T
mattype{D,T}(::Type{Vec{D,T}}) = Mat{D,D,T}
mattype{T <: Number}(::Type{T}) = T

############
# FEFunction

export FEFunction, nshape, shape, index, func, sample

abstract FEFunction{T}

macro defineFEFunctionType(name, nloc)
    esc(quote
        export $name
        type $name{T} <: FEFunction{T}
            data::Vector{T}
        end

        $name(T::Type, n::Int) = $name(Array{T}($nloc*n))
        $name(args...) = $name(Float64,args...)

        Base.length(u::$name) = div(length(u.data),$nloc)
        index(u::$name, i, s) = mod1($nloc*(i-1)+s,length(u.data))
    end)
end

scalartype{T}(::Type{FEFunction{T}}) = scalartype(T)
Base.eltype{T}(::Type{FEFunction{T}}) = T

Base.vec(u::FEFunction) = reinterpret(scalartype(u), u.data)
func{F <: FEFunction}(::Type{F}, data) = F(reinterpret(eltype(F), data))
func{F <: FEFunction}(::F, data) = func(F,data)

nshape{T <: FEFunction}(::Type{T}) = throw(MethodError(nshape, (T,)))
nshape(x::FEFunction) = nshape(typeof(x))

shape{T <: FEFunction}(::Type{T},args...) = throw(MethodError(shape, (T,args...)))
shape{T <: FEFunction}(::Type{T},s,p) = shape(T,s,p,Val{0})
shape(x::FEFunction,args...) = shape(typeof(x),args...)

Base.getindex(u::FEFunction, i::Int, s::Int) = @inbounds return u.data[index(u,i,s)]
Base.setindex!(u::FEFunction, ui, i::Int, s::Int) = @inbounds u.data[index(u,i,s)] = ui

function Base.getindex{D}(u::FEFunction, i::Int, p, ::Type{Val{D}})
    uip = zero(eltype(u))
    for s = 1:nshape(u)
        uip .+= u[i,s]*shape(u,s,p,Val{D})
    end
    return uip
end
Base.getindex(u::FEFunction, i::Int, p) = u[i,p,Val{0}]

function sample{D}(u::FEFunction, n::Int, ::Type{Val{D}})
    P = linspace(0,1,n+1)[1:end-1]
    v = LinearFEFunction(eltype(u), length(u)*n)
    for i = 1:length(u)
        for (ip,p) = enumerate(P)
            v[n*(i-1) + ip] = u[i,p,Val{D}]
        end
    end
    return v
end
sample(u::FEFunction, n::Int) = sample(u,n,Val{0})

##################
# LinearFEFunction

@defineFEFunctionType(LinearFEFunction,1)

function LinearFEFunction(T, f, P)
    u = LinearFEFunction(T,length(P)-1)
    for (i,p) = enumerate(P[1:end-1])
        u[i] = f(p)
    end
    return u
end

nshape{T}(::Type{LinearFEFunction{T}}) = 2
function shape{T}(::Type{LinearFEFunction{T}}, s::Int, p, ::Type{Val{0}})
    if s == 1
        return 1 - p
    else
        return p
    end
end
function shape{T}(::Type{LinearFEFunction{T}}, s::Int, p, ::Type{Val{1}})
    if s == 1
        return -one(p)
    else
        return one(p)
    end
end

Base.getindex(x::LinearFEFunction, i::Int) = x[i,1]
Base.setindex!(x::LinearFEFunction, xi, i::Int) = x[i,1] = xi

##################
# CubicFEFunction

@defineFEFunctionType(CubicFEFunction,3)

function CubicFEFunction(T, f, P)
    u = CubicFEFunction(T,length(P)-1)
    for i = 1:length(P)-1
        for (j,p) = enumerate(linspace(P[i],P[i+1],4)[1:end-1])
            u[i,j] = f(p)
        end
    end
    return u
end

nshape{T}(::Type{CubicFEFunction{T}}) = 4
function shape{T}(::Type{CubicFEFunction{T}}, s::Int, p, ::Type{Val{0}})
    if s == 1
        return -9/2*(p-1/3)*(p-2/3)*(p-1)
    elseif s == 2
        return 27/2*p*(p-2/3)*(p-1)
    elseif s == 3
        return -27/2*p*(p-1/3)*(p-1)
    elseif s == 4
        return 9/2*p*(p-1/3)*(p-2/3)
    else
        return convert(typeof(p), NaN)
    end
end
function shape{T}(::Type{CubicFEFunction{T}}, s::Int, p, ::Type{Val{1}})
    if s == 1
        return -9/2*((p-2/3)*(p-1) + (p-1/3)*(p-1) + (p-1/3)*(p-2/3))
    elseif s == 2
        return 27/2*((p-2/3)*(p-1) + p*(p-1) + p*(p-2/3))
    elseif s == 3
        return -27/2*((p-1/3)*(p-1) + p*(p-1) + p*(p-1/3))
    elseif s == 4
        return 9/2*((p-1/3)*(p-2/3) + p*(p-2/3) + p*(p-1/3))
    else
        return convert(typeof(p), NaN)
    end
end

###################
# HermiteFEFunction

@defineFEFunctionType(HermiteFEFunction,2)

function HermiteFEFunction(T::DataType, f, df, P)
    fac = (P[end]-P[1])/(length(P)-1)
    u = HermiteFEFunction(T,length(P)-1)
    for (i,p) = enumerate(P[1:end-1])
        u[i,1] = f(p)
        u[i,2] = fac*df(p)
    end
    return u
end

using ForwardDiff
function HermiteFEFunction(T::DataType, f, P)
    fac = (P[end]-P[1])/(length(P)-1)
    u = HermiteFEFunction(T,length(P)-1)
    for (i,p) = enumerate(P[1:end-1])
        _,fp = derivative(f,p,AllResults)
        u[i,1] = value(fp)
        u[i,2] = fac*derivative(fp)
    end
    return u
end

nshape{T}(::Type{HermiteFEFunction{T}}) = 4
  hermite_f(p) = 3*p.^2 - 2*p.^3
  hermite_df(p) = p.^3 - p.^2
 dhermite_f(p) = 6*p - 6*p.^2
 dhermite_df(p) = 3*p.^2 - 2*p
ddhermite_f(p) = 6 - 12*p
ddhermite_df(p) = 6*p - 2
function shape{T}(::Type{HermiteFEFunction{T}}, s::Int, p, ::Type{Val{0}})
    if s == 1
        return hermite_f(1-p)
    elseif s == 2
        return -hermite_df(1-p)
    elseif s == 3
        return hermite_f(p)
    elseif s == 4
        return hermite_df(p)
    else
        return convert(typeof(p), NaN)
    end
end
function shape{T}(::Type{HermiteFEFunction{T}}, s::Int, p, ::Type{Val{1}})
    if s == 1
        return -dhermite_f(1-p)
    elseif s == 2
        return dhermite_df(1-p)
    elseif s == 3
        return dhermite_f(p)
    elseif s == 4
        return dhermite_df(p)
    else
        return convert(typeof(p), NaN)
    end
end
function shape{T}(::Type{HermiteFEFunction{T}}, s::Int, p, ::Type{Val{2}})
    if s == 1
        return ddhermite_f(1-p)
    elseif s == 2
        return -ddhermite_df(1-p)
    elseif s == 3
        return ddhermite_f(p)
    elseif s == 4
        return ddhermite_df(p)
    else
        return convert(typeof(p), NaN)
    end
end

####################
# Assembly functions

using FastGaussQuadrature

export @assemble_mat
macro assemble_mat(u, nq, preproc, expr)
    return quote
        u = $(esc(u))

        (P,W) = gausslegendre($(esc(nq)))
        P = 0.5*(P+1); W /= 2

        d = div(sizeof(eltype(u)),sizeof(scalartype(u)))
        N = d^2*nshape(u)^2
        I = Array{Int}(length(u)*N)
        J = Array{Int}(length(u)*N)
        V = Array{scalartype(u)}(length(u)*N)
        for i = 1:length(u)
            Mloc = zeros(mattype(eltype(u)),nshape(u),nshape(u))
            for (p,w) = zip(P,W)
                $(esc(:i)) = i
                $(esc(:p)) = p
                $(esc(preproc))

                for s = 1:nshape(u)
                    for ss = 1:nshape(u)
                        $(esc(:s)) = s
                        $(esc(:ss)) = ss
                        Mloc[ss,s] .+= w*$(esc(expr))
                    end
                end
            end

            for s = 1:nshape(u)
                sidx = index(u,i,s)
                for ss = 1:nshape(u)
                    ssidx = index(u,i,ss)

                    for id = 1:d
                        I[N*(i-1)+d^2*nshape(u)*(s-1)+d^2*(ss-1)+d*(id-1)+(1:d)] = d*(ssidx-1) + (1:d)
                        J[N*(i-1)+d^2*nshape(u)*(s-1)+d^2*(ss-1)+d*(id-1)+(1:d)] = d*( sidx-1) + id
                    end
                end
            end
            V[N*(i-1)+(1:N)] = reinterpret(scalartype(u),Mloc, (N,))
        end
        sparse(I,J,V)
    end
end

export @assemble_vec
macro assemble_vec(u, nq, preproc, expr)
    return quote
        u = $(esc(u))

        (P,W) = gausslegendre($(esc(nq)))
        P = 0.5*(P+1); W /= 2

        b = typeof(u)(zeros(u.data))
        for i = 1:length(u)
            for (p,w) = zip(P,W)
                $(esc(:i)) = i
                $(esc(:p)) = p
                $(esc(preproc))

                for s = 1:nshape(u)
                    $(esc(:s)) = s
                    b[i,s] += w*$(esc(expr))
                end
            end
        end
        vec(b)
    end
end

end

max_stars_repo_name: ettersi/CellMotility

max_issues_repo_name: ettersi/CellMotility

max_forks_repo_name: ettersi/CellMotility


text:
abstract type AbstractModel end

mutable struct Data
    Fs::Array{Float64, 1} # Fs = [ f(x) for x in X ]
    # X is a N×D matrix, that contains N row vectors in R^D
    Xs::Array{Float64, 2}
end

function Data(;Fs::Array{Float64, 1}=[], Xs::Array=Array{Float64, 2}[])

    sz = size(Xs)
    if length(sz) == 1
        return Data(reshape(Xs, sz[1], 1), Array{Float64, 1}(Fs))
    elseif length(sz) == 2
        return Data(reshape(Xs, sz[1], 1), Array{Float64, 1}(Fs))
    else
        @error "Xs shoud be a 2D Matrix and Fs a vector"
    end

    return nothing

end

function Data(F::Function, Xs::Array{Float64, 2})
    Fs = Float64[ F(Xs[i,:]) for i=1:size(Xs,1) ]
    Data(Fs, Xs)
end

function Data(F::Function, Xs::Array{Float64, 1})
    Fs = Float64[ F(Xs[i]) for i=1:length(Xs) ]
    Xs = reshape(Xs, length(Xs), 1)
    Data(Fs, Xs)
end

mutable struct KernelInterpolation <: AbstractModel
    kernel::Kernel
    kernelMatrix::Matrix{Float64}
    kernelMatrixInv::Matrix{Float64}
    trainingData::Data
    coeffs::Array{Float64}
    λ::Float64
end

function KernelInterpolation(trainingData::Data;kernel::Kernel = GaussianKernel(1.0), coeffs::Array = Array[], λ::Float64=0.0)
    KernelInterpolation(kernel, zeros(0,0), zeros(0,0), trainingData, coeffs, λ)
end

function KernelInterpolation(Fs, Xs; kernel::Kernel = GaussianKernel(1.0), coeffs::Array = Array[], λ::Float64=0.0)
    KernelInterpolation(kernel, zeros(0,0), zeros(0,0), Data(Array(Fs), Array(Xs)), coeffs, λ)
end

function KernelInterpolation(F::Function, Xs ;kernel::Kernel = GaussianKernel(1.0), coeffs::Array = Array[], λ::Float64=0.0)
    KernelInterpolation(kernel, zeros(0,0), zeros(0,0), Data(F, Array(Xs)), coeffs, λ)
end


text:
"""
* `g` : input gradients w.r.t. KI and rhoI
* `gout` : output gradients according to parameterization
"""
function chainrule!(gout::AbstractVector, g::AbstractVector, mod::Medium, parameterization)
	nznx=prod(length.(mod.mgrid))
	(length(gout)≠(count(parameterization.≠ :null)*nznx)) &&  error("size x")

	rho=mod[:rho];
	vp=mod[:vp];
	# vs=mod[:vs]; # not implemented

	if(parameterization == [:χKI, :χrhoI, :null])
		@inbounds for i in 1:nznx
			gout[i]=χg(g[i],mod.ref[:KI],1)
			gout[nznx+i]=χg(g[nznx+i],mod.ref[:rhoI],1)
		end
	elseif(parameterization == [:χKI, :null, :null])
		@inbounds for i in 1:nznx
			gout[i]=χg(g[i],mod.ref[:KI],1)
		end
	elseif(parameterization == [:χvp, :χrho, :null])
		@inbounds for i in 1:nznx
			# derivative w.r.t vp
			gout[i]= χg(grad_of_vp(g[i], vp[i], rho[i]), mod.ref[:vp],1)
			# derivative w.r.t. rho
			gout[nznx+i]=χg(grad_of_rho(g[i],g[nznx+i],vp[i],rho[i]), mod.ref[:rho],1)
		end
	elseif(parameterization == [:χvp, :null, :null])
		@inbounds for i in 1:nznx
			gout[i]= χg(grad_of_vp(g[i], vp[i], rho[i]), mod.ref[:vp],1)
		end
	elseif(parameterization == [:null, :χrho, :null])
		@inbounds for i in 1:nznx
			gout[i]=χg(grad_of_rho(g[i],vp[i],rho[i]), mod.ref[:rho],1)
		end
	end

end

grad_of_vp(gKI, vp, rho) = -2.0 * gKI * inv(vp*vp*vp*rho)
grad_of_rho(gKI, grhoI, vp, rho) = -1.0 * inv(abs2(rho)) * (inv(vp*vp)*gKI + grhoI)
grad_of_rho(grhoI, vp, rho) = -1.0 * inv(abs2(rho)) * (grhoI)

"""
No different from the previous case, but...
"""
function pert_chainrule!(gout::AbstractVector, g::AbstractVector, mod::Medium, parameterization)
	nznx=prod(length.(mod.mgrid))
	(length(gout)≠(count(parameterization.≠ :null)*nznx)) &&  error("size x")
	fill!(gout, 0.0)
	if(parameterization == [:χKI, :χrhoI, :null])
		@inbounds for i in 1:nznx
			gout[i]=g[i]*mod.ref[:KI]
			gout[nznx+i]=g[nznx+i]*mod.ref[:rhoI]
		end
	elseif(parameterization == [:χKI, :null, :null])
		@inbounds for i in 1:nznx
			gout[i]=χg(g[i],mod.ref[:KI],1)
		end
	elseif(parameterization == [:χvp, :χrho, :null])
		@inbounds for i in 1:nznx
			# derivative w.r.t vp
			gout[i]= -2.0*mod.ref[:KI]*g[i]
			# derivative w.r.t. rho
			gout[nznx+i]=-1.0*mod.ref[:KI]*g[i]-1.0*mod.ref[:rhoI]*g[nznx+i]
		end
	elseif(parameterization == [:χvp, :null, :null])
		@inbounds for i in 1:nznx
			gout[i]=-2.0*mod.ref[:KI]*g[i]
		end
	elseif(parameterization == [:null, :χrho, :null])
		@inbounds for i in 1:nznx
			gout[i]=-1.0*mod.ref[:rhoI]*g[i]
		end
	end
end

"""
Use chain rule to output gradients with
respect to χvp and χrho from  gradients
with respect to KI and rhoI.

# Arguments

* `gmod::Seismic` : gradient model
* `mod::Seismic` : model required for chain rule
* `g1` : gradient of an objective function with respect `attribs[1]`
* `g2` : gradient of an objective function with respect `attribs[2]`
* `attribs::Vector{Symbol}=[:χKI, :χrhoI]` :
* `flag::Int64=1` :
  * `=1` updates `gmod` using `g1` and `g2`
  * `=-1` updates `g1` and `g2` using `gmod`
"""
function chainrule!(
		      gmod::Medium,
		      mod::Medium,
		      g,
		      attribvec::Vector{Symbol}=[:χKI, :χrhoI, :null],
		      flag::Int64=1
		      )

	nznx=prod(length.(mod.mgrid))
	(length(g)≠(count(attribvec.≠ :null)*nznx)) &&  error("size x")

	rho=mod[:rho]; vp=mod[:vp];
	# vs=mod[:vs];
	if(flag == 1)
		if(attribvec == [:χKI, :χrhoI, :null])
			@inbounds for i in 1:nznx
				g[i]=χg(g[i],mod.ref[:KI],-1)
				g[nznx+i]=χg(g[nznx+i],mod.ref[:rhoI],-1)
				# gradient w.r.t  χrho
				gmod.m[:χrho][i]= -1.0*abs2(inv(rho[i]))*g[nznx+i]-inv(vp[i]*vp[i]*rho[i]*rho[i])*g[i]
				# gradient w.r.t χvp
				gmod.m[:χvp][i] = -2.0*inv(vp[i]*vp[i]*vp[i])*inv(rho[i])*g[i]
				g[i]=χg(g[i],mod.ref[:KI],1)
				g[nznx+i]=χg(g[nznx+i],mod.ref[:rhoI],1)
			end
			χg!(gmod.m[:χrho],mod.ref[:rho],1)
			χg!(gmod.m[:χvp],mod.ref[:vp],1)
		elseif(attribvec == [:χKI, :null, :null])
			@inbounds for i in 1:nznx
				g[i]=χg(g[i],mod.ref[:KI],-1)
				# gradient w.r.t χvp
				gmod.m[:χvp][i] = -2.0*inv(vp[i]*vp[i]*vp[i])*inv(rho[i])*g[i]
				g[i]=χg(g[i],mod.ref[:KI],1)
			end
			χg!(gmod.m[:χvp],mod.ref[:vp],1)

		elseif(attribvec == [:χvp, :χrho, :null])
			@inbounds for i in 1:nznx; gmod.m[:χvp][i]=g[i]; end
			@inbounds for i in 1:nznx; gmod.m[:χrho][i]=g[nznx+i]; end
		elseif(attribvec == [:null, :χrho, :null])
			@inbounds for i in 1:nznx; gmod.m[:χrho][i]=g[i]; end
		elseif(attribvec == [:χvp, :null, :null])
			@inbounds for i in 1:nznx; gmod.m[:χvp][i]=g[i]; end
		else
			error("invalid attribs")
		end
	elseif(flag == -1)
		if(attribvec == [:χKI, :χrhoI, :null])
			χg!(gmod.m[:χvp], mod.ref[:vp], -1) # undo it later
			χg!(gmod.m[:χrho], mod.ref[:rho], -1) # undo it later
			gvp = gmod.m[:χvp]
			grho = gmod.m[:χrho]
			@inbounds for i in 1:nznx
				g[i] = -0.5 * mod.ref[:KI] * gvp[i] * rho[i] *  vp[i]^3
			end
			@inbounds for i in 1:nznx
				g[nznx+i] = (grho[i] * mod.ref[:rhoI] * -1. * rho[i]*rho[i]) +
				(0.5 * mod.ref[:rhoI] .* gvp[i] .*  vp[i] .* rho[i])
			end
			χg!(gvp,mod.ref[:vp],1)
			χg!(grho,mod.ref[:rho],1)
		elseif(attribvec == [:χKI, :null, :null])
			χg!(gmod.m[:χvp], mod.ref[:vp], -1) # undo it later
			gvp = gmod.m[:χvp]
			@inbounds for i in 1:nznx
				g[i] = -0.5 * mod.ref[:KI] * gvp[i] * rho[i] *  vp[i]^3
			end
			χg!(gvp,mod.ref[:vp],1)
		elseif(attribvec == [:χvp, :χrho, :null])
			@inbounds for i in 1:nznx
				g[i] = gmod.m[:χvp][i]
				g[nznx+i] = gmod.m[:χrho][i]
			end
		elseif(attribvec == [:χvp, :null, :null])
			@inbounds for i in 1:nznx
				g[i] = gmod.m[:χvp][i]
			end
		elseif(attribvec == [:null, :χrho, :null])
			@inbounds for i in 1:nznx
				g[i] = gmod.m[:χrho][i]
			end
		else
			error("invalid attribs")
		end
	else
		error("invalid flag")
	end
end


text:
module MergeSorted

import Base.Order: Ordering, Forward, ord, lt
export mergesorted, mergesorted!

# merge sorted vectors vl and vr into v
# from indices lo to hi in v
function mergesorted!(v::AbstractVector,
                      lo::Int, hi::Int,
                      vl::AbstractVector,
                      lol::Int, hil::Int,
                      vr::AbstractVector,
                      lor::Int, hir::Int,
                      order::Ordering)
    c = lol
    p = lor
    nl = hil
    nr = hir
    i = lo
    @inbounds while c <= nl && p <= nr && i <= hi
        if lt(order, vr[p], vl[c])
            v[i] = vr[p]
            p = p+1
            i = i+1
        else
            v[i] = vl[c]
            c = c+1
            i = i+1
        end
    end
    @inbounds while p <= nr && i <= hi
        v[i] = vr[p]
        i = i+1
        p = p+1
    end
    @inbounds while c <= nl && i <= hi
        v[i] = vl[c]
        i = i+1
        c = c+1
    end
    v
end

function mergesorted!(v::AbstractVector, vl::AbstractVector,
                      vr::AbstractVector, order::Ordering)
    inds = eachindex(v)
    indsl = eachindex(vl)
    indsr = eachindex(vr)
    mergesorted!(v,first(inds),last(inds),vl,first(indsl),last(indsl),
                 vr,first(indsr),last(indsr),order)
end

"""
    mergesorted!(v, vl, vr; lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward)

Merge sorted vectors `vl` and `vr`, overwriting vector `v`, in linear time. Assumes
that `vl` and `vr` are sorted and does not check whether `vl` or `vr`
are sorted. You could used `issorted` to check if `vl` and `vr` are sorted.
If length of `v` is less than the sum of the lengths of
`vl` and `vr`, this simply stops when all indices in `v` are filled.
If larger, it stops when `vl` and `vr` are merged into `v`.

The `lt`, `by`, `rev`, `order` keywords work the same as for the `sort` function.
Namely, the `by` keyword lets you provide a function that will be applied to
each element before comparison; the `lt` keyword allows providing a
custom "less than" function; use `rev=true` to reverse the sorting
order. These options are independent and can be used together in all
possible combinations: if both `by` and `lt` are specified, the `lt`
function is applied to the result of the `by` function; `rev=true`
reverses whatever ordering specified via the `by` and `lt` keywords.
"""
function mergesorted!(v::AbstractVector,
                      vl::AbstractVector,
                      vr::AbstractVector;
                      lt=isless,
                      by=identity,
                      rev::Union{Bool,Nothing}=nothing,
                      order::Ordering=Forward)
    ordr = ord(lt,by,rev,order)
    mergesorted!(v, vl, vr, ordr)
end

"""
    mergesorted(vl, vr; lt=isless, by=identity, rev::Union{Bool,Nothing}=nothing, order::Ordering=Forward)

Merge sorted vectors `vl` and `vr` into a new sorted vector in linear time. See [`mergesorted!`](@ref).
"""
function mergesorted(vl::AbstractVector,
                     vr::AbstractVector;
                     lt=isless,
                     by=identity,
                     rev::Union{Bool,Nothing}=nothing,
                     order::Ordering=Forward)
    v = similar(promote_type(typeof(vl),typeof(vr)), length(vl)+length(vr))
    ordr = ord(lt,by,rev,order)
    mergesorted!(v, vl, vr, ordr)
end

end # module


text:
"""
    NOCB(; context=Context())

Next observation carried backward (NOCB) iterates backwards through the `data` and fills
missing data with the next existing observation.

See also:
- [LOCF](@ref): Last Observation Carried Forward

WARNING: missing elements at the tail of the array may not be imputed if there is no
existing observation to carry backward. As a result, this method does not guarantee
that all missing values will be imputed.

# Keyword Arguments
* `context::AbstractContext`: A context which keeps track of missing data
  summary information

# Example
```jldoctest
julia> using Impute: NOCB, Context, impute

julia> M = [1.0 2.0 missing missing 5.0; 1.1 2.2 3.3 missing 5.5]
2×5 Array{Union{Missing, Float64},2}:
 1.0  2.0   missing  missing  5.0
 1.1  2.2  3.3       missing  5.5

julia> impute(M, NOCB(; context=Context(; limit=1.0)); dims=2)
2×5 Array{Union{Missing, Float64},2}:
 1.0  2.0  5.0  5.0  5.0
 1.1  2.2  3.3  5.5  5.5
```
"""
struct NOCB <: Imputor
    context::AbstractContext
end

# TODO: Switch to using Base.@kwdef on 1.1
NOCB(; context=Context()) = NOCB(context)

function impute!(data::AbstractVector, imp::NOCB)
    imp.context() do c
        end_idx = findlast(c, data) - 1
        for i in end_idx:-1:firstindex(data)
            if ismissing!(c, data[i])
                data[i] = data[i+1]
            end
        end

        return data
    end
end


text:
# Make Chain without transaction pool

# TODO: check if it is better to use something like
# struct Link
#     hash :: Array{UInt256, 1}
#     ...
# end
# instead

"""
    Link

The elements of the chain, only for internal representation.

```
link = chain[0]
Block(link)
Header(link)
double_sha256(link)
```
"""
struct Link
    hash          :: UInt256
    file_number   :: UInt64
    file_position :: UInt64
end

Link() = Link(zero(UInt256), typemax(UInt64), typemax(UInt64))

double_sha256(link::Link) = link.hash
get_file_pos(link::Link) = link.file_position
get_file_num(link::Link) = link.file_number

# function Base.show(io::IO, link::Link)
#     println(io, "Link:")
#     println(io, "  File number: " * string(get_file_num(link), base = 10))
#     println(io, "  Position:    " * string(get_file_pos(link), base = 16))
# end
function Base.show(io::IO, link::Link)
    println(io, "Link:")
    if !get(io, :limit, false)
        println(io, "  Hash:        " * string(double_sha256(link), base = 16))
    end
    println(io, "  File number: " * string(get_file_num(link), base = 10))
    println(io, "  Position:    " * string(get_file_pos(link), base = 16))
end

# TODO: make this zero based!
"""
    Chain

`Vector{Link}`, data type to represent blockchain.

```julia
chain = make_chain()
```
"""
struct Chain
    data::Vector{Link}
end
Chain() = Chain(Link[])

Base.copy(x::Chain) = Chain(copy(x.data))

to_index(i::Integer) = i + 1
from_index(i::Integer) = i - 1

to_index(i::AbstractUnitRange) = to_index(first(i)):to_index(last(i))
from_index(i::AbstractUnitRange) = from_index(first(i)):from_index(last(i))

Base.eltype(x::Chain) = Link

Base.push!(x::Chain, l::Link) = push!(x.data, l)
Base.deleteat!(x::Chain, i::Integer) = deleteat!(x.data, to_index(i))

Base.length(x::Chain) = length(x.data)
Base.firstindex(x::Chain) = 0
Base.lastindex(x::Chain) = from_index(lastindex(x.data))
Base.eachindex(x::Chain) = from_index(eachindex(x.data))

Base.checkbounds(::Type{Bool}, x::Chain, i::Integer) =
    checkbounds(Bool, x.data, to_index(i))
function Base.checkbounds(x::Chain, i::Integer)
    if checkbounds(Bool, x.data, to_index(i))
        return nothing
    else
        throw(BoundsError(x, i))
    end
end

Base.checkbounds(::Type{Bool}, x::Chain, i::UnitRange) =
    checkbounds(Bool, x.data, to_index(first(i))) &&
    checkbounds(Bool, x.data, to_index(last(i)))

function Base.checkbounds(x::Chain, i::UnitRange)
    if checkbounds(Bool, x, i)
        return nothing
    else
        throw(BoundsError(x, i))
    end
end

Base.first(x::Chain) = first(x.data)
Base.last(x::Chain) = last(x.data)

@inline function Base.getindex(x::Chain, i::Integer)
    @boundscheck checkbounds(x, i)
    # TODO: @inbounds here?
    x.data[to_index(i)]
end

@inline function Base.getindex(x::Chain, i::UnitRange)
    @boundscheck checkbounds(x, i)
    # TODO: @inbounds here?
    Chain(x.data[to_index(i)])
end

Base.getindex(x::Chain) = x

function Base.show(io::IO, chain::Chain)
    # TODO: this prints a newline at the end...
    print(io, "Chain length ", string(length(chain), base = 10))
end

# function Base.showall(io::IO, chain::Chain)
#     show(io, chain)
#     for i in 1:length(chain)
#         show(io, chain[i])
#     end
# end

# struct Chain
#     data :: Array{Link, 1}
# end
#
# Chain() = Chain(Array(0, 1))
# push!(chain::Chain, link::Link) = push!(chain.data, link)
# length(chain::Chain) = length(chain.data)
# getindex(chain::Chain, key...) = getindex(chain, key...)

function Header(link::Link)

    # fn = get_block_chain_file_path(get_file_num(link))
    # open(fn) do fh

    link |>
        get_file_num |>
        get_block_chain_file_path |>
        x -> open(x) do fh

            seek(fh, get_file_pos(link))
            check_magic_bytes(fh)

            # Skip the Blocksize UInt32:
            skip(fh, sizeof(UInt32))

            Header(fh)
        end
end

function Block(link::Link)

    # fn = get_block_chain_file_path(get_file_num(link))
    # open(fn) do fh

    link |>
        get_file_num |>
        get_block_chain_file_path |>
        x -> open(x) do fh

            seek(fh, get_file_pos(link))
            check_magic_bytes(fh)

            Block(fh)
        end
end

function dump_block_data(link::Link)
    link |>
        get_file_num |>
        get_block_chain_file_path |>
        x -> open(x) do fh
            seek(fh, get_file_pos(link))
            check_magic_bytes(fh)
            dump_block_data(fh)
        end
end

function link_and_prev_hash(bcio::BCIterator)

    file_pos = get_file_pos(bcio)
    file_num = get_file_num(bcio)

    header = Header(bcio)
    block_hash = double_sha256(header)

    prev_block_hash = header.previous_hash

    Link(block_hash, file_num, file_pos), prev_block_hash
end

function check_out_of_order_blocks!(
        chain::Chain,
        out_of_order_blocks::Vector{Link},
        out_of_order_prev_hashes::Vector{UInt256}
    )
    # TODO: optimize this using a linked list? or a Dict or other kind of hash
    # table

    @assert length(out_of_order_blocks) == length(out_of_order_prev_hashes)

    @label start
    for l in eachindex(out_of_order_blocks)

        if out_of_order_prev_hashes[l] == chain.data[end].hash

            push!(chain, out_of_order_blocks[l])

            deleteat!(out_of_order_blocks, l)
            deleteat!(out_of_order_prev_hashes, l)

            @goto start
        end

    end

    return nothing
end

function BCIterator(x::Link)
    bcio = BCIterator(get_file_num(x))
    BCIterator(seek(bcio, get_file_pos(x)))
end

function init_make_chain_long(chain::Chain, max_out_of_order_blocks::Int64)

    _chain = copy(chain)
    bcio = BCIterator(_chain[end - max_out_of_order_blocks + 1])
    out_of_order_blocks = Link[]
    out_of_order_prev_hashes = UInt256[]

    # collect all of the possible out of order blocks and add them to
    # `_chain`
    bcio_end = _chain[end] |> BCIterator
    while bcio < bcio_end
        link, prev_block_hash = link_and_prev_hash(bcio)

        if !any(j -> _chain[j].hash == link.hash,
                (length(_chain) - max_out_of_order_blocks):(length(_chain) - 1))
            push!(out_of_order_blocks, link)
            push!(out_of_order_prev_hashes, prev_block_hash)
        end

    end
    @assert bcio == bcio_end
    close(bcio_end)

    return _chain, bcio, out_of_order_blocks, out_of_order_prev_hashes
end

function init_make_chain_short()
    _chain = Chain()
    bcio = BCIterator()
    out_of_order_blocks = Link[]
    out_of_order_prev_hashes = UInt256[]

    link, prev_block_hash = link_and_prev_hash(bcio)
    push!(_chain, link)

    return _chain, bcio, out_of_order_blocks, out_of_order_prev_hashes
end

"""
    make_chain(chain::Chain, height::Integer)::Chain
    make_chain(chain::Chain)::Chain
    make_chain(height::Integer)::Chain
    make_chain()::Chain

Read a chain of `height` or the entire bockchain, if `height` is not specified.
If `chain` is supplied, update the given chain.
"""
function make_chain(
        chain                   :: Chain,
        height                  :: Int64,
        # This is hardcoded in the bitcoin reference client:
        max_out_of_order_blocks :: Int64 = 1024
    )

    if length(chain) <= max_out_of_order_blocks
        _chain, bcio, out_of_order_blocks, out_of_order_prev_hashes =
            init_make_chain_short()
    else
        _chain, bcio, out_of_order_blocks, out_of_order_prev_hashes =
            init_make_chain_long(chain, max_out_of_order_blocks)
    end

    # TODO: if height is larger the actual _chain length, this will run forever
    while length(_chain) < height
        local link, prev_block_hash
        # TODO: don't use errors for programming logic
        try
            link, prev_block_hash = link_and_prev_hash(bcio)
        catch e
            close(bcio)
            if typeof(e) == NoMoreFilesError
                @show e
                return _chain
            elseif typeof(e) == EOFError
                @show e
                return _chain
            elseif typeof(e) == MagicBytesError
                @show e
                # block file are padded with zeros
                if e.bytes == zero(UInt32)
                    # return _chain
                    @show _chain[end]
                    # rethrow(e)
                    return _chain
                else
                    @show _chain[end]
                    rethrow(e)
                end
            else
                @show _chain[end]
                rethrow(e)
            end
        end

        if _chain[end].hash == prev_block_hash
            push!(_chain, link)
        else
            push!(out_of_order_blocks, link)
            push!(out_of_order_prev_hashes, prev_block_hash)
            check_out_of_order_blocks!(_chain, out_of_order_blocks,
                                       out_of_order_prev_hashes)
        end

    end

    close(bcio)
    return _chain
end

make_chain()             = make_chain(Chain(), typemax(Int64))
make_chain(n::Int64)     = make_chain(Chain(), n)
make_chain(chain::Chain) = make_chain(chain, typemax(Int64))

# TODO: this one probably does not work well at the moment, when I tested it, it
# was more or less as fast as `make_dict`, I bet the dictionary access can be
# made faster.
"""
    make_chain_dict

Alternative implementation of `make_chain`.
"""
function make_chain_dict(
    chain                   :: Chain,
    height                  :: Integer,
    # This is hardcoded in the bitcoin reference client:
    max_out_of_order_blocks :: Integer = 1024
)

    if length(chain) <= max_out_of_order_blocks
        bcio = BCIterator()::BCIterator
        chain = Chain()
    else
        bcio = BCIterator(chain[end - max_out_of_order_blocks + 1])::BCIterator
        chain = chain[1:(end - max_out_of_order_blocks)]
    end

    out_of_order_blocks = Dict{UInt256, Link}()
    # out_of_order_blocks = ObjectIdDict()

    link, prev_block_hash = link_and_prev_hash(bcio)

    push!(chain, link)

    while length(chain) < height

        # TODO: don't use errors for programming logic!!!
        try
            link, prev_block_hash = link_and_prev_hash(bcio)
        catch e
            if typeof(e) == NoMoreFilesError
                return chain
            elseif typeof(e) == MagicBytesError
                # block file are padded with zeros
                if e.bytes == zero(UInt32)
                    return chain
                else
                    @show chain[end]
                    rethrow(e)
                end
            else
                @show chain[end]
                rethrow(e)
            end
        end

        if chain[end].hash == prev_block_hash
            push!(chain, link)
        else
            out_of_order_blocks[prev_block_hash] = link

            while true
                try
                    # ObjectIdDict is {Any, Any}
                    push!(chain, pop!(out_of_order_blocks, chain[end].hash)::Link)
                catch
                    break
                end
            end

            # while haskey(out_of_order_blocks, chain[end].hash)
            #     # ObjectIdDict is {Any, Any}
            #     push!(chain, pop!(out_of_order_blocks, chain[end].hash)::Link)
            # end
        end

    end

    return chain
end


text:
include("scene.jl")
include("dynamics.jl")

"""Generate program"""
function generateprogram(rng=Random.GLOBAL_RNG; gridsize::Int=16, group::Bool=false)
  # generate objects and types
  types_and_objects = generatescene_objects(rng, gridsize=gridsize)
  generateprogram_given_objects(types_and_objects, rng, gridsize=gridsize, group=group)
end

"""Generate program given object decomposition (types and objects)"""
function generateprogram_given_objects(types_and_objects, rng=Random.GLOBAL_RNG; gridsize::Int=16, group::Bool=false)
  # generate objects and types
  types, objects, background, _ = types_and_objects

  non_object_global_vars = []
  num_non_object_global_vars = rand(0:0)

  for i in 1:num_non_object_global_vars
    type = rand(["Bool", "Int"])
    if type == "Bool"
      push!(non_object_global_vars, (type, rand(["true", "false"]), i))
    else
      push!(non_object_global_vars, (type, rand(1:3), i))
    end
  end

  if (!group)
    # construct environment object
    environment = Dict(["custom_types" => Dict(
                                              map(t -> "Object_ObjType$(t.id)" => t.custom_fields, types)
                                              ),
                        "variables" => Dict(
                                            vcat(
                                            map(obj -> "obj$(obj.id)" => "Object_ObjType$(obj.type.id)", objects)...,
                                            map(tuple -> "globalVar$(tuple[3])" => tuple[1], non_object_global_vars)...
                                            )
                                           )])

    # generate next values for each object
    next_vals = map(obj -> genObjectUpdateRule("obj$(obj.id)", environment), objects)
    objects = [(objects[i], next_vals[i]) for i in 1:length(objects)]

    # generate on-clauses for each object
    on_clause_object_ids = rand(1:length(objects), rand(1:length(objects)))
    on_clauses = map(i -> (genBool(environment), genUpdateRule("obj$(i)", environment, p=0.5), i), on_clause_object_ids)

    # generate on-clauses for each non-object global variable
    # generate next values for each non-object global variable
    if length(non_object_global_vars) != 0
      non_object_nexts = map(tuple -> genUpdateRule("globalVar$(tuple[3])", environment), non_object_global_vars)
      non_object_on_clause_ids = rand(1:length(non_object_global_vars), rand(0:length(non_object_global_vars)))
      non_object_on_clauses = map(i -> (genBool(environment), genUpdateRule("globalVar$(i)", environment), i), non_object_on_clause_ids)
    else
      non_object_nexts = []
      non_object_on_clauses = []
    end

    """
    (program
      (= GRID_SIZE $(gridsize))
      (= background "$(background)")
      $(join(map(t -> "(object ObjType$(t.id) $(join(map(field -> "(: $(field[1]) $(field[2]))", t.custom_fields), " ")) (list $(join(map(cell -> """(Cell $(cell[1]) $(cell[2]) "$(t.color)")""", t.shape), " "))))", types), "\n  "))

      $(join(map(tuple -> "(: globalVar$(tuple[3]) $(tuple[1]))", non_object_global_vars), "\n  "))

      $(join(map(tuple -> "(= globalVar$(tuple[3]) (initnext $(tuple[2]) $(non_object_nexts[tuple[3]])))", non_object_global_vars), "\n  "))

      $((join(map(obj -> """(: obj$(obj[1].id) ObjType$(obj[1].type.id))""", objects), "\n  "))...)

      $((join(map(obj ->
      """(= obj$(obj[1].id) (initnext (ObjType$(obj[1].type.id) $(join(obj[1].custom_field_values, " ")) (Position $(obj[1].position[1] - 1) $(obj[1].position[2] - 1))) $(obj[2])))""", objects), "\n  ")))

      $((join(map(tuple ->
      """(on $(tuple[1]) (= obj$(tuple[3]) $(tuple[2])))""", on_clauses), "\n  "))...)

      $((join(map(tuple ->
      """(on $(tuple[1]) (= globalVar$(tuple[3]) $(tuple[2])))""", non_object_on_clauses), "\n  "))...)
    )
    """
  else
    # group objects of the same type into lists
    type_ids = unique(map(obj -> obj.type.id, objects))
    list_type_ids = filter(id -> count(obj -> obj.type.id == id, objects) > 1, type_ids)
    constant_type_ids = filter(id -> count(obj -> obj.type.id == id, objects) == 1, type_ids)

    println(length(types))
    println(length(objects))

    environment = Dict(["custom_types" => Dict(
                                map(t -> "Object_ObjType$(t.id)" => t.custom_fields, types)
                                ),
                        "variables" => Dict(
                              vcat(
                                map(id -> "objList$(findall(x -> x == id, list_type_ids)[1])" => "ObjectList_ObjType$(id)", list_type_ids)...,
                                map(id -> "obj$(findall(x -> x == id, constant_type_ids)[1])" => "Object_ObjType$(id)", constant_type_ids)...,
                                map(tuple -> "globalVar$(tuple[3])" => tuple[1], non_object_global_vars)...
                              )
                            )])

    # generate next values and on-clauses for each object
    # lists
    if length(list_type_ids) != 0
      next_list_vals = map(id -> genUpdateRule("objList$(findall(x -> x == id, list_type_ids)[1])", environment), list_type_ids)

      on_clause_list_ids = rand(list_type_ids, rand(1:length(list_type_ids)))
      on_clauses_list = map(id -> (genBool(environment), genUpdateRule("objList$(findall(x -> x == id, list_type_ids)[1])", environment, p=0.5), findall(x -> x == id, list_type_ids)[1]), on_clause_list_ids)
    else
      next_list_vals = []
      on_clauses_list = []
    end

    # constants
    if length(constant_type_ids) != 0
      next_constant_vals = map(id -> genUpdateRule("obj$(findall(x -> x == id, constant_type_ids)[1])", environment), constant_type_ids)

      on_clauses_constant_ids = rand(constant_type_ids, rand(1:length(constant_type_ids)))
      on_clauses_constant = map(id -> (genBool(environment), genUpdateRule("obj$(findall(x -> x == id, constant_type_ids)[1])", environment, p=0.5), findall(x -> x == id, constant_type_ids)[1]), on_clauses_constant_ids)
    else
      next_constant_vals = []
      on_clauses_constant = []
    end

    # generate next values and on-clauses for each non-object variable
    if length(non_object_global_vars) != 0
      non_object_nexts = map(tuple -> genUpdateRule("globalVar$(tuple[3])", environment), non_object_global_vars)
      non_object_on_clause_ids = rand(1:length(non_object_global_vars), rand(0:length(non_object_global_vars)))
      non_object_on_clauses = map(i -> (genBool(environment), genUpdateRule("globalVar$(i)", environment), i), non_object_on_clause_ids)
    else
      non_object_nexts = []
      non_object_on_clauses = []
    end
    """
    (program
      (= GRID_SIZE $(gridsize))
      (= background "$(background)")
      $(join(map(t -> "(object ObjType$(t.id) $(join(map(field -> "(: $(field[1]) $(field[2]))", t.custom_fields), " ")) (list $(join(map(cell -> """(Cell $(cell[1]) $(cell[2]) "$(t.color)")""", t.shape), " "))))", types), "\n  "))

      $(join(map(tuple -> "(: globalVar$(tuple[3]) $(tuple[1]))", non_object_global_vars), "\n  "))

      $(join(map(tuple -> "(= globalVar$(tuple[3]) (initnext $(tuple[2]) $(non_object_nexts[tuple[3]])))", non_object_global_vars), "\n  "))

      $((join(map(id -> """(: objList$(findall(x -> x == id, list_type_ids)[1]) (List ObjType$(id)))""", list_type_ids), "\n  "))...)
      $((join(map(id -> """(: obj$(findall(x -> x == id, constant_type_ids)[1]) ObjType$(id))""", constant_type_ids), "\n  "))...)

      $((join(map(id ->
      """(= objList$(findall(x -> x == id, list_type_ids)[1]) (initnext (list $(join(map(obj -> "(ObjType$(obj.type.id) $(join(obj.custom_field_values, " ")) (Position $(obj.position[1] - 1) $(obj.position[2] - 1)))", filter(o -> o.type.id == id, objects)), " "))) $(next_list_vals[findall(y -> y == id, list_type_ids)[1]])))""", list_type_ids), "\n  ")))

      $((join(map(id ->
      """(= obj$(findall(x -> x == id, constant_type_ids)[1]) (initnext $(join(map(obj -> "(ObjType$(obj.type.id) $(join(obj.custom_field_values, " ")) (Position $(obj.position[1] - 1) $(obj.position[2] - 1)))", filter(o -> o.type.id == id, objects)))) $(next_constant_vals[findall(y -> y == id, constant_type_ids)[1]])))""", constant_type_ids), "\n  ")))

      $((join(map(tuple ->
      """(on $(tuple[1]) (= objList$(tuple[3]) $(tuple[2])))""", on_clauses_list), "\n  "))...)

      $((join(map(tuple ->
      """(on $(tuple[1]) (= obj$(tuple[3]) $(tuple[2])))""", on_clauses_constant), "\n  "))...)

      $((join(map(tuple ->
      """(on $(tuple[1]) (= globalVar$(tuple[3]) $(tuple[2])))""", non_object_on_clauses), "\n  "))...)
    )
    """
  end
end

function generate_hypothesis_update_rule(object, object_decomposition; p=0.0)
  types, objects, background, gridsize = object_decomposition
  objects = [object, filter(o -> o.position != (-1, -1), objects)...]
  # construct environment
  environment = Dict(["custom_types" => Dict(map(t -> "Object_ObjType$(t.id)" => t.custom_fields, types)
                          ),
                      "variables" => Dict(map(obj -> "obj$(obj.id)" => "Object_ObjType$(obj.type.id)", objects)
                      )])

  # generate update rule
  """(= obj$(object.id) $(genObjectUpdateRule("obj$(object.id)", environment, p=p)))"""
end

function generate_hypothesis_position(position, environment_vars)
  objects = map(obj -> "obj$(obj.id)", filter(x -> x isa Obj, environment_vars))
  user_event = filter(x -> !(x isa Obj), environment_vars)[1]
  @show environment_vars
  choices = []
  if length(objects) != 0
    push!(choices, ["(.. $(rand(objects)) origin)",
                    "(move (.. $(rand(objects)) origin) (Position $(rand(0:1)) $(rand(0:1))))"]...)
  end

  if !isnothing(user_event) && (user_event != "nothing") && (occursin("click", split(user_event, " ")[1]))
    push!(choices, "(Position (.. click x) (.. click y))")
  end

  if choices == []
    ""
  else
    choices[rand(1:length(choices))]
  end
end

function generate_hypothesis_position_program(hypothesis_position, actual_position, object_decomposition)
  program_no_update_rules = program_string_synth(object_decomposition)

  program = string(program_no_update_rules[1:end-2], "\n",
                    """
                    (: matches Bool)
                    (= matches (initnext false (prev matches)))

                    (on (== $(hypothesis_position) (Position $(actual_position[1]) $(actual_position[2]))) (= matches true))
                    """, "\n",
                   ")")

end

function generate_hypothesis_string(string, environment_vars, object_types)
  objects = filter(x -> (x isa Obj) && length(x.type.custom_fields) > 0, environment_vars)
  object = rand(objects)
  @show string
  @show objects
  x = filter(type -> length(type.custom_fields) > 0 && string in type.custom_fields[1][3], object_types)
  @show x
  pair_string = filter(s -> s != string, map(type -> type.custom_fields[1][3], filter(type -> length(type.custom_fields) > 0 && string in type.custom_fields[1][3], object_types))[1])[1]

  first_string, second_string = rand() > 0.5 ? (string, pair_string) : (pair_string, string)
  """(if (== (.. (prev obj$(object.id)) color) "$(object.type.custom_fields[1][3][1])") then "$(first_string)" else "$(second_string)")"""
end

function generate_hypothesis_string_program(hypothesis_string, actual_string, object_decomposition)
  program_no_update_rules = program_string_synth(object_decomposition)

  program = string(program_no_update_rules[1:end-2], "\n",
                    """
                    (: matches Bool)
                    (= matches (initnext false (prev matches)))

                    (on (== $(hypothesis_string) "$(actual_string)") (= matches true))
                    """, "\n",
                   ")")
end

function gen_event_bool(object_decomposition, object_id, user_events, global_var_dict)
  object_types, object_mapping, _, _ = object_decomposition
  start_objects = map(k -> object_mapping[k][1], filter(key -> !isnothing(object_mapping[key][1]), collect(keys(object_mapping))))
  non_list_objects = filter(x -> (count(y -> y.type.id == x.type.id, start_objects) == 1) && (count(obj_id -> filter(z -> !isnothing(z), object_mapping[obj_id])[1].type.id == x.type.id, collect(keys(object_mapping))) == 1), start_objects)
  user_events = filter(e -> (e != "") && (e != "nothing") && !isnothing(e), user_events)

  # ----- add global events, unrelated to objects -----
  choices = ["true", "up", "down", "left", "right",  "(& clicked (isFree click))"] # "clicked",

  ## time-related
  push!(choices, "(== (% (prev time) 10) 5)")
  push!(choices, "(== (% (prev time) 10) 0)")
  push!(choices, "(== (% (prev time) 5) 2)")
  push!(choices, "(== (% (prev time) 4) 2)")

  # globalVar-related
  if length(collect(keys(global_var_dict))) > 0
    for key in collect(keys(global_var_dict))
      values = unique(global_var_dict[key])
      for value in values
        push!(choices, "(== (prev globalVar$(key)) $(value))")
      end
    end
  end

  # ----- add events dealing with constant objects (i.e. objects not contained in a list) -----
  if non_list_objects != []
    for object in non_list_objects
      push!(choices, ["(.. (prev obj$(object.id)) alive)",
                      "(clicked (prev obj$(object.id)))",
                      vcat(map(pos -> ["(== (.. (.. (prev obj$(object.id)) origin) x) $(pos[1]))",
                                       "(== (.. (.. (prev obj$(object.id)) origin) y) $(pos[2]))",
                                       "(& (== (.. (.. (prev obj$(object.id)) origin) x) $(pos[1])) (== (.. (.. (prev obj$(object.id)) origin) y) $(pos[2])))",
                                       "(& (.. (prev obj$(object.id)) alive) (== (.. (.. (prev obj$(object.id)) origin) x) $(pos[1])))",
                                       "(& (.. (prev obj$(object.id)) alive) (== (.. (.. (prev obj$(object.id)) origin) y) $(pos[2])))",
                                       "(& (.. (prev obj$(object.id)) alive) (& (== (.. (.. (prev obj$(object.id)) origin) x) $(pos[1])) (== (.. (.. (prev obj$(object.id)) origin) y) $(pos[2]))))"],
                           map(obj -> obj.position, filter(x -> !isnothing(x), object_mapping[object.id])))...)...,
      ]...)

      if object.type.custom_fields != [] && object.type.custom_fields[1][1] == "color"
        color_values = object.type.custom_fields[1][3]
        for color in color_values
          push!(choices, """(== (.. (prev obj$(object.id)) color) "$(color)")""")
        end
      end

      for type in object_types
        push!(choices, [
          "(intersects (prev obj$(object.id)) (prev addedObjType$(type.id)List))",
          "(intersects (adjacentObjs (prev obj$(object.id))) (prev addedObjType$(type.id)List))", # can add things with `.. id)` x here
          "(intersects (prev obj$(object.id)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))",
          "(& (isWithinBounds (moveLeft (prev obj$(object.id)))) (| (! (intersects (moveLeft (prev obj$(object.id))) (prev addedObjType$(type.id)List))) (& (! (intersects (move (prev obj$(object.id)) (Position -2 0)) (prev addedObjType$(type.id)List))) (isWithinBounds (move (prev obj$(object.id)) (Position -2 0))))))",
          "(& (isWithinBounds (moveUp (prev obj$(object.id)))) (| (! (intersects (moveUp (prev obj$(object.id))) (prev addedObjType$(type.id)List))) (& (! (intersects (move (prev obj$(object.id)) (Position 0 -2)) (prev addedObjType$(type.id)List))) (isWithinBounds (move (prev obj$(object.id)) (Position 0 -2))))))",
          ]...)
        for object2 in non_list_objects
          if object.id != object2.id
            # sokoban
            ## left
            push!(choices, "(& left (& (in true (map (--> obj (& (isWithinBounds obj) (isFree (.. obj origin)))) (map (--> obj (moveLeft obj)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))) (in (Position 1 0) (map (--> obj (displacement (.. obj origin) (.. (prev obj$(object.id)) origin))) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))))")
            # push!(choices, "(& left (& (intersects (prev obj$(object2.id)) (filter (--> obj (== (.. obj id) $(object_id)) (prev addedObjType$(type.id)List)))) (in (Position 1 0) (map (--> obj (displacement obj (prev obj$(object.id)))) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))))")

            ## up
            push!(choices, "(& up (& (intersects (prev obj$(object2.id)) (map (--> obj (moveUp obj)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))) (in (Position 0 1) (map (--> obj (displacement (.. obj origin) (.. (prev obj$(object.id)) origin))) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))))")
            push!(choices, "(& up (& (in true (map (--> obj (& (isWithinBounds obj) (isFree (.. obj origin)))) (map (--> obj (moveUp obj)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))) (in (Position 0 1) (map (--> obj (displacement (.. obj origin) (.. (prev obj$(object.id)) origin))) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))))")
          end
        end
      end
    end
  end

  if length(non_list_objects) > 1
    for object_1 in non_list_objects
      for object_2 in non_list_objects
        if object_1.id != object_2.id
          push!(choices, [
            "(! (intersects (prev obj$(object_1.id)) (prev obj$(object_2.id))))",
            "(intersects (adjacentObjs (prev obj$(object_1.id))) (prev obj$(object_2.id)))",
          ]...)
        end
      end
    end
  end

  # ----- add events dealing with objects contained in a list -----
  for type in object_types
    push!(choices, "(clicked (prev addedObjType$(type.id)List))")
    push!(choices, "(== (prev addedObjType$(type.id)List) (list))")
    push!(choices, "(!= (prev addedObjType$(type.id)List) (list))")

    # color-related events
    if (length(type.custom_fields) > 0) && type.custom_fields[1][1] == "color"
      color_values = type.custom_fields[1][3]
      for color in color_values
        push!(choices, """(clicked (filter (--> obj (== (.. obj color) "$(color)")) (prev addedObjType$(type.id)List)))""")
        push!(choices, """(intersects (list "$(color)") (map (--> obj (.. obj color)) (prev addedObjType$(type.id)List)))""")
        push!(choices, """(clicked (filter (--> obj (== (.. obj color) "$(color)")) (prev addedObjType$(type.id)List)))""")

        # object_id-based
        push!(choices, """(intersects (list "$(color)") (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))""")
        push!(choices, """(intersects (list "$(color)") (map (--> obj (.. obj color)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))""")
        push!(choices, """(intersects (unfold (map (--> obj (adjacentObjs obj)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))) (filter (--> obj (== (.. obj color) "$(color)")) (prev addedObjType$(type.id)List)))""")
        push!(choices, """(intersects (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)) (filter (--> obj (== (.. obj color) "$(color)")) (prev addedObjType$(type.id)List)))""")
        for color2 in color_values
          if color != color2
            push!(choices, """(& (intersects (filter (--> obj (== (.. obj color) "$(color2)")) (prev addedObjType$(type.id)List)) (map (--> obj (moveDown obj)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))) (intersects (list "$(color)") (map (--> obj (.. obj color)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))))""")
            push!(choices, """(& (intersects (filter (--> obj (& (== (.. (.. obj origin) y) 5) (== (.. obj color) "$(color2)"))) (prev addedObjType$(type.id)List)) (map (--> obj (moveDown obj)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))) (intersects (list "$(color)") (map (--> obj (.. obj color)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))))""")
          end
        end
      end
    end
    # more object_id-based
    push!(choices, "(& (clicked (prev addedObjType$(type.id)List)) (in (objClicked click (prev addedObjType$(type.id)List)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))")
    push!(choices, "(& (clicked (prev addedObjType$(type.id)List)) (! (in (objClicked click (prev addedObjType$(type.id)List)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))))")
    push!(choices, "(clicked (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)))")
    push!(choices, "(in true (map (--> obj (== (.. obj id) $(object_id))) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))")
    push!(choices, "(in false (map (--> obj (== (.. obj id) $(object_id))) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))")

    # object-specific field-based
    object_specific_fields = filter(t -> occursin("field", t[1]), type.custom_fields)
    if object_specific_fields != []
      field_values = object_specific_fields[1][3]
      for value in field_values
        push!(choices, "(intersects (list $(value)) (map (--> obj (.. obj field1)) (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List))))")
      end
    end

    for type2 in object_types
      if type2.id != type.id
        push!(choices, "(intersects (prev addedObjType$(type.id)List) (prev addedObjType$(type2.id)List))")
        push!(choices, "(intersects (filter (--> obj (== (.. obj id) $(object_id))) (prev addedObjType$(type.id)List)) (prev addedObjType$(type2.id)List))")
      end
    end

  end

  println("XYZ")
  @show choices
  sort(choices, by=length)
end

function construct_compound_events(choices, event_vector_dict)
  println("START construct_compound_events")
  @show event_vector_dict
  object_specific_events = filter(k -> !(event_vector_dict[k] isa AbstractArray), choices)
  global_events = filter(k -> event_vector_dict[k] isa AbstractArray, choices)

  nonzero_object_specific_events = filter(e -> unique(vcat(collect(values(event_vector_dict[e]))...)) != [0], object_specific_events)
  nonzero_global_events = filter(e -> unique(event_vector_dict[e]) != [0], global_events)

  compound_events = []

  # construct global/global compound events and global/object-specific compound events
  @show length(nonzero_global_events)
  nonzero_global_events = sort(nonzero_global_events, by=length)
  # @show nonzero_global_events
  for i in 1:length(nonzero_global_events)
    @show i
    event_i = nonzero_global_events[i]
    @show event_i
    for j in (i+1):length(nonzero_global_events)
      event_j = nonzero_global_events[j]
      if !occursin(event_i, event_j) && !occursin(event_j, event_i)
        and_value = event_vector_dict[event_i] .& event_vector_dict[event_j]
        or_value = event_vector_dict[event_i] .| event_vector_dict[event_j]

        if unique(and_value) != [0]
          push!(compound_events, "(& $(event_i) $(event_j))")
          event_vector_dict["(& $(event_i) $(event_j))"] = and_value
        end

        if unique(or_value) != [0]
          push!(compound_events, "(| $(event_i) $(event_j))")
          event_vector_dict["(| $(event_i) $(event_j))"] = or_value
        end

      end
    end

    # for k in 1:length(nonzero_object_specific_events)
    #   event_k = nonzero_object_specific_events[k]
    #   and_event_values = Dict()
    #   or_event_values = Dict()
    #   object_ids = collect(keys(event_vector_dict[event_k]))
    #   for object_id in object_ids
    #     and_value = event_vector_dict[event_i] .& event_vector_dict[event_k][object_id]
    #     or_value = event_vector_dict[event_i] .| event_vector_dict[event_k][object_id]

    #     and_event_values[object_id] = and_value
    #     or_event_values[object_id] = or_value
    #   end

    #   if unique(vcat(map(id -> and_event_values[id], object_ids)...)) != [0]
    #     push!(compound_events, "(& $(event_i) $(event_k))")
    #     event_vector_dict["(& $(event_i) $(event_k))"] = and_event_values
    #   end

    #   if unique(vcat(map(id -> or_event_values[id], object_ids)...)) != [0]
    #     push!(compound_events, "(| $(event_i) $(event_k))")
    #     event_vector_dict["(| $(event_i) $(event_k))"] = or_event_values
    #   end

    # end

  end

  # skip doubly object-specific events for now
  println("END construct_compound_events")
  sort(compound_events, by=length)
end


text:
abstract type DependencyTreeError <: Exception end

struct GraphConnectivityError <: DependencyTreeError
    g
    msg::String
end

struct NonProjectiveGraphError <: DependencyTreeError
    g
end

struct RootlessGraphError <: DependencyTreeError
    g
end

struct MultipleRootsError <: DependencyTreeError
    g
end

struct MultiWordTokenError <: DependencyTreeError end

struct EmptyTokenError <: DependencyTreeError end