text:
# Translating a SQL node graph to a SQL statement.

function render(n; dialect = :default)
    actx = AnnotateContext()
    n′ = annotate(convert(SQLNode, n), actx)
    @debug "FunSQL.annotate\n" * sprint(pprint, n′) _group = Symbol("FunSQL.annotate")
    resolve!(actx)
    @debug "FunSQL.resolve!\n" * sprint(pprint, n′) _group = Symbol("FunSQL.resolve!")
    link!(actx)
    @debug "FunSQL.link!\n" * sprint(pprint, n′) _group = Symbol("FunSQL.link!")
    tctx = TranslateContext(dialect, actx.path_map)
    c = translate_toplevel(n′, tctx)
    @debug "FunSQL.translate\n" * sprint(pprint, c) _group = Symbol("FunSQL.translate")
    sql = render(c, dialect = dialect)
    @debug "FunSQL.render\n" * sql _group = Symbol("FunSQL.render")
    sql
end

# Partially constructed query.

struct Assemblage
    clause::Union{SQLClause, Nothing}       # A SQL subquery (possibly without SELECT clause).
    cols::OrderedDict{Symbol, SQLClause}    # SELECT arguments, if necessary.
    repl::Dict{SQLNode, Symbol}             # Maps a reference node to a column alias.

    Assemblage(clause; cols = OrderedDict{Symbol, SQLClause}(), repl = Dict{SQLNode, Symbol}()) =
        new(clause, cols, repl)
end

# Pack SELECT arguments.
function complete(cols::OrderedDict{Symbol, SQLClause})
    args = SQLClause[]
    for (name, col) in cols
        if !(@dissect(col, ID(name = id_name)) && id_name == name)
            col = AS(over = col, name = name)
        end
        push!(args, col)
    end
    if isempty(args)
        push!(args, LIT(missing))
    end
    args
end

# Add a SELECT clause to a partially assembled subquery (if necessary).
function complete(a::Assemblage)
    clause = a.clause
    if !@dissect(clause, SELECT() || UNION())
        args = complete(a.cols)
        clause = SELECT(over = clause, args = args)
    end
    @assert clause !== nothing
    clause
end

# Build node->clause map assuming that the assemblage will be extended.
function make_subs(a::Assemblage, ::Nothing)::Dict{SQLNode, SQLClause}
    subs = Dict{SQLNode, SQLClause}()
    for (ref, name) in a.repl
        subs[ref] = a.cols[name]
    end
    subs
end

# Build node->clause map assuming that the assemblage will be completed.
function make_subs(a::Assemblage, alias::Symbol)
    subs = Dict{SQLNode, SQLClause}()
    cache = Dict{Symbol, SQLClause}()
    for (ref, name) in a.repl
        subs[ref] = get(cache, name) do
            ID(over = alias, name = name)
        end
    end
    subs
end

# Build a node->alias map and implicit SELECT columns for a UNION query.
function make_repl_cols(refs::Vector{SQLNode})::Tuple{Dict{SQLNode, Symbol}, OrderedDict{Symbol, SQLClause}}
    repl = Dict{SQLNode, Symbol}()
    cols = OrderedDict{Symbol, SQLClause}()
    dups = Dict{Symbol, Int}()
    for ref in refs
        name′ = name = label(ref)
        k = get(dups, name, 0) + 1
        if k > 1
            name′ = Symbol(name, '_', k)
            while name′ in keys(dups)
                k += 1
                name′ = Symbol(name, '_', k)
            end
            dups[name] = k
        end
        repl[ref] = name′
        cols[name′] = ID(name′)
        dups[name′] = 1
    end
    repl, cols
end

# Build a node->alias map and SELECT columns.
function make_repl_cols(trns::Vector{Pair{SQLNode, SQLClause}})::Tuple{Dict{SQLNode, Symbol}, OrderedDict{Symbol, SQLClause}}
    repl = Dict{SQLNode, Symbol}()
    cols = OrderedDict{Symbol, SQLClause}()
    dups = Dict{Symbol, Int}()
    renames = Dict{Tuple{Symbol, SQLClause}, Symbol}()
    for (ref, c) in trns
        name′ = name = label(ref)
        k = get(dups, name, 0) + 1
        if k > 1
            name′ = get(renames, (name, c), nothing)
            if name′ !== nothing
                repl[ref] = name′
                continue
            end
            name′ = Symbol(name, '_', k)
            while name′ in keys(dups)
                k += 1
                name′ = Symbol(name, '_', k)
            end
            dups[name] = k
        end
        cols[name′] = c
        dups[name′] = 1
        renames[name, c] = name′
        repl[ref] = name′
    end
    (repl, cols)
end

# Translating context.

struct TranslateContext
    dialect::SQLDialect
    path_map::PathMap
    aliases::Dict{Symbol, Int}
    with_map::OrderedDict{SQLNode, Pair{Symbol, Assemblage}}
    recursive::Ref{Bool}
    vars::Dict{Symbol, SQLClause}
    subs::Dict{SQLNode, SQLClause}

    TranslateContext(dialect, path_map::PathMap) =
        new(dialect,
            path_map,
            Dict{Symbol, Int}(),
            OrderedDict{SQLNode, Pair{Symbol, Assemblage}}(),
            Ref(false),
            Dict{Symbol, SQLClause}(),
            Dict{SQLNode, SQLClause}())

    function TranslateContext(ctx::TranslateContext; vars = nothing, subs = nothing)
        new(ctx.dialect,
            ctx.path_map,
            ctx.aliases,
            ctx.with_map,
            ctx.recursive,
            something(vars, ctx.vars),
            something(subs, ctx.subs))
    end
end

allocate_alias(ctx::TranslateContext, n::SQLNode) =
    allocate_alias(ctx, (n[]::BoxNode).type.name)

function allocate_alias(ctx::TranslateContext, alias::Symbol)
    n = get(ctx.aliases, alias, 0) + 1
    ctx.aliases[alias] = n
    Symbol(alias, '_', n)
end

function translate_toplevel(n::SQLNode, ctx)
    c = translate(n, ctx)
    if !isempty(ctx.with_map)
        args = SQLClause[]
        for (alias, a) in values(ctx.with_map)
            cols = Symbol[name for name in keys(a.cols)]
            if isempty(cols)
                push!(cols, :_)
            end
            arg = CTE(over = complete(a), name = alias, columns = cols)
            push!(args, arg)
        end
        c = WITH(over = c, args = args, recursive = ctx.recursive[])
    end
    c
end

# Translating scalar nodes.

function translate(n, ctx::TranslateContext, subs::Dict{SQLNode, SQLClause})
    ctx′ = TranslateContext(ctx, subs = subs)
    translate(n, ctx′)
end

function translate(n::SQLNode, ctx)
    c = get(ctx.subs, n, nothing)
    if c === nothing
        c = convert(SQLClause, translate(n[], ctx))
    end
    c
end

translate(ns::Vector{SQLNode}, ctx) =
    SQLClause[translate(n, ctx) for n in ns]

translate(::Nothing, ctx) =
    nothing

translate(n::AggregateNode, ctx) =
    translate(Val(n.name), n, ctx)

translate(@nospecialize(name::Val{N}), n::AggregateNode, ctx) where {N} =
    translate_default(n, ctx)

function translate_default(n::AggregateNode, ctx)
    args = translate(n.args, ctx)
    filter = translate(n.filter, ctx)
    AGG(uppercase(string(n.name)), distinct = n.distinct, args = args, filter = filter)
end

function translate(::Val{:count}, n::AggregateNode, ctx)
    args = !isempty(n.args) ? translate(n.args, ctx) : [OP("*")]
    filter = translate(n.filter, ctx)
    AGG(:COUNT, distinct = n.distinct, args = args, filter = filter)
end

translate(n::Union{AsNode, HighlightNode}, ctx) =
    translate(n.over, ctx)

function translate(n::IntBindNode, ctx)
    vars′ = copy(ctx.vars)
    for (name, i) in n.label_map
        vars′[name] = translate(n.args[i], ctx)
    end
    ctx′ = TranslateContext(ctx, vars = vars′)
    translate(n.over, ctx′)
end

function translate(n::BoxNode, ctx)
    base = assemble(n, ctx)
    complete(base)
end

translate(n::FunctionNode, ctx) =
    translate(Val(n.name), n, ctx)

translate(@nospecialize(name::Val{N}), n::FunctionNode, ctx) where {N} =
    translate_default(n, ctx)

function translate_default(n::FunctionNode, ctx)
    args = translate(n.args, ctx)
    if Base.isidentifier(n.name)
        FUN(uppercase(string(n.name)), args = args)
    else
        OP(n.name, args = args)
    end
end

for (name, op) in (:not => :NOT,
                   :like => :LIKE,
                   :exists => :EXISTS,
                   :(==) => Symbol("="),
                   :(!=) => Symbol("<>"))
    @eval begin
        translate(::Val{$(QuoteNode(name))}, n::FunctionNode, ctx) =
            OP($(QuoteNode(op)),
               args = SQLClause[translate(arg, ctx) for arg in n.args])
    end
end

for (name, op, default) in ((:and, :AND, true), (:or, :OR, false))
    @eval begin
        function translate(::Val{$(QuoteNode(name))}, n::FunctionNode, ctx)
            args = translate(n.args, ctx)
            if isempty(args)
                LIT($default)
            elseif length(args) == 1
                args[1]
            elseif length(args) == 2 && @dissect(args[1], LIT(val = val)) && val == $default
                args[2]
            elseif @dissect(args[1], OP(name = name, args = args′)) && name === $(QuoteNode(op))
                OP($(QuoteNode(op)), args = SQLClause[args′..., args[2:end]...])
            else
                OP($(QuoteNode(op)), args = args)
            end
        end
    end
end

for (name, op, default) in (("in", "IN", false), ("not in", "NOT IN", true))
    @eval begin
        function translate(::Val{Symbol($name)}, n::FunctionNode, ctx)
            if length(n.args) <= 1
                LIT($default)
            else
                args = translate(n.args, ctx)
                if length(args) == 2 && @dissect(args[2], SELECT() || UNION())
                    OP($op, args = args)
                else
                    OP($op, args[1], FUN("", args = args[2:end]))
                end
            end
        end
    end
end

translate(::Val{Symbol("is null")}, n::FunctionNode, ctx) =
    OP(:IS, SQLClause[translate(arg, ctx) for arg in n.args]..., missing)

translate(::Val{Symbol("is not null")}, n::FunctionNode, ctx) =
    OP("IS NOT", SQLClause[translate(arg, ctx) for arg in n.args]..., missing)

translate(::Val{:case}, n::FunctionNode, ctx) =
    CASE(args = SQLClause[translate(arg, ctx) for arg in n.args])

for (name, op) in (("between", "BETWEEN"), ("not between", "NOT BETWEEN"))
    @eval begin
        function translate(::Val{Symbol($name)}, n::FunctionNode, ctx)
            if length(n.args) == 3
                args = SQLClause[translate(arg, ctx) for arg in n.args]
                OP($op, args[1], args[2], args[3] |> KW(:AND))
            else
                translate_default(n, ctx)
            end
        end
    end
end

for (name, op) in (("current_date", "CURRENT_DATE"),
                   ("current_timestamp", "CURRENT_TIMESTAMP"))
    @eval begin
        function translate(::Val{Symbol($name)}, n::FunctionNode, ctx)
            if isempty(n.args)
                OP($op)
            else
                translate_default(n, ctx)
            end
        end
    end
end

translate(n::LiteralNode, ctx) =
    LIT(n.val)

translate(n::SortNode, ctx) =
    SORT(over = translate(n.over, ctx), value = n.value, nulls = n.nulls)

function translate(n::VariableNode, ctx)
    c = get(ctx.vars, n.name, nothing)
    if c === nothing
        c = VAR(n.name)
    end
    c
end

# Translating subquery nodes.

assemble(n::SQLNode, ctx) =
    assemble(n[], ctx)

function assemble(n::BoxNode, ctx)
    refs′ = SQLNode[]
    for ref in n.refs
        if @dissect(ref, over |> HandleBoundNode(handle = handle)) && handle == n.handle
            push!(refs′, over)
        else
            push!(refs′, ref)
        end
    end
    base = assemble(n.over, refs′, ctx)
    repl′ = Dict{SQLNode, Symbol}()
    for ref in n.refs
        if @dissect(ref, over |> HandleBoundNode(handle = handle)) && handle == n.handle
            repl′[ref] = base.repl[over]
        else
            repl′[ref] = base.repl[ref]
        end
    end
    Assemblage(base.clause, cols = base.cols, repl = repl′)
end

assemble(n::SQLNode, refs, ctx) =
    assemble(n[], refs, ctx)

function assemble(::Nothing, refs, ctx)
    @assert isempty(refs)
    Assemblage(nothing)
end

function aligned_columns(refs, repl, args)
    length(refs) == length(args) || return false
    for (ref, arg) in zip(refs, args)
        if !(@dissect(arg, ID(name = name) || AS(name = name)) && name === repl[ref])
            return false
        end
    end
    return true
end

function assemble(n::AppendNode, refs, ctx)
    base = assemble(n.over, ctx)
    branches = [n.over => base]
    for arg in n.args
        push!(branches, arg => assemble(arg, ctx))
    end
    dups = Dict{SQLNode, SQLNode}()
    seen = Dict{Symbol, SQLNode}()
    for ref in refs
        name = base.repl[ref]
        if name in keys(seen)
            other_ref = seen[name]
            if all(a.repl[ref] === a.repl[other_ref] for (arg, a) in branches)
                dups[ref] = seen[name]
            end
        else
            seen[name] = ref
        end
    end
    urefs = SQLNode[ref for ref in refs if !(ref in keys(dups))]
    repl, dummy_cols = make_repl_cols(urefs)
    for (ref, uref) in dups
        repl[ref] = repl[uref]
    end
    cs = SQLClause[]
    for (arg, a) in branches
        if @dissect(a.clause, SELECT(args = args)) && aligned_columns(urefs, repl, args)
            push!(cs, a.clause)
            continue
        elseif !@dissect(a.clause, SELECT() || UNION())
            alias = nothing
            tail = a.clause
        else
            alias = allocate_alias(ctx, arg)
            tail = FROM(AS(over = complete(a), name = alias))
        end
        subs = make_subs(a, alias)
        cols = OrderedDict{Symbol, SQLClause}()
        for ref in urefs
            name = repl[ref]
            cols[name] = subs[ref]
        end
        c = SELECT(over = tail, args = complete(cols))
        push!(cs, c)
    end
    c = UNION(over = cs[1], all = true, args = cs[2:end])
    Assemblage(c, repl = repl, cols = dummy_cols)
end

function assemble(n::AsNode, refs, ctx)
    base = assemble(n.over, ctx)
    repl′ = Dict{SQLNode, Symbol}()
    for ref in refs
        if @dissect(ref, over |> NameBound())
            repl′[ref] = base.repl[over]
        else
            repl′[ref] = base.repl[ref]
        end
    end
    Assemblage(base.clause, cols = base.cols, repl = repl′)
end

function assemble(n::DefineNode, refs, ctx)
    base = assemble(n.over, ctx)
    if !any(ref -> @dissect(ref, Get(name = name)) && name in keys(n.label_map), refs)
        return base
    end
    if !@dissect(base.clause, SELECT() || UNION())
        base_alias = nothing
        c = base.clause
    else
        base_alias = allocate_alias(ctx, n.over)
        c = FROM(AS(over = complete(base), name = base_alias))
    end
    subs = make_subs(base, base_alias)
    repl = Dict{SQLNode, Symbol}()
    trns = Pair{SQLNode, SQLClause}[]
    tr_cache = Dict{Symbol, SQLClause}()
    for ref in refs
        if @dissect(ref, nothing |> Get(name = name)) && name in keys(n.label_map)
            col = get!(tr_cache, name) do
                def = n.args[n.label_map[name]]
                translate(def, ctx, subs)
            end
            push!(trns, ref => col)
        else
            push!(trns, ref => subs[ref])
        end
    end
    repl, cols = make_repl_cols(trns)
    Assemblage(c, cols = cols, repl = repl)
end

assemble(::FromNothingNode, refs, ctx) =
    assemble(nothing, refs, ctx)

function unwrap_repl(a::Assemblage)
    repl′ = Dict{SQLNode, Symbol}()
    for (ref, name) in a.repl
        @dissect(ref, over |> NameBound()) || error()
        repl′[over] = name
    end
    Assemblage(a.clause, cols = a.cols, repl = repl′)
end

function assemble(n::FromReferenceNode, refs, ctx)
    (alias, a) = ctx.with_map[n.over]
    a = unwrap_repl(a)
    c = FROM(over = ID(alias))
    subs = make_subs(a, alias)
    trns = Pair{SQLNode, SQLClause}[]
    for ref in refs
        push!(trns, ref => subs[ref])
    end
    repl, cols = make_repl_cols(trns)
    return Assemblage(c, cols = cols, repl = repl)
end

function assemble(n::FromTableNode, refs, ctx)
    seen = Set{Symbol}()
    for ref in refs
        @dissect(ref, nothing |> Get(name = name)) && name in n.table.column_set || error()
        if !(name in seen)
            push!(seen, name)
        end
    end
    alias = allocate_alias(ctx, n.table.name)
    tbl = ID(over = n.table.schema, name = n.table.name)
    c = FROM(AS(over = tbl, name = alias))
    cols = OrderedDict{Symbol, SQLClause}()
    for col in n.table.columns
        col in seen || continue
        cols[col] = ID(over = alias, name = col)
    end
    repl = Dict{SQLNode, Symbol}()
    for ref in refs
        if @dissect(ref, nothing |> Get(name = name))
            repl[ref] = name
        end
    end
    Assemblage(c, cols = cols, repl = repl)
end

function assemble(n::GroupNode, refs, ctx)
    has_aggregates = any(ref -> @dissect(ref, Agg()), refs)
    if isempty(n.by) && !has_aggregates
        return assemble(nothing, refs, ctx)
    end
    base = assemble(n.over, ctx)
    if @dissect(base.clause, tail := nothing || FROM() || JOIN() || WHERE())
        base_alias = nothing
    else
        base_alias = allocate_alias(ctx, n.over)
        tail = FROM(AS(over = complete(base), name = base_alias))
    end
    subs = make_subs(base, base_alias)
    by = translate(n.by, ctx, subs)
    trns = Pair{SQLNode, SQLClause}[]
    for ref in refs
        if @dissect(ref, nothing |> Get(name = name))
            @assert name in keys(n.label_map)
            push!(trns, ref => by[n.label_map[name]])
        elseif @dissect(ref, nothing |> Agg(name = name))
            push!(trns, ref => translate(ref, ctx, subs))
        end
    end
    repl, cols = make_repl_cols(trns)
    @assert !isempty(cols)
    if has_aggregates
        c = GROUP(over = tail, by = by)
    else
        args = complete(cols)
        c = SELECT(over = tail, distinct = true, args = args)
        cols = OrderedDict{Symbol, SQLClause}([name => ID(name) for name in keys(cols)])
    end
    return Assemblage(c, cols = cols, repl = repl)
end

assemble(n::HighlightNode, refs, ctx) =
    assemble(n.over, ctx)

function assemble(n::IntBindNode, refs, ctx)
    vars′ = copy(ctx.vars)
    for (name, i) in n.label_map
        vars′[name] = translate(n.args[i], ctx)
    end
    ctx′ = TranslateContext(ctx, vars = vars′)
    assemble(n.over, ctx′)
end

function assemble(n::IntIterateNode, refs, ctx)
    ctx′ = TranslateContext(ctx, vars = Dict{Symbol, SQLClause}())
    base = unwrap_repl(assemble(n.over, ctx′))
    @assert @dissect(base.clause, FROM())
    subs = make_subs(base, nothing)
    trns = Pair{SQLNode, SQLClause}[]
    for ref in refs
        push!(trns, ref => subs[ref])
    end
    repl, cols = make_repl_cols(trns)
    Assemblage(base.clause, cols = cols, repl = repl)
end

function assemble(n::IntJoinNode, refs, ctx)
    left = assemble(n.over, ctx)
    if @dissect(left.clause, tail := FROM() || JOIN())
        left_alias = nothing
    else
        left_alias = allocate_alias(ctx, n.over)
        tail = FROM(AS(over = complete(left), name = left_alias))
    end
    lateral = !isempty(n.lateral)
    subs = make_subs(left, left_alias)
    if lateral
        right = assemble(n.joinee, TranslateContext(ctx, subs = subs))
    else
        right = assemble(n.joinee, ctx)
    end
    if @dissect(right.clause, (joinee := nothing |> ID() |> AS(name = right_alias)) |> FROM()) ||
       @dissect(right.clause, (joinee := nothing |> ID(name = right_alias)) |> FROM())
        for (ref, name) in right.repl
            subs[ref] = right.cols[name]
        end
    else
        right_alias = allocate_alias(ctx, n.joinee)
        joinee = AS(over = complete(right), name = right_alias)
        right_cache = Dict{Symbol, SQLClause}()
        for (ref, name) in right.repl
            subs[ref] = get(right_cache, name) do
                ID(over = right_alias, name = name)
            end
        end
    end
    on = translate(n.on, ctx, subs)
    c = JOIN(over = tail, joinee = joinee, on = on, left = n.left, right = n.right, lateral = lateral)
    trns = Pair{SQLNode, SQLClause}[]
    for ref in refs
        push!(trns, ref => subs[ref])
    end
    repl, cols = make_repl_cols(trns)
    Assemblage(c, cols = cols, repl = repl)
end

function assemble(n::KnotNode, refs, ctx)
    left = assemble(n.over, ctx)
    repl = Dict{SQLNode, Symbol}()
    dups = Dict{SQLNode, SQLNode}()
    seen = Dict{Symbol, SQLNode}()
    for ref in refs
        if @dissect(ref, over |> NameBound())
            name = left.repl[over]
            repl[ref] = name
            if name in keys(seen)
                dups[over] = seen[name]
            else
                seen[name] = over
            end
        else
            error()
        end
    end
    temp_union = Assemblage(left.clause, cols = left.cols, repl = repl)
    union_alias = allocate_alias(ctx, n.name)
    ctx.with_map[SQLNode(n.box)] = union_alias => temp_union
    right = unwrap_repl(assemble(n.iterator, ctx))
    urefs = SQLNode[]
    for ref in refs
        @dissect(ref, over |> NameBound()) || error()
        !(over in keys(dups)) || continue
        push!(urefs, over)
    end
    cs = SQLClause[]
    for (arg, a) in (n.over => left, n.iterator => right)
        if @dissect(a.clause, SELECT(args = args)) && aligned_columns(urefs, left.repl, args)
            push!(cs, a.clause)
            continue
        elseif !@dissect(a.clause, SELECT() || UNION())
            alias = nothing
            tail = a.clause
        else
            alias = allocate_alias(ctx, arg)
            tail = FROM(AS(over = complete(a), name = alias))
        end
        subs = make_subs(a, alias)
        cols = OrderedDict{Symbol, SQLClause}()
        for ref in urefs
            name = left.repl[ref]
            cols[name] = subs[ref]
        end
        c = SELECT(over = tail, args = complete(cols))
        push!(cs, c)
    end
    union_clause = UNION(over = cs[1], all = true, args = cs[2:end])
    cols = OrderedDict{Symbol, SQLClause}()
    for ref in urefs
        name = left.repl[ref]
        cols[name] = ID(name)
    end
    union = Assemblage(union_clause, cols = cols, repl = repl)
    ctx.with_map[SQLNode(n.box)] = union_alias => union
    ctx.recursive[] = true
    c = FROM(over = ID(union_alias))
    subs = make_subs(union, union_alias)
    trns = Pair{SQLNode, SQLClause}[]
    for ref in refs
        push!(trns, ref => subs[ref])
    end
    repl, cols = make_repl_cols(trns)
    return Assemblage(c, cols = cols, repl = repl)
end

function assemble(n::LimitNode, refs, ctx)
    base = assemble(n.over, ctx)
    if n.offset === nothing && n.limit === nothing
        return base
    end
    if @dissect(base.clause, tail := nothing || FROM() || JOIN() || WHERE() || GROUP() || HAVING() || ORDER())
        base_alias = nothing
    else
        base_alias = allocate_alias(ctx, n.over)
        tail = FROM(AS(over = complete(base), name = base_alias))
    end
    c = LIMIT(over = tail, offset = n.offset, limit = n.limit)
    subs = make_subs(base, base_alias)
    trns = Pair{SQLNode, SQLClause}[]
    for ref in refs
        push!(trns, ref => subs[ref])
    end
    repl, cols = make_repl_cols(trns)
    Assemblage(c, cols = cols, repl = repl)
end

function assemble(n::OrderNode, refs, ctx)
    base = assemble(n.over, ctx)
    if isempty(n.by)
        return base
    end
    if @dissect(base.clause, tail := nothing || FROM() || JOIN() || WHERE() || GROUP() || HAVING())
        base_alias = nothing
    else
        base_alias = allocate_alias(ctx, n.over)
        tail = FROM(AS(over = complete(base), name = base_alias))
    end
    subs = make_subs(base, base_alias)
    by = translate(n.by, ctx, subs)
    c = ORDER(over = tail, by = by)
    trns = Pair{SQLNode, SQLClause}[]
    for ref in refs
        push!(trns, ref => subs[ref])
    end
    repl, cols = make_repl_cols(trns)
    Assemblage(c, cols = cols, repl = repl)
end

function assemble(n::PartitionNode, refs, ctx)
    base = assemble(n.over, ctx)
    if !any(ref -> @dissect(ref, Agg()), refs)
        return base
    end
    if @dissect(base.clause, tail := nothing || FROM() || JOIN() || WHERE() || GROUP() || HAVING())
        base_alias = nothing
    else
        base_alias = allocate_alias(ctx, n.over)
        tail = FROM(AS(over = complete(base), name = base_alias))
    end
    c = WINDOW(over = tail, args = [])
    subs = make_subs(base, base_alias)
    ctx′ = TranslateContext(ctx, subs = subs)
    by = translate(n.by, ctx′)
    order_by = translate(n.order_by, ctx′)
    partition = PARTITION(by = by, order_by = order_by, frame = n.frame)
    trns = Pair{SQLNode, SQLClause}[]
    for ref in refs
        if @dissect(ref, nothing |> Agg(name = name))
            push!(trns, ref => partition |> translate(ref, ctx′))
        else
            push!(trns, ref => subs[ref])
        end
    end
    repl, cols = make_repl_cols(trns)
    Assemblage(c, cols = cols, repl = repl)
end

function assemble(n::SelectNode, refs, ctx)
    base = assemble(n.over, ctx)
    if !@dissect(base.clause, SELECT() || UNION())
        base_alias = nothing
        tail = base.clause
    else
        base_alias = allocate_alias(ctx, n.over)
        tail = FROM(AS(over = complete(base), name = base_alias))
    end
    subs = make_subs(base, base_alias)
    cols = OrderedDict{Symbol, SQLClause}()
    for (name, i) in n.label_map
        col = n.args[i]
        cols[name] = translate(col, ctx, subs)
    end
    c = SELECT(over = tail, args = complete(cols))
    cols = OrderedDict{Symbol, SQLClause}([name => ID(name) for name in keys(cols)])
    repl = Dict{SQLNode, Symbol}()
    for ref in refs
        @dissect(ref, nothing |> Get(name = name)) || error()
        repl[ref] = name
    end
    Assemblage(c, cols = cols, repl = repl)
end

function merge_conditions(c1, c2)
    if @dissect(c1, OP(name = :AND, args = args1))
        if @dissect(c2, OP(name = :AND, args = args2))
            return OP(:AND, args1..., args2...)
        else
            return OP(:AND, args1..., c2)
        end
    elseif @dissect(c2, OP(name = :AND, args = args2))
        return OP(:AND, c1, args2...)
    else
        return OP(:AND, c1, c2)
    end
end

function assemble(n::WhereNode, refs, ctx)
    base = assemble(n.over, ctx)
    if @dissect(base.clause, nothing || FROM() || JOIN() || WHERE() || HAVING()) ||
       @dissect(base.clause, GROUP(by = by)) && !isempty(by)
        subs = make_subs(base, nothing)
        condition = translate(n.condition, ctx, subs)
        if @dissect(condition, LIT(val = val)) && val === true
            return base
        end
        if @dissect(base.clause, tail |> WHERE(condition = tail_condition))
            condition = merge_conditions(tail_condition, condition)
            c = WHERE(over = tail, condition = condition)
        elseif @dissect(base.clause, GROUP())
            c = HAVING(over = base.clause, condition = condition)
        elseif @dissect(base.clause, tail |> HAVING(condition = tail_condition))
            condition = merge_conditions(tail_condition, condition)
            c = HAVING(over = tail, condition = condition)
        else
            c = WHERE(over = base.clause, condition = condition)
        end
    else
        base_alias = allocate_alias(ctx, n.over)
        tail = FROM(AS(over = complete(base), name = base_alias))
        subs = make_subs(base, base_alias)
        condition = translate(n.condition, ctx, subs)
        if @dissect(condition, LIT(val = val)) && val === true
            return base
        end
        c = WHERE(over = tail, condition = condition)
    end
    trns = Pair{SQLNode, SQLClause}[]
    for ref in refs
        push!(trns, ref => subs[ref])
    end
    repl, cols = make_repl_cols(trns)
    return Assemblage(c, cols = cols, repl = repl)
end

function assemble(n::WithNode, refs, ctx)
    ctx′ = TranslateContext(ctx, vars = Dict{Symbol, SQLClause}())
    for arg in n.args
        a = assemble(arg, ctx)
        alias = allocate_alias(ctx, arg)
        ctx.with_map[arg] = alias => a
    end
    assemble(n.over, ctx)
end


text:
using DAWG
using Test

l = ["aaa","aab","aac","aaaxx","nmj","mit"]
println("testing Sparse Matrix DAWG...")
smdawg = makeSparseMatrixDAWG(l)
olist = dictionaryMatch("aaaaac",smdawg)
println(olist)
@test length(olist) == 2
@test olist[1][1] == 1
@test olist[1][2] == 3
@test olist[2][1] == 4
@test olist[2][2] == 6

println("testing Double Array DAWG...")
dadawg = makeDoubleArrayDAWG(l)
olist = dictionaryMatch("aaaaac",dadawg)
println(olist)
@test length(olist) == 2
@test olist[1][1] == 1
@test olist[1][2] == 3
@test olist[2][1] == 4
@test olist[2][2] == 6

ext: jl


text:
# additional bigint functionality
using Base.GMP.MPZ
using Base.GMP.MPZ: gmpz, mpz_t

divexact!(x::BigInt, a::BigInt, b::BigInt) =
    (ccall((:__gmpz_divexact, :libgmp), Cvoid, (mpz_t, mpz_t, mpz_t), x, a, b); x)
divexact(a::BigInt, b::BigInt) = divexact!(BigInt(), a, b)
divexact!(a::BigInt, b::BigInt) = divexact!(a, a, b)

const TMP_BIG = BigInt(0)

function mul!(x::Rational{BigInt}, a::Rational{BigInt}, b::Rational{BigInt})
    MPZ.mul!(x.num, a.num, b.num)
    MPZ.mul!(x.den, a.den, b.den)
    g = MPZ.gcd!(TMP_BIG, x.num, x.den)
    divexact!(x.num, g)
    divexact!(x.den, g)
    return x
end


text:
import Base.convert

#= conversion between set types =#

# convert methods for identity (no-ops)
for T in subtypes(LazySet, true)
    @eval begin
        Base.convert(::Type{$T}, X::$T) = X
    end
end

"""
    convert(T::Type{HPOLYGON}, P::VPolygon) where {HPOLYGON<:AbstractHPolygon}

Converts a polygon in vertex representation to a polygon in constraint representation.

### Input

- `HPOLYGON` -- type used for dispatch
- `P`        -- polygon in vertex representation

### Output

A polygon in constraint representation.
"""
function convert(T::Type{HPOLYGON}, P::VPolygon) where {HPOLYGON<:AbstractHPolygon}
    return tohrep(P, T)
end

"""
    convert(::Type{HPOLYGON}, X::LazySet; [check_boundedness]::Bool=true) where {HPOLYGON<:AbstractHPolygon}

Converts a polyhedral set to a polygon in vertex representation.

### Input

- `PT` -- type used for dispatch
- `X`  -- set
- `check_boundedness` -- (optional, default `true`) if `true` check whether the
                         set `X` is bounded before creating the polygon

### Output

A polygon in constraint representation.

### Algorithm

We compute the list of constraints of `X`, then instantiate the polygon.
"""
function convert(::Type{HPOLYGON}, X::LazySet; check_boundedness::Bool=true) where {HPOLYGON<:AbstractHPolygon}
    @assert dim(X) == 2 "set must be two-dimensional for conversion, but it is of dimension $(dim(X))"
    PT = basetype(HPOLYGON)
    if check_boundedness && !isbounded(X)
        throw(ArgumentError("expected a bounded set for conversion to `HPolygon`"))
    end
    return PT(constraints_list(X))
end

"""
    convert(::Type{VPolygon}, P::AbstractHPolygon)

Converts a polygon in constraint representation to a polygon in vertex representation.

### Input

- `VPolygon` -- type used for dispatch
- `P`        -- polygon in constraint representation

### Output

A polygon in vertex representation.
"""
function convert(::Type{VPolygon}, P::AbstractHPolygon)
    return tovrep(P)
end

"""
    convert(::Type{HPolytope}, P::AbstractHPolygon)

Convert from polygon in H-representation to polytope in H-representation.

### Input

- `type` -- target type
- `P`    -- source polygon

### Output

The polygon represented as 2D polytope.
"""
function convert(::Type{HPolytope}, P::AbstractHPolygon)
    return HPolytope(P.constraints)
end

"""
    convert(::Type{VPolytope}, P::AbstractPolytope)

Convert polytopic type to polytope in V-representation.

### Input

- `type` -- target type
- `P`    -- source polytope

### Output

The set `P` represented as a `VPolytope`.
"""
function convert(::Type{VPolytope}, P::AbstractPolytope)
    return VPolytope(vertices_list(P))
end

"""
    convert(::Type{VPolygon}, P::AbstractPolytope)

Convert polytopic set to polygon in V-representation.

### Input

- `type` -- target type
- `P`    -- source polytope

### Output

The 2D polytope represented as a polygon.
"""
function convert(::Type{VPolygon}, P::AbstractPolytope)
    @assert dim(P) == 2 "polytope must be two-dimensional for conversion"
    return VPolygon(vertices_list(P))
end

"""
    convert(::Type{VPolygon}, X::LazySet)

Generic conversion to polygon in vertex representation.

### Input

- `type` -- target type
- `X`    -- set

### Output

The 2D set represented as a polygon.

### Algorithm

We compute the list of vertices of `X` and wrap the result in a polygon in
vertex representation, which guarantees that the vertices are sorted in
counter-clockwise fashion.
"""
function convert(::Type{VPolygon}, X::LazySet)
    @assert dim(X) == 2 "set must be two-dimensional for conversion"
    return VPolygon(vertices_list(X))
end

"""
    convert(::Type{HPolytope}, P::AbstractPolytope)

Convert a polytopic set to a polytope in H-representation.

### Input

- `type` -- target type
- `P`    -- source polytope

### Output

The given polytope represented as a polytope in constraint representation.

### Algorithm

First the list of constraints of `P` is computed, then the corresponding
`HPolytope` is created.
"""
function convert(::Type{HPolytope}, P::AbstractPolytope)
    return HPolytope(constraints_list(P))
end

"""
    convert(::Type{HPolyhedron}, P::AbstractPolytope)

Convert a polytopic set to a polyhedron in H-representation.

### Input

- `type` -- target type
- `P`    -- source polytope

### Output

The given polytope represented as a polyhedron in constraint representation.
"""
function convert(::Type{HPolyhedron}, P::AbstractPolytope)
    return HPolyhedron(constraints_list(P))
end

function convert(::Type{HPolyhedron}, X::AbstractPolyhedron) where {N}
    return HPolyhedron(constraints_list(X))
end

# conversion of a lazyset to a polyhedron with dense normal vectors
function convert(::Type{HPolyhedron{N, Vector{N}}}, X::AbstractPolyhedron) where {N}
    clist = constraints_list(X)
    return HPolyhedron([HalfSpace(Vector(c.a), c.b) for c in clist])
end

function convert(::Type{HPolyhedron}, X::LazySet)
    return HPolyhedron(constraints_list(X))
end

"""
    convert(::Type{HPolytope}, P::VPolytope)

Convert from polytope in V-representation to polytope in H-representation.

### Input

- `type` -- target type
- `P`    -- source polytope

### Output

The polytope in the dual representation.

### Algorithm

The `tohrep` function is invoked. It requires the `Polyhedra` package.
"""
function convert(::Type{HPolytope}, P::VPolytope)
    return tohrep(P)
end

function convert(::Type{HPolytope}, X::LazySet)
    return HPolytope(constraints_list(X))
end

"""
    convert(::Type{VPolytope}, X::LazySet; [prune]::Bool=true)

Generic conversion to polytope in vertex representation.

### Input

- `type`  -- target type
- `X`     -- set
- `prune` -- (optional, default: `true`) option to remove redundant vertices

### Output

The given set represented as a polytope in vertex representation.

### Algorithm

We compute the list of vertices of `X` and wrap the result in a polytope in
vertex representation, `VPolytope`. Use the option `prune` to select whether or not
to remove redundant vertices before constructing the polytope.
"""
function convert(::Type{VPolytope}, X::LazySet; prune::Bool=true)
    return VPolytope(vertices_list(X, prune=prune))
end

"""
    convert(::Type{VPolytope}, P::HPolytope)

Convert from polytope in H-representation to polytope in V-representation.

### Input

- `type` -- target type
- `P`    -- source polytope

### Output

The polytope in the dual representation.

### Algorithm

The `tovrep` function is invoked. It requires the `Polyhedra` package.
"""
function convert(::Type{VPolytope}, P::HPolytope)
    return tovrep(P)
end

"""
    convert(::Type{HPOLYGON}, P::HPolytope{N, VN};
            prune::Bool=true) where {N<:Real, VN<:AbstractVector{N}, HPOLYGON<:AbstractHPolygon}

Convert from 2D polytope in H-representation to polygon in H-representation.

### Input

- `type`  -- target type
- `P`     -- source polytope (must be 2D)
- `prune` -- (optional, default: `true`) flag for removing redundant
             constraints in the end
### Output

The 2D polytope represented as polygon.
"""
function convert(::Type{HPOLYGON}, P::HPolytope{N, VN};
                 prune::Bool=true) where {N<:Real, VN<:AbstractVector{N}, HPOLYGON<:AbstractHPolygon}
    @assert dim(P) == 2 "polytope must be two-dimensional for conversion"
    H = HPOLYGON(Vector{LinearConstraint{N, VN}}())
    for ci in constraints_list(P)
        addconstraint!(H, ci; prune=prune)
    end
    return H
end

# fast conversion from a 2D hyperrectangular set to a zonotope
function _convert_2D(::Type{Zonotope}, H::AbstractHyperrectangle{N}) where {N}
    c = center(H)
    rx = radius_hyperrectangle(H, 1)
    ry = radius_hyperrectangle(H, 2)
    G = _genmat_2D(c, rx, ry)
    return Zonotope(c, G)
end

@inline function _genmat_2D(c::AbstractVector{N}, rx, ry) where {N}
    flat_x = isapproxzero(rx)
    flat_y = isapproxzero(ry)
    ncols = !flat_x + !flat_y
    G = Matrix{N}(undef, 2, ncols)
    if !flat_x
        @inbounds begin G[1] = rx; G[2] = zero(N) end
        if !flat_y
            @inbounds begin G[3] = zero(N); G[4] = ry end
        end
    elseif !flat_y
        @inbounds begin G[1] = zero(N); G[2] = ry end
    end
    return G
end

function load_genmat_2D_static()
return quote
    @inline function _genmat_2D(c::SVector{L, N}, rx, ry) where {L, N}
        flat_x = isapproxzero(rx)
        flat_y = isapproxzero(ry)
        if !flat_x && !flat_y
            G = SMatrix{2, 2, N, 4}(rx, zero(N), zero(N), ry)
        elseif !flat_x && flat_y
            G = SMatrix{2, 1, N, 2}(rx, zero(N))
        elseif flat_x && !flat_y
            G = SMatrix{2, 1, N, 2}(zero(N), ry)
        else
            G = SMatrix{2, 0, N, 0}()
        end
        return G
    end

    # this function is type-stable but doesn't prune the generators according
    # to flat dimensions of H
    function _convert_2D_static(::Type{Zonotope}, H::AbstractHyperrectangle{N}) where {N}
        c = center(H)
        rx = radius_hyperrectangle(H, 1)
        ry = radius_hyperrectangle(H, 2)
        G = SMatrix{2, 2, N, 4}(rx, zero(N), zero(N), ry)
        return Zonotope(c, G)
    end

    function _convert_static(::Type{Zonotope}, H::Hyperrectangle{N, <:SVector, <:SVector}) where {N}
        return Zonotope(center(H), _genmat_static(H))
    end
end end  # quote / load_genmat_2D_static

function convert(::Type{Zonotope}, S::Singleton)
    return Zonotope(center(S), genmat(S))
end

"""
    convert(::Type{Zonotope}, Z::AbstractZonotope)

Converts a zonotopic set to a zonotope.

### Input

- `Zonotope` -- type, used for dispatch
- `H`        -- zonotopic set

### Output

A zonotope.
"""
function convert(::Type{Zonotope}, Z::AbstractZonotope)
    return _convert_zonotope_fallback(Z)
end

function convert(::Type{Zonotope}, H::AbstractHyperrectangle)
    dim(H) == 2 && return _convert_2D(Zonotope, H)
    return _convert_zonotope_fallback(H)
end

_convert_zonotope_fallback(Z) = Zonotope(center(Z), genmat(Z))

function convert(::Type{Singleton},
                 cp::CartesianProduct{N, S1, S2}) where {N, S1<:AbstractSingleton{N}, S2<:AbstractSingleton{N}}
    return Singleton(vcat(element(cp.X), element(cp.Y)))
end

"""
    convert(::Type{Zonotope}, cp::CartesianProduct{N, HN1, HN2}) where {N<:Real,
            HN1<:AbstractHyperrectangle{N}, HN2<:AbstractHyperrectangle{N}}

Converts the cartesian product of two hyperrectangular sets to a zonotope.

### Input

- `Zonotope` -- type, used for dispatch
- `cp`       -- cartesian product of two hyperrectangular sets

### Output

This method falls back to the conversion of the cartesian product to a single
hyperrectangle, and then from a hyperrectangle to a zonotope.
"""
function convert(::Type{Zonotope}, cp::CartesianProduct{N, HN1, HN2}
                ) where {N<:Real, HN1<:AbstractHyperrectangle{N},
                         HN2<:AbstractHyperrectangle{N}}
    return convert(Zonotope, convert(Hyperrectangle, cp))
end

"""
    convert(::Type{Zonotope}, cpa::CartesianProductArray{N, HN})
        where {N<:Real, HN<:AbstractHyperrectangle{N}}

Converts the cartesian product array of hyperrectangular sets to a zonotope.

### Input

- `Zonotope` -- type, used for dispatch
- `cpa`      -- cartesian product array of hyperrectangular sets

### Output

A zonotope.

### Algorithm

This method falls back to the conversion of the cartesian product to a single
hyperrectangle, and then from a hyperrectangle to a zonotope.
"""
function convert(::Type{Zonotope}, cpa::CartesianProductArray{N, HN}
                ) where {N<:Real, HN<:AbstractHyperrectangle{N}}
    return convert(Zonotope, convert(Hyperrectangle, cpa))
end

"""
    convert(::Type{Zonotope}, S::LinearMap{N, ZN}
           ) where {N, ZN<:AbstractZonotope{N}}

Converts the lazy linear map of a zonotopic set to a zonotope.

### Input

- `Zonotope` -- type, used for dispatch
- `S`        -- linear map of a zonotopic set

### Output

A zonotope.

### Algorithm

This method first applies the (concrete) linear map to the zonotopic set and
then converts the result to a `Zonotope` type.
"""
function convert(::Type{Zonotope}, S::LinearMap{N, ZN}
                ) where {N, ZN<:AbstractZonotope{N}}
    return convert(Zonotope, linear_map(S.M, S.X))
end

"""
    convert(::Type{Zonotope}, S::LinearMap{N, CartesianProduct{N, HN1, HN2}}
           ) where {N, HN1<:AbstractHyperrectangle{N},
                    HN2<:AbstractHyperrectangle{N}}

Converts the lazy linear map of the cartesian product of two hyperrectangular
sets to a zonotope.

### Input

- `Zonotope` -- type, used for dispatch
- `S`        -- linear map of the cartesian product of hyperrectangular sets

### Output

A zonotope.

### Algorithm

This method first converts the cartesian product to a zonotope, and then
applies the (concrete) linear map to the zonotope.
"""
function convert(::Type{Zonotope},
                 S::LinearMap{N, CartesianProduct{N, HN1, HN2}}
                ) where {N, HN1<:AbstractHyperrectangle{N},
                         HN2<:AbstractHyperrectangle{N}}
    return linear_map(S.M, convert(Zonotope, S.X))
end

"""
    convert(::Type{Zonotope},S::LinearMap{N, CartesianProductArray{N, HN}}
           ) where {N, HN<:AbstractHyperrectangle{N}}

Converts the lazy linear map of the cartesian product of a finite number of
hyperrectangular sets to a zonotope.

### Input

- `Zonotope` -- type, used for dispatch
- `S`        -- linear map of a `CartesianProductArray` of hyperrectangular sets

### Output

A zonotope.

### Algorithm

This method first converts the cartesian product array to a zonotope, and then
applies the (concrete) linear map to the zonotope.
"""
function convert(::Type{Zonotope}, S::LinearMap{N, CartesianProductArray{N, HN}}
                ) where {N, HN<:AbstractHyperrectangle{N}}
    return linear_map(S.M, convert(Zonotope, S.X))
end

"""
    convert(::Type{HPOLYGON}, S::AbstractSingleton{N}
           ) where {N<:Real, HPOLYGON<:AbstractHPolygon}

Convert from singleton to polygon in H-representation.

### Input

- `type` -- target type
- `S`    -- singleton

### Output

A polygon in constraint representation with the minimal number of constraints
(three).
"""
function convert(::Type{HPOLYGON}, S::AbstractSingleton{N}
                ) where {N<:Real, HPOLYGON<:AbstractHPolygon}
    constraints_list = Vector{LinearConstraint{N, Vector{N}}}(undef, 3)
    o = one(N)
    z = zero(N)
    v = element(S)
    constraints_list[1] = LinearConstraint([o, o], v[1] + v[2])
    constraints_list[2] = LinearConstraint([-o, z], -v[1])
    constraints_list[3] = LinearConstraint([z, -o], -v[2])
    return HPOLYGON(constraints_list)
end

"""
    convert(::Type{HPOLYGON}, L::LineSegment{N}
          ) where {N<:Real, HPOLYGON<:AbstractHPolygon}

Convert from line segment to polygon in H-representation.

### Input

- `type`  -- target type
- `L`     -- line segment
- `prune` -- (optional, default: `false`) flag for removing redundant
             constraints in the end
### Output

A flat polygon in constraint representation with the minimal number of
constraints (four).
"""
function convert(::Type{HPOLYGON}, L::LineSegment{N}) where {N<:Real, HPOLYGON<:AbstractHPolygon}
    H = HPOLYGON{N}()
    c = halfspace_left(L.p, L.q)
    addconstraint!(H, c; prune=false)
    addconstraint!(H, LinearConstraint(-c.a, -c.b); prune=false)
    line_dir = L.q - L.p
    c = LinearConstraint(line_dir, dot(L.q, line_dir))
    addconstraint!(H, c; prune=false)
    line_dir = -line_dir
    addconstraint!(H, LinearConstraint(line_dir, dot(L.p, line_dir)); prune=false)
    return H
end

"""
    convert(::Type{Hyperrectangle}, H::AbstractHyperrectangle)

Convert a hyperrectangular set to a hyperrectangle.

### Input

- `Hyperrectangle` -- hyperrectangle type, used for dispatch
- `H`              -- hyperrectangular set

### Output

A hyperrectangle.

### Examples

```jldoctest
julia> convert(Hyperrectangle, Interval(0.0, 1.0))
Hyperrectangle{Float64, Vector{Float64}, Vector{Float64}}([0.5], [0.5])
```
"""
function convert(::Type{Hyperrectangle}, H::AbstractHyperrectangle)
    return Hyperrectangle(center(H), radius_hyperrectangle(H))
end

"""
    convert(::Type{Interval}, H::AbstractHyperrectangle)

Converts a hyperrectangular set to an interval.

### Input

- `Interval` -- interval type, used for dispatch
- `H`        -- hyperrectangular set

### Output

An interval.

### Examples

```jldoctest
julia> convert(Interval, Hyperrectangle([0.5], [0.5]))
Interval{Float64, IntervalArithmetic.Interval{Float64}}([0, 1])
```
"""
function convert(::Type{Interval}, H::AbstractHyperrectangle)
    @assert dim(H) == 1 "can only convert a one-dimensional $(typeof(H)) to `Interval`"
    return Interval(low(H, 1), high(H, 1))
end

"""
    convert(::Type{Interval}, S::LazySet{N}) where {N<:Real}

Converts a convex set to an interval.

### Input

- `Interval` -- interval type, used for dispatch
- `S`        -- convex set

### Output

An interval.
"""
function convert(::Type{Interval}, S::LazySet{N}) where {N<:Real}
    @assert dim(S) == 1 "cannot convert a $(dim(S))-dimensional $(typeof(S)) to `Interval`"
    return Interval(-ρ(N[-1], S), ρ(N[1], S))
end

"""
    convert(::Type{Hyperrectangle},
            cpa::CartesianProductArray{N, HN}) where {N<:Real, HN<:AbstractHyperrectangle{N}}

Converts the cartesian product of a finite number of hyperrectangular sets to
a single hyperrectangle.

### Input

- `Hyperrectangle` -- type used for dispatch
- `S`              -- cartesian product array of hyperrectangular set

### Output

A hyperrectangle.

### Algorithm

This implementation uses the `center` and `radius_hyperrectangle` methods of
`AbstractHyperrectangle`.
"""
function convert(::Type{Hyperrectangle},
                 cpa::CartesianProductArray{N, HN}) where {N<:Real, HN<:AbstractHyperrectangle{N}}
     n = dim(cpa)
     c = Vector{N}(undef, n)
     r = Vector{N}(undef, n)
     i = 1
     @inbounds for block_set in array(cpa)
         j = i + dim(block_set) - 1
         c[i:j] = center(block_set)
         r[i:j] = radius_hyperrectangle(block_set)
         i = j + 1
     end
     return Hyperrectangle(c, r)
end

"""
    convert(::Type{Hyperrectangle},
            cp::CartesianProduct{N, HN1, HN2}) where {N<:Real, HN1<:AbstractHyperrectangle{N}, HN2<:AbstractHyperrectangle{N}}

Converts the cartesian product of two hyperrectangular sets to a single hyperrectangle.

### Input

- `Hyperrectangle` -- type used for dispatch
- `S`              -- cartesian product of two hyperrectangular sets

### Output

A hyperrectangle.

### Algorithm

The result is obtained by concatenating the center and radius of each hyperrectangle.
This implementation uses the `center` and `radius_hyperrectangle` methods of
`AbstractHyperrectangle`.
"""
function convert(::Type{Hyperrectangle},
                 cp::CartesianProduct{N, HN1, HN2}) where {N<:Real, HN1<:AbstractHyperrectangle{N}, HN2<:AbstractHyperrectangle{N}}
     X, Y = cp.X, cp.Y
     c = vcat(center(X), center(Y))
     r = vcat(radius_hyperrectangle(X), radius_hyperrectangle(Y))
     return Hyperrectangle(c, r)
end

"""
    convert(::Type{Hyperrectangle},
            cpa::CartesianProductArray{N, Interval{N}}) where {N<:Real}

Converts the cartesian product of a finite number of intervals to a single
hyperrectangle.

### Input

- `Hyperrectangle` -- type used for dispatch
- `S`              -- cartesian product array of intervals

### Output

A hyperrectangle.

### Algorithm

This implementation uses the `min` and `max` methods of `Interval` to reduce
the allocatons and improve performance (see LazySets#1143).
"""
function convert(::Type{Hyperrectangle},
                 cpa::CartesianProductArray{N, Interval{N}}) where {N<:Real}
     # since the sets are intervals, the dimension of cpa is its length
     n = length(array(cpa))
     l = Vector{N}(undef, n)
     h = Vector{N}(undef, n)
     @inbounds for (i, Ii) in enumerate(array(cpa))
         l[i] = min(Ii)
         h[i] = max(Ii)
     end
     return Hyperrectangle(low=l, high=h)
end

"""
    convert(::Type{CartesianProduct{N, Interval{N}, Interval{N}}},
            H::AbstractHyperrectangle{N}) where {N<:Real}

Converts a two-dimensional hyperrectangle to the cartesian product of two
intervals.

### Input

- `CartesianProduct` -- type used for dispatch
- `H`                -- hyperrectangle

### Output

The cartesian product of two intervals.
"""
function convert(::Type{CartesianProduct{N, Interval{N}, Interval{N}}},
                 H::AbstractHyperrectangle{N}) where {N<:Real}
    @assert dim(H) == 2 "the hyperrectangle must be two-dimensional to convert it to " *
            "the cartesian product of two intervals, but it is $(dim(H))-dimensional; " *
            "consider converting it to a 'CartesianProductArray{$N, Interval{$N}}' instead"
    Ix = Interval(low(H, 1), high(H, 1))
    Iy =  Interval(low(H, 2), high(H, 2))
    return CartesianProduct(Ix, Iy)
end

"""
    convert(::Type{CartesianProductArray{N, Interval{N}}},
            H::AbstractHyperrectangle{N}) where {N<:Real}

Converts a hyperrectangle to the cartesian product array of intervals.

### Input

- `CartesianProductArray` -- type used for dispatch
- `H`                     -- hyperrectangle

### Output

The cartesian product of a finite number of intervals.
"""
function convert(::Type{CartesianProductArray{N, Interval{N}}},
                 H::AbstractHyperrectangle{N}) where {N<:Real}
    Iarray = [Interval(low(H, i), high(H, i)) for i in 1:dim(H)]
    return CartesianProductArray(Iarray)
end

"""
    convert(::Type{Zonotope}, cp::CartesianProduct{N, ZN1, ZN2}
           ) where {N<:Real, ZN1<:AbstractZonotope{N}, ZN2<:AbstractZonotope{N}}

Converts the cartesian product of two zonotopes to a new zonotope.

### Input

- `Zonotope` -- type used for dispatch
- `S`        -- cartesian product of two zonotopes

### Output

A zonotope.

### Algorithm

The cartesian product is obtained by:

- Concatenating the centers of each input zonotope.
- Arranging the generators in block-diagional fashion, and filled with zeros
  in the off-diagonal; for this reason, the generator matrix of the returned
  zonotope is built as a sparse matrix.
"""
function convert(::Type{Zonotope}, cp::CartesianProduct{N, ZN1, ZN2}
                ) where {N<:Real, ZN1<:AbstractZonotope{N}, ZN2<:AbstractZonotope{N}}
    Z1, Z2 = cp.X, cp.Y
    c = vcat(center(Z1), center(Z2))
    G = blockdiag(sparse(genmat(Z1)), sparse(genmat(Z2)))
    return Zonotope(c, G)
end

"""
    convert(::Type{HPolytope}, H::AbstractHyperrectangle)

Converts a hyperrectangular set to a polytope in constraint representation.

### Input

- `HPolytope` -- type used for dispatch
- `H`         -- hyperrectangular set

### Output

A polytope in constraint representation.
"""
function convert(::Type{HPolytope},
                 H::AbstractHyperrectangle)
    return HPolytope(constraints_list(H))
end

"""
    convert(::Type{HPOLYGON}, H::AbstractHyperrectangle) where
        {HPOLYGON<:AbstractHPolygon}

Converts a hyperrectangular set to a polygon in constraint representation.

### Input

- `HPOLYGON`  -- type used for dispatch
- `H`         -- hyperrectangular set

### Output

A polygon in constraint representation.
"""
function convert(X::Type{HPOLYGON},
                 H::AbstractHyperrectangle) where {HPOLYGON<:AbstractHPolygon}
    @assert dim(H) == 2 "cannot convert a $(dim(H))-dimensional " *
        "hyperrectangle into a two-dimensional polygon"
    return HPOLYGON(constraints_list(H))
end

"""
    convert(::Type{IntervalArithmetic.Interval}, x::Interval)

Converts a `LazySets` interval to an `Interval` from `IntervalArithmetic`.

### Input

- `Interval` -- type used for dispatch, from `IntervalArithmetic`
- `x`        -- interval (`LazySets.Interval`)

### Output

An `IntervalArithmetic.Interval`.
"""
function convert(::Type{IntervalArithmetic.Interval}, x::Interval)
    return IntervalArithmetic.interval(min(x), max(x))
end

"""
    convert(::Type{Interval}, x::IntervalArithmetic.Interval)

Converts an `Interval` from `IntervalArithmetic` to an interval in `LazySets`.

### Input

- `Interval` -- type used for dispatch
- `x`        -- interval (`IntervalArithmetic.Interval`)

### Output

A `LazySets.Interval`.
"""
function convert(::Type{Interval}, x::IntervalArithmetic.Interval)
    return Interval(IntervalArithmetic.inf(x), IntervalArithmetic.sup(x))
end

"""
    convert(::Type{IntervalArithmetic.IntervalBox}, H::AbstractHyperrectangle)

Converts a hyperrectangular set to an `IntervalBox` from `IntervalArithmetic`.

### Input

- `IntervalBox` -- type used for dispatch
- `H`           -- hyperrectangular set

### Output

An `IntervalBox`.
"""
function convert(::Type{IntervalArithmetic.IntervalBox}, H::AbstractHyperrectangle)
    return IntervalArithmetic.IntervalBox(IntervalArithmetic.interval.(low(H), high(H)))
end

"""
    convert(::Type{Hyperrectangle}, IB::IntervalArithmetic.IntervalBox)

Converts an `IntervalBox` from `IntervalArithmetic` to a hyperrectangular set.

### Input

- `Hyperrectangle` -- type used for dispatch
- `IB`             -- interval box

### Output

A `Hyperrectangle`.

### Notes

`IntervalArithmetic.IntervalBox` uses *static* vectors to store each component
interval, hence the resulting `Hyperrectangle` has its center and radius represented
as a static vector (`SArray`).
"""
function convert(::Type{Hyperrectangle}, IB::IntervalArithmetic.IntervalBox)
    low_IB = IntervalArithmetic.inf.(IB)
    high_IB = IntervalArithmetic.sup.(IB)
    return Hyperrectangle(low=low_IB, high=high_IB)
end

"""
    convert(::Type{Hyperrectangle}, r::Rectification{N, AH})
        where {N<:Real, AH<:AbstractHyperrectangle{N}}

Converts a rectification of a hyperrectangle to a hyperrectangle.

### Input

- `Hyperrectangle` -- type used for dispatch
- `r`              -- rectification of a hyperrectangle

### Output

A `Hyperrectangle`.
"""
function convert(::Type{Hyperrectangle},
                 r::Rectification{N, AH}) where {N<:Real,
                                                 AH<:AbstractHyperrectangle{N}}
    return rectify(r.X)
end

"""
    convert(::Type{Interval},
            r::Rectification{N, IN}) where {N<:Real, IN<:Interval{N}}

Converts a rectification of an interval to an interval.

### Input

- `Interval` -- type used for dispatch
- `r`        -- rectification of an interval

### Output

An `Interval`.
"""
function convert(::Type{Interval},
                 r::Rectification{N, IN}) where {N<:Real, IN<:Interval{N}}
    return Interval(rectify([min(r.X), max(r.X)]))
end

"""
    convert(::Type{VPolytope},
            X::ConvexHullArray{N, Singleton{N, VT}}) where {N, VT}

Converts the convex hull array of singletons to a polytope in V-representation.

### Input

- `VPolytope` -- type used for dispatch
- `X`         -- convex hull array of singletons

### Output

A polytope in vertex representation.
"""
function convert(::Type{VPolytope},
                 X::ConvexHullArray{N, Singleton{N, VT}}) where {N, VT}
    return VPolytope(vertices_list(X))
end

"""
    convert(::Type{VPolygon},
            X::ConvexHullArray{N, Singleton{N, VT}}) where {N, VT}

Converts the convex hull array of singletons to a polygon in V-representation.

### Input

- `VPolygon`  -- type used for dispatch
- `X`         -- convex hull array of singletons

### Output

A polygon in vertex representation.
"""
function convert(::Type{VPolygon},
                 X::ConvexHullArray{N, Singleton{N, VT}}) where {N, VT}
    @assert dim(X) == 2
    return VPolygon(vertices_list(X))
end

"""
    convert(::Type{MinkowskiSumArray},
            X::MinkowskiSum{N, ST, MinkowskiSumArray{N, ST}}) where {N, ST}

Converts the Minkowski sum of a Minkowski sum array to a Minkowski sum array.

### Input

- `MinkowskiSumArray`  -- type used for dispatch
- `X`                  -- Minkowski sum of a Minkowski sum array

### Output

A Minkowski sum array.
"""
function convert(::Type{MinkowskiSumArray},
                 X::MinkowskiSum{N, ST, MinkowskiSumArray{N, ST}}) where {N, ST}
    return MinkowskiSumArray(vcat(X.X, X.Y.array))
end

"""
    convert(::Type{Interval}, x::MinkowskiSum{N, IT, IT}) where {N, IT<:Interval{N}}

Converts the Minkowski sum of two intervals into an interval.

### Input

- `Interval` -- type used for dispatch
- `x`        -- Minkowski sum of a pair of intervals

### Output

An interval.
"""
function convert(::Type{Interval}, x::MinkowskiSum{N, IT, IT}) where {N, IT<:Interval{N}}
    return minkowski_sum(x.X, x.Y)
end

function convert(::Type{HalfSpace{N, Vector{N}}}, hs::HalfSpace{N, <:AbstractVector{N}}) where {N}
    return HalfSpace(Vector(hs.a), hs.b)
end

function convert(::Type{Zonotope},
                 am::AbstractAffineMap{N, <:AbstractZonotope{N}}) where {N<:Real}
    Z1 = convert(Zonotope, linear_map(matrix(am), set(am)))
    translate!(Z1, vector(am))
    return Z1
end

"""
    convert(::Type{HParallelotope}, Z::AbstractZonotope{N}) where {N}

Converts a zonotopic set of order one into a parallelotope in constraint
representation.

### Input

- `HParallelotope` -- type used for dispatch
- `Z`              -- zonotopic set

### Output

A parallelotope in constraint representation.

### Notes

This function requires that the list of constraints of `Z` are obtained in
the particular order returned from the constraints list function of a `Zonotope`.
"""
function convert(::Type{HParallelotope}, Z::AbstractZonotope{N}) where {N}
    @assert order(Z) == 1 "cannot convert a zonotope that is not of order 1 to"*
                          " a parallelotope"
    n = dim(Z)

    Z = convert(Zonotope, Z)
    constraints = constraints_list(Z) # TODO refactor + use _constraints_list_zonotope

    D = Matrix{N}(undef, n, n)
    c = Vector{N}(undef, 2n)
    j = 1
    @inbounds for i in 1:n
        D[i, :] = constraints[j].a
        c[i] = constraints[j].b
        c[i+n] = constraints[j+1].b
        j += 2
    end
    return HParallelotope(D, c)
end

"""
    convert(::Type{Zonotope}, cp::CartesianProduct{N, AZ1, AZ2}) where
         {N, AZ1<:AbstractZonotope{N}, AZ2<:AbstractZonotope{N}}

Converts a cartesian product of two zonotopes into a zonotope.

### Input

- `Zonotope` -- type used for dispatch
- `cp`       -- cartesian product of two zonotopes

### Output

A zonotope.

### Notes

This implementation creates a `Zonotope` with sparse vector and matrix representation.
"""
function convert(::Type{Zonotope}, cp::CartesianProduct{N, AZ1, AZ2}) where
         {N, AZ1<:AbstractZonotope{N}, AZ2<:AbstractZonotope{N}}
    Z1, Z2 = cp.X, cp.Y
    c = vcat(center(Z1), center(Z2))
    G = blockdiag(sparse(genmat(Z1)), sparse(genmat(Z2)))
    return Zonotope(c, G)
end

"""
    convert(::Type{Zonotope}, cpa::CartesianProductArray{N, AZ})
        where {N, AZ<:AbstractZonotope{N}}

Converts a cartesian product array of zonotopes into a zonotope.

### Input

- `Zonotope` -- type used for dispatch
- `cpa`       -- cartesian product array of zonotopes

### Output

A zonotope.

### Notes

This function requires the use of `SparseArrays`.
"""
function convert(::Type{Zonotope}, cpa::CartesianProductArray{N, AZ}) where
        {N, AZ<:AbstractZonotope{N}}
    arr = array(cpa)
    c = reduce(vcat, center.(arr))
    G = reduce(blockdiag, sparse.(genmat.(arr)))
    return Zonotope(c, G)
end

convert(::Type{HPolytope}, P::HPolyhedron) = HPolytope(copy(constraints_list(P)))
convert(::Type{HPolyhedron}, P::HPolytope) = HPolyhedron(copy(constraints_list(P)))

for T in [HPolygon, HPolygonOpt, HPolytope, HPolyhedron]
@eval begin
    function convert(::Type{$T}, P::Intersection{N, S1, S2}) where {N, S1<:AbstractPolyhedron{N}, S2<:AbstractPolyhedron{N}}
        clist = vcat(constraints_list(P.X), constraints_list(P.Y))
        return ($T)(clist)
    end

    function convert(::Type{$T}, P::IntersectionArray{N, S}) where {N, S<:AbstractPolyhedron}
        clist = reduce(vcat, constraints_list.(array(P)))
        return ($T)(clist)
    end
end
end

"""
    convert(::Type{STAR}, P::AbstractPolyhedron{N}) where {N}

Converts a polyhedral set into a star set represented as a lazy affine map.

### Input

- `STAR` -- type used for dispatch
- `P`    -- polyhedral set

### Output

A star set.
"""
function convert(::Type{STAR}, P::AbstractPolyhedron{N}) where {N}
    n = dim(P)
    c = zeros(N, n)
    V = Matrix(one(N)*I, n, n)
    return AffineMap(V, P, c)
end

"""
    convert(::Type{STAR}, X::Star)

Converts a star set into its equivalent representation as a lazy affine map.

### Input

- `STAR` -- type used for dispatch
- `X`    -- star set

### Output

A star set.
"""
function convert(::Type{STAR}, X::Star)
    return AffineMap(X.V, X.P, X.c)
end

"""
    convert(::Type{Star}, P::AbstractPolyhedron{N}) where {N}

Converts a polyhedral set into a star set.

### Input

- `Star` -- type used for dispatch
- `P`    -- polyhedral set

### Output

A star set.
"""
function convert(::Type{Star}, P::AbstractPolyhedron{N}) where {N}
    n = dim(P)
    c = zeros(N, n)
    V = Matrix(one(N)*I, n, n)
    return Star(c, V, P)
end

function convert(::Type{Hyperplane}, P::HPolyhedron; skip_check::Bool=false)
    # check that the number of constraints is fine
    if !skip_check && !is_hyperplanar(P)
        throw(ArgumentError("the polyhedron is not hyperplanar: $P"))
    end

    # construct hyperplane from first constraint
    c1 = @inbounds first(constraints_list(P))
    return Hyperplane(c1.a, c1.b)
end


text:
# Generic Spiking Layer driving an HH layer

# verifies that identical stimulus presented to 2 disconnected cells produces exactly the same datas

using NeuralNets

N_stim = 100 # input dim
T = 300
dt = 0.01
time_trace = 0:dt:T
nsteps = length(time_trace)

net = SpikingLayersNet()

# create layers
P_L = add_layer!(net, SpikingLayer(SimpleSpikingNeuron,"P_L",100))
LGN_L = add_layer!(net, SpikingLayer(HHNeuron,"LGN_L",900))
c = p_lgn_connectivity(P_L.N, LGN_L.N, EXC, 3, false)
connect!(net, "P_L", "LGN_L", c)

# precompute image stimulus
spike_train = falses(N_stim,nsteps,3)
for i=1:N_stim
	input_freq = 30 + 10 * rand()
	ISI = int(round(1/input_freq * 1000/dt))# in steps
	spike_train[i,1:ISI:end,1] = true
end

stim_spikes = cell(length(net.l))
stim_spikes[1] = spike_train[:,:,1]
stim_spikes[2] = nothing
rs = RunSettings(T,stim_spikes)
out = runSpikingNet!(net,rs)

using PyPlot
include("../src/apma2821v/plotting.jl")
plot_all_rasters(out)
println("Press Enter to Continue...")
readline()


text:
using ISAtmosphere
using Test

@testset "ISAtmosphere.jl" begin
    @test T(9000.0, -1.5) ≈ 228.15 atol = 0.01
    @test T(13000.0, 0.0) ≈ 216.65 atol = 0.01
    @test T(13000) ≈ 216.65 atol = 0.01
    @test p(9000.0, -1.5) ≈ 30742.5 atol = 0.1
    @test p(13000.0, 0.0) ≈ 16510.4 atol = 0.1
    @test p(13000.0, 0) ≈ 16510.4 atol = 0.1
    @test ρ(30742.5, 228.15) ≈ 0.469414 atol = 0.0001
    @test ρ(16510.4, 216.65) ≈ 0.265483 atol = 0.0001
    @test ρ(16510, 217) ≈ 0.265049 atol = 0.0001
    @test a(228.15) ≈ 302.8 atol = 0.1
    @test a(216.65) ≈ 295.07 atol = 0.1
    @test a(217) ≈ 295.308 atol = 0.01

    @test Vcas2Vtas(128.611, p(9000.0), T(9000.0)) ≈ 201.01 atol = 0.1
    @test Vtas2Vcas(201.01, p(9000.0), T(9000.0)) ≈ 128.611 atol = 0.1
    @test Vtas2Vcas(201, p(9000.0), T(9000.0)) ≈ 128.611 atol = 0.1
    @test Vtas2M(201.01, T(9000.0)) ≈ 0.661667 atol = 0.001
    @test Vtas2M(201, T(9000.0)) ≈ 0.661667 atol = 0.001
    @test M2Vtas(0.661667, T(9000.0)) ≈ 201.01 atol = 0.1
    @test Vcas2M(128.611, p(9000.0), T(9000.0)) ≈ 0.661667 atol = 0.001
    @test M2Vcas(0.661667, p(9000.0), T(9000.0)) ≈ 128.611 atol = 0.1

    @test Hp_trans(133.756, 0.8) ≈ 11260.287 atol = 0.1
    @test Hp_trans(133.756, 0.6) ≈ 6952.80 atol = 0.1

    @test ISAtmosphere.θ(288) ≈ 0.999479 atol = 0.001
    @test ISAtmosphere.δ(101325) ≈ 1.000 atol = 0.001
    @test ISAtmosphere.σ(1) ≈ 0.816327 atol = 0.001

    cond = conditions(9000.0, -1.5)
    @test cond.T_K ≈ 228.15 atol = 0.01
    @test cond.p_Pa ≈ 30742.5 atol = 0.1
    @test cond.ρ_kg_m³ ≈ 0.469414 atol = 0.0001
    @test cond.a_m_s ≈ 302.8 atol = 0.1
end


text:
# make a synthetic projection
include("../src/analytic/gridrec.jl")
using TomoForward

img = zeros(128, 128, 2)
img[10:80, 20:110, 1:2] .= 1.0

nslice = size(img, 3)

nangles = 90
detcount = 196
# detcount = Int(floor(size(img,1)*1.4))
angles = Array(LinRange(0,pi,nangles+1)[1:nangles])
proj_geom = ProjGeom(1.0, detcount, angles)

A = fp_op_parallel2d_strip(proj_geom, size(img, 1), size(img, 2))

p = zeros(nangles, nslice, detcount)
for i=1:nslice
    p[:,i,:] = reshape(A * vec(img[:,:,i]), nangles, detcount)
end

@time rec_img = recon2d_gridrec(p, angles)

using PyPlot
imshow(rec_img[:,:,1])
#imshow(img[:,:,1])

max_stars_repo_name: JuliaTomo/DynamicTomographyWithFlow

max_issues_repo_name: JuliaTomo/DynamicTomographyWithFlow

max_forks_repo_name: JuliaTomo/DynamicTomographyWithFlow