Implemented findall(in(interval), x::AbstractRange), fixes #52 by jagot · Pull Request #63 · JuliaMath/IntervalSets.jl

jagot · 2020-05-09T11:47:51Z

jagot · 2020-05-09T18:31:01Z

I realized I wanted to add the following function as well:

Base.findall(interval_d::Base.Fix2{typeof(in),Interval{L,R,T}}, x::AbstractArray)  where {L,R,T} =
    findall(v -> v ∈ interval_d.x, x)

but this breaks an ambiguity test:

IntervalSets: Test Failed at /Users/jagot/.julia/dev/IntervalSets/test/runtests.jl:27
  Expression: isempty(detect_ambiguities(IntervalSets, Base, Core))  
   Evaluated:
   isempty(Tuple{Method,Method}[(findall(interval_d::Base.Fix2{typeof(in),Interval{L,R,T}},
   x::AbstractArray) where {L, R, T} in IntervalSets at
   /Users/jagot/.julia/dev/IntervalSets/src/findall.jl:81,
   findall(p::Function, S::SparseArrays.AbstractSparseMatrixCSC) in
   SparseArrays at
   /Applications/Julia-1.4.app/Contents/Resources/julia/share/julia/stdlib/v1.4/SparseArrays/src/sparsematrix.jl:1400),
   (findall(interval_d::Base.Fix2{typeof(in),Interval{L,R,T}},
   x::AbstractArray) where {L, R, T} in IntervalSets at
   /Users/jagot/.julia/dev/IntervalSets/src/findall.jl:81,
   findall(p::Base.Fix2{typeof(in),T} where T,
   x::SparseArrays.AbstractSparseMatrixCSC) in SparseArrays at
   /Applications/Julia-1.4.app/Contents/Resources/julia/share/julia/stdlib/v1.4/SparseArrays/src/sparsematrix.jl:1419),
   (findall(interval_d::Base.Fix2{typeof(in),Interval{L,R,T}},
   x::AbstractArray) where {L, R, T} in IntervalSets at
   /Users/jagot/.julia/dev/IntervalSets/src/findall.jl:81,
   findall(p::Base.Fix2{typeof(in),T} where T,
   x::SparseArrays.SparseVector{#s662,Ti} where #s662) where Ti in
   SparseArrays at
   /Applications/Julia-1.4.app/Contents/Resources/julia/share/julia/stdlib/v1.4/SparseArrays/src/sparsevector.jl:733),
   (findall(interval_d::Base.Fix2{typeof(in),Interval{L,R,T}},
   x::AbstractArray) where {L, R, T} in IntervalSets at
   /Users/jagot/.julia/dev/IntervalSets/src/findall.jl:81,
   findall(p::Function, x::SparseArrays.SparseVector{#s662,Ti} where
   #s662) where Ti in SparseArrays at
   /Applications/Julia-1.4.app/Contents/Resources/julia/share/julia/stdlib/v1.4/SparseArrays/src/sparsevector.jl:709)])   
Stacktrace:
 [1] macro expansion at /Users/jagot/.julia/dev/IntervalSets/test/runtests.jl:27 [inlined]
 [2] macro expansion at /Users/julia/buildbot/worker/package_macos64/build/usr/share/julia/stdlib/v1.4/Test/src/Test.jl:1113 [inlined]
 [3] top-level scope at /Users/jagot/.julia/dev/IntervalSets/test/runtests.jl:24

The function seems to work as intended, so I'm not sure if the test should be amended, or what else.

EDIT: It's basically this ambiguity:

julia> x = sprand(5,3,0.5)
5×3 SparseMatrixCSC{Float64,Int64} with 12 stored entries:
  [1, 1]  =  0.00663687
  [2, 1]  =  0.0354308
  [4, 1]  =  0.205993
  [5, 1]  =  0.537299
  [1, 2]  =  0.882739
  [2, 2]  =  0.990146
  [4, 2]  =  0.331874
  [1, 3]  =  0.377636
  [2, 3]  =  0.203865
  [3, 3]  =  0.287234
  [4, 3]  =  0.839448
  [5, 3]  =  0.731989

julia> findall(in(0.3..0.9), x)
ERROR: MethodError: findall(::Base.Fix2{typeof(in),Interval{:closed,:closed,Float64}}, ::SparseMatrixCSC{Float64,Int64}) is ambiguous. Candidates:
  findall(p::Base.Fix2{typeof(in),T} where T, x::SparseArrays.AbstractSparseMatrixCSC) in SparseArrays at /Applications/Julia-1.4.app/Contents/Resources/julia/share/julia/stdlib/v1.4/SparseArrays/src/sparsematrix.jl:1419
  findall(interval_d::Base.Fix2{typeof(in),Interval{L,R,T}}, x::AbstractArray) where {L, R, T} in IntervalSets at /Users/jagot/.julia/dev/IntervalSets/src/findall.jl:81
  findall(p::Function, S::SparseArrays.AbstractSparseMatrixCSC) in SparseArrays at /Applications/Julia-1.4.app/Contents/Resources/julia/share/julia/stdlib/v1.4/SparseArrays/src/sparsematrix.jl:1400
  findall(pred::Base.Fix2{typeof(in),T} where T, x::Union{Tuple, AbstractArray}) in Base at array.jl:2322
Possible fix, define
  findall(::Base.Fix2{typeof(in),Interval{L,R,T}}, ::SparseArrays.AbstractSparseMatrixCSC) where {L, R, T}

dlfivefifty · 2020-05-09T19:08:26Z

Just fix the ambiguity?

mcabbott · 2020-05-09T19:08:39Z

That would be nice to have work, I was a bit surprised the default didn't just work. Here's where it goes, BTW:

findall(pred::Fix2{typeof(in)}, x::Union{AbstractArray, Tuple}) = _findin(x, pred.x)

function _findin(a::Union{AbstractArray, Tuple}, b)
    ind  = Vector{eltype(keys(a))}()
    bset = Set(b)
    @inbounds for (i,ai) in pairs(a)
        ai in bset && push!(ind, i)
    end
    ind
end

It's a little tempting to write Base.Set(i::Interval) = i... but you could overload _findin(a::Union{AbstractArray, Tuple}, b::Interval) to avoid having to depend on SparseArrays

…actArray)

jagot · 2020-05-17T09:10:45Z

Does this look good now?

test/findall.jl

jagot · 2020-05-17T11:17:32Z

~~@mcabbott @dlfivefifty Is it fine if I merge this and release as 0.5.1?~~

Scratch that, I think I found an edge case which is not working yet:

x = 0.0:0.02040816326530612:1.0
findall(in(Interval{:closed,:open}(1.0..1.0)), x)

gives a BoundsError. The example may seem contrived, but it appears in B-splines with clustered end-points.

dlfivefifty

Looks good, made one comment about Random.seed! and perhaps add some BigFloat tests, but I'm happy for it to be merged when you are, if no one else pipes up

test/findall.jl

jagot · 2020-05-18T17:54:16Z

I found I had already covered the corner case above in my B-spline code (🤦). Will probably cook up some BigFloat tests, de-duplicate the tests I have now and re-add @mcabbott's OffsetArrays examples.

jagot · 2020-05-19T08:44:22Z

Good catch with the BigFloats, there were indeed some corner cases for reverse ranges, that I think I've fixed now.

mcabbott · 2020-05-19T23:28:45Z

Many thanks for getting this done.

I just found another edge case, which I'm not really sure this ought to try to support, but anyway here it is:

julia> using IntervalSets                                          

julia> using Dates                                                 

julia> findall(in(Interval(Date(2020, 1, 8), Date(2020, 1, 22))), Date(2020):Week(1):Date(2021))                                      
ERROR: MethodError: no method matching isless(::Week, ::Int64)
Closest candidates are:
  isless(::Missing, ::Any) at missing.jl:87
  isless(::DoubleFloats.DoubleFloat{T}, ::Integer) where T<:Union{Float16, Float32, Float64} at /Users/me/.julia/packages/DoubleFloats/8fO4c/src/type/compare.jl:135
  isless(::AbstractFloat, ::Real) at operators.jl:158
  ...
Stacktrace:
 [1] <(::Week, ::Int64) at ./operators.jl:268
 [2] findall(::Base.Fix2{typeof(in),Interval{:closed,:closed,Date}}, ::StepRange{Date,Week}) at /Users/me/.julia/packages/IntervalSets/D282g/src/findall.jl:43

jagot · 2020-05-20T05:29:30Z

I don't think we should not support it, but I find myself unwilling to get into date semantics :)
However, it does seem as only some means of testing if a timespan is negative is required, this already works (to my astonishment):

julia> w = Week(1)
1 week

julia> cld(3w,2w)
2

jagot · 2020-06-01T11:14:14Z

@mcabbott I think this is fairly easy to fix, once JuliaLang/julia#36099 is taken care of:

    a,b = if δx < zero(δx)
        rev = findall(in(interval), reverse(x))
        isempty(rev) && return rev

        a = (il+ir)-last(rev)
        b = (il+ir)-first(rev)

        a,b
    else
        lx, rx = first(x), last(x)
        l = max(leftendpoint(interval), lx-one(δx))
        r = min(rightendpoint(interval), rx+one(δx))

        (l > rx || r < lx) && return 1:0

        a = il + max(0, round(Int, cld(l-lx, δx)))
        a += (a ≤ ir && (x[a] == l && L == :open || x[a] < l))

        b = min(ir, round(Int, cld(r-lx, δx)) + il)
        b -= (b ≥ il && (x[b] == r && R == :open || x[b] > r))

        a,b
    end

mcabbott · 2020-06-01T11:35:03Z

Thanks for digging, I haven't got back to this... although I think I was guilty of introducing the rx+1 in the first place!

Implemented findall(in(interval), x::AbstractRange), fixes #52

49065a1

Overload Base._findin to support Base.findall(in(::Interval), ::Abstr…

fac4797

…actArray)

mcabbott reviewed May 17, 2020

View reviewed changes

test/findall.jl Outdated Show resolved Hide resolved

Minor fix

e3449fa

dlfivefifty reviewed May 17, 2020

View reviewed changes

test/findall.jl Outdated Show resolved Hide resolved

Fixed some corner cases; set random seed

4e7c0ff

jagot added 4 commits May 19, 2020 09:30

Added tests for findall(in(::Interval), ::OffsetArray)

e6c29d2

Adapted some findall tests to Float32, Float64 & BigFloat

d1fa35d

Fixed issues with reverse ranges for BigFloats

277a16a

Test deduplication

09c104d

Final cleanup

39a3fd7

jagot merged commit 162bd0d into master May 19, 2020

mcabbott mentioned this pull request May 19, 2020

Replace findrange.jl with IntervalSets mcabbott/AxisKeys.jl#18

Merged

jagot mentioned this pull request Jun 1, 2020

findall for Date(Time) ranges #64

Closed

mcabbott mentioned this pull request Nov 22, 2020

Faster searchsorted methods for range and array inputs JuliaLang/julia#38527

Closed

jagot deleted the jagot/findall branch April 13, 2021 21:34

Conversation

jagot commented May 9, 2020

Uh oh!

jagot commented May 9, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dlfivefifty commented May 9, 2020

Uh oh!

mcabbott commented May 9, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

jagot commented May 17, 2020

Uh oh!

Uh oh!

jagot commented May 17, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

dlfivefifty left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

jagot commented May 18, 2020

Uh oh!

jagot commented May 19, 2020

Uh oh!

mcabbott commented May 19, 2020

Uh oh!

jagot commented May 20, 2020

Uh oh!

jagot commented Jun 1, 2020

Uh oh!

mcabbott commented Jun 1, 2020

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

jagot commented May 9, 2020 •

edited

Loading

mcabbott commented May 9, 2020 •

edited

Loading

jagot commented May 17, 2020 •

edited

Loading