Base.isless(u::AbstractInterval, v::AbstractInterval) may create confusing ordering for IntervalValue

[sambitdash]

Since, Base.isless(u::AbstractInterval, v::AbstractInterval) is defined, the same will propagate down to IntervalValue.

Technically, isequal(u, v) should be similar to !isless(u, v) && !isless(v, u).

But, isequal(u::IntervalValue, v::IntervalValue) will take into consideration the u.value and v.value parameters. This may lead to anomalous behavior in some cases. Like if you are using cmp(u, v) for example.

[sambitdash]

Closing as this is interval ordering and pure number ordering may not apply. This will be a case of partial ordering. I will reopen if I can prove otherwise.

[sambitdash]

This may be a bit of a details since I worked on it I will like to just write it down for future reference. The behavior as defined is correct and matches to Julia fallback of operators of 0.6 but not 0.7. Considering two intervals:

x = (a, b)
y = (c, d)

x < y => (a < c) || ( a == c && b < d)
y > x => (c > a) || ( c == a && d > b)

Hence: x < y <=> y > x as expected.

Now we want to see if:

x == y <=> !(x < y) && !(x > y)
       <=> !(x < y) && !(y < x)

!(x < y) <=> !((a < c) || ( a == c && b < d))
         <=> !(a < c) && !(a == c && b < d)
         <=> (c >= a) && (a != c || b >= d)
Similarly, 
!(y < x) <=> (a >= c) && (c != a || d >= b)

!(x < y) && !(y < x) <=> (a == c) && (b == d)

x == y <=> !(x < y) && !(y < x)

While mathematical trichotomy is preserved at an abstract type level in case of IntervalValue additional value parameter has to be considered as well and that may break the trichotomy as fallback for == is:

Base.(==) (x, y) = (x === y)

[sambitdash]

ec83e2a provides a detailed description of the problem. The solution provided was to convert every comparison where AbstractInterval{K} or its sub-types used is converted to a form of < than operator. However, maintaining this sanity across the life cycle of the module is not practical and can lead to future errors.

== and hash operator should be introduced that should ensure comparison of abstract type as well as concrete subtypes maintain mathematical trichotomy of lexicographic ordering.

I also tried to impress upon the Julia community to bring back the 0.6 behavior but it does not seem the community is really keen on that. Hence, reopening this bug.

https://discourse.julialang.org/t/behavior-of-when-isless-or-is-defined/10114/21

[sambitdash]

One last usecase in the code below (first(u) == first(v)) :

abstract type AbstractInterval{T} end

function basic_isless(u::AbstractInterval, v::AbstractInterval)
    return first(u) < first(v) || (first(u) == first(v) && last(u) < last(v))
end

function Base.isless(u::AbstractInterval, v::AbstractInterval)
    return basic_isless(u, v)
end

May fail if T is an abstract supertype, This is ok for most cases where isbits(T) == true which may be cases like built-in numbers.

it may be safer to write basic_isless as:

function basic_isless(u::AbstractInterval, v::AbstractInterval)
    return first(u) < first(v) || (!(first(v) < first(u)) && last(u) < last(v))
end

or expect the caller to implement == operator in the documentation for T along with <. Issue is < will not be defined so the caller will get error. But == will kind of fallback to === and there will not be any warnings but errors in runtime. I think this behavior will be in 0.6 as well.

[TransGirlCodes]

May fail if T is an abstract supertype, This is ok for most cases where isbits(T) == true which may be cases like built-in numbers.

Will it help things to restrict T in AbstractInterval{T} to be restricted to be T<:Real?

[sambitdash]

@benjward that will work for Integer types as well. As Integer <: Real. But is restrictive if you are going to use an abstract data as key. Say a Point or a person whose age could be the comparative quantity.

[sambitdash]

Give me all the words btw "aa" to "cd" in the English dictionary is a good interval example with String as key.

[dcjones]

The solution I'm inclined towards is to use custom comparison functions within the package.

That is, instead of defining Base.isless(::AbstractInterval, ::AbstractInterval), define some other functions, say interval_isless and interval_isequal and call those directly within IntervalTrees.

Upsides:

• Avoids the problem you've identified.
• The data structure won't be broken by an "incorrect" isless method.
• Potentially better performance. If a subtype of AbstractInterval has a more elaborate ordering, and thus a more expensive isless function, we can bypass it.

Downsides:

• the extra verbosity and annoyance of having to remember to use these interval comparisons and not the regular comparison operators in the interval tree code.
• IntervalTree won't respect a more elaborate ordering and only consider endpoints.

It's possible I'm overlooking some use case where it's important for the data structure to obey a custom ordering, but I think it's more trouble than it's worth, and we should just banish them.

I'm happy to go ahead and try this out. I want to do some tinkering anyway.

[TransGirlCodes]

@dcjones If you make a PR, can you make it to the version-1.0 branch?

I'm setting up version-1.0 branches across BioJulia packages to incorporate any julia version 0.7/1.0 related changes now and to drop julia 0.6. This is so as to encourage use of the latest julia, especially as it is the language hitting 1.0.