Julia: searchsorted by applies by function to item being searched

[RauliRuohonen]

Consider this:

using Base.Dates: Second

immutable tsp # time series point
    t :: DateTime
    y :: Float64
end

t0 = now()
S = [tsp(t0+Second(10), 42), tsp(t0+Second(13), -1), tsp(t0+Second(17), 31)]

searchsortedfirst(S, t0+Second(12), by=x -> x.t)
searchsortedfirst(S, tsp(t0+Second(12), NaN), by=x -> x.t)

The first search call fails and the second is not ideal because one has to use a dummy value (NaN here) to fill in the parts of the item being searched that are not part of the key. I think that in searchsortedfirst(S, x, by=f) it would make more sense to apply f() to the items of _S_ but not to the item _x_. If the searchsorted functions worked like that, then the current behavior is easily obtained by using searchsortedfirst(S, f(x), by=f). Inversion of f() is not necessarily as easy.

[kmsquire]

I think that makes sense. Care to try fixing this and making a pull request? No worries if not.

[krcools]

I encountered the exact same problem in trying to find a column in a column-lex-sorted Matrix:

A = abs(rand(Int,3,7)) % 10
B = sortcols(A)
x = B[:,5]
searchsortedfirst(collect(1:7), x, by = i->B[:,i], lt = lexless)

This fails like the OP describes. The alternative is even more clumsy here as it would require the addition of an extra column containing the search target to B.

I don't have experience with pull request but am willing to look into it.

[RauliRuohonen]

This came up at https://github.com/JuliaLang/julia/issues/19295#issuecomment-259805716. I guess #19295 covers this now?

[haampie]

19295 is now closed, but this issue still exists.

Let me give another example where it is very annoying:

struct Coord{Tv}
  x::Tv
  y::Tv
end

norm2(p::Coord) = p.x * p.x + p.y * p.y

function function_from_another_package()
  ps = [Coord(randn(), randn()) for i = 1 : 10]
  I = sortperm(ps, by = norm2)
  return ps, I
end

function find_first_coord_outside_unit_circle()
  ps, I = function_from_another_package()

  # You can't pass the distance 1 as you'd expect
  searchsortedfirst(I, 1.0, by = i -> norm2(ps[i])) # nope...

  # You can't pass a coord on the unit circle either...
  searchsortedfirst(I, Coord(1.0, 0.0), by = i -> norm2(ps[i])) # nope...

  # The only solution seems to be the following -- but this 
  # requires me looking into the internals of searchsortedfirst
  searchsortedfirst(I, 1.0, lt = (p, q) -> norm2(ps[p]) < q)
end

[haampie]

I have a potential solution here: https://github.com/haampie/SortingSortingOut.jl#make-search-convenient----search-by-transformed-value-not-by-specific-vector-element

[tkf]

If we have #31553 (or any solution to #19198), I think we can just write searchsortedfirst((for f.(xs)), y).