interleaveby iterator

[ettersi]

Adds the following function:

imerge(a,b, predicate = <=, fa = identity, fb = identity)

Iterate over the union of a and b, merge-sort style.

Input:

• predicate(ak,bk) -> Bool: Whether to pick the next element of a (true) or b (false).
• fa(ak), fb(bk): Functions to apply to the picked elements

julia> collect(imerge(1:2:5, 2:2:6, <=, identity, x->-x))
6-element Vector{Int64}:
  1
 -2
  3
 -4
  5
 -6

---

This PR is based on https://github.com/JuliaCollections/IterTools.jl/pull/86, so ideally we merge that one first.

[ettersi]

Bump

[nsajko]

IMO the documentation should clearly define what this does, without referring to merge sort. Merging has its own Wikipedia page, separate from the one for merge sort, so it would also make sense to link to that: https://en.wikipedia.org/wiki/Merge_algorithm

Also, surely there's a better name for this than imerge? Something more self-documenting and more mnemonic?

[pepijndevos]

I have written something similar in the past and would really like something like this to get merged.

It seems to me the fa & fb are a bit extra, and would be better handled in a separate map step, no? What's the intended use for them?

IIRC my impl iterates over unique values. I also seem to remember trouble with type stability.

struct MergedAxis{A, B}
    a::A
    b::B
    dir::Int64 # 1 ascending, -1 descending
end
MergedAxis(a, b) = MergedAxis(a, b, 1)

Base.IteratorSize(::Core.Type{<:MergedAxis}) = Base.SizeUnknown()
Base.IteratorEltype(::Core.Type{<:MergedAxis}) = Base.EltypeUnknown()

struct Done end
const done = Done()
isdone(x) = false
isdone(x::Done) = true

function mergeiter((a, astate), oldastate, (b, bstate), oldbstate, dir)
    c = cmp(a, b)*dir
    if c==0
        (a, (astate, bstate))
    elseif c==1
        (b, (oldastate, bstate))
    elseif c==-1
        (a, (astate, oldbstate))
    end
end

function Base.iterate(ma::MergedAxis)
    Base.iterate(ma, (nothing, nothing))
end

#xmin(m::MergedAxis) = min(xmin(m.a), xmin(m.b))
#xmax(m::MergedAxis) = max(xmax(m.a), xmax(m.b))

function Base.iterate(ma::MergedAxis, (sa, sb))
    ita = if isdone(sa)
        nothing
    elseif isnothing(sa)
        Base.iterate(ma.a)  # Should Base. be used here?
    else
        Base.iterate(ma.a, sa)
    end
    itb = if isdone(sb)
        nothing
    elseif isnothing(sb)
        Base.iterate(ma.b)
    else
        Base.iterate(ma.b, sb)
    end
    if ita === nothing && itb === nothing
        return nothing
    elseif ita === nothing
        return itb[1], (done, itb[2])
    elseif itb === nothing
        return ita[1], (ita[2], done)
    end
    mergeiter(ita, sa, itb, sb, ma.dir)
end

function Iterators.reverse(it::MergedAxis)
    MergedAxis(Iterators.reverse(it.a), Iterators.reverse(it.b), -it.dir)
end

[codecov-commenter]

Codecov Report

Merging #87 (94e856d) into master (cf043fe) will increase coverage by 0.42%. The diff coverage is 93.33%.

@@            Coverage Diff             @@
##           master      #87      +/-   ##
==========================================
+ Coverage   90.73%   91.15%   +0.42%     
==========================================
  Files           1        1              
  Lines         313      328      +15     
==========================================
+ Hits          284      299      +15     
  Misses         29       29              

Impacted Files	Coverage Δ
src/IterTools.jl	91.15% <93.33%> (+0.42%)	:arrow_up:

:mega: We’re building smart automated test selection to slash your CI/CD build times. Learn more

[oxinabox]

I talked this design over with @pepijndevos and am happy to merge the version I just pushed, which I will do shortly.

As he suggested it drops the post-transform steps.

It also renames it. and defaults to lessthan