isdisjoint_interval broken for multiple arguments

[Joel-Dahne]

We have

julia> isdisjoint_interval(interval(1, 2), interval(3, 4), interval(5, 6), interval(1, 2))
true

even though clearly the first and last interval are not disjoint. The documentation of the isdisjoint_interval function says

  isdisjoint_interval(x, y)

  Test whether x and y have no common elements.

It doesn't actually specify how multiple arguments are handled, but presumably it would return true if all of them are disjoint and false if any two of them overlap. This is how the three argument version works at least

julia> isdisjoint_interval(interval(1, 2), interval(3, 4), interval(1, 2))
false

The implementation

isdisjoint_interval(x, y, z, w...) = isdisjoint_interval(x, y) & isdisjoint_interval(x, z) & isdisjoint_interval(y, z, w...)

basically does a reduction using the pairwise version. It doesn't at any time compare x with any of the w... values. One could get a correct implementation by checking all possible pairs, proportional to n^2 if n is the number of arguments. It would be possible to do this is almost linear time if one first sorts the inputs and then checks pairwise disjointness, but I'm not sure one could do much better than that. I think the naive quadratic version would work fine here since one doesn't want to pass too many arguments to a Julia function either way.

[dpsanders]

I think this just shouldn't be defined for more than 2 intervals.

[OlivierHnt]

Thanks for reporting this issue. I think it's nice to define it for multiple inputs.
We could just do

IntervalArithmetic.isdisjoint_interval(x, y, z) = isdisjoint_interval(x, y) & isdisjoint_interval(x, z) & isdisjoint_interval(y, z)
IntervalArithmetic.isdisjoint_interval(x, y, z, w...) = isdisjoint_interval(x, y) & isdisjoint_interval(x, z) & isdisjoint_interval(x, w...) &  isdisjoint_interval(y, z, w...)

[OlivierHnt]

Or a less redundant version could be:

IntervalArithmetic.isdisjoint_interval(x, y, z, w...) = _isdisjoint_interval(x, y, z, w...)

_isdisjoint_interval(x) = true
_isdisjoint_interval(x, y) = isdisjoint_interval(x, y)
_isdisjoint_interval(x, y, z, w...) = _isdisjoint_interval(x, y) & _isdisjoint_interval(x, z) & _isdisjoint_interval(x, w...) & _isdisjoint_interval(y, z, w...)

[Joel-Dahne]

It would probably be beneficial to use && instead of & here, since otherwise it will always check all combinations even if the first one returns false.

If your goal is to minimize amount of code then defining only

IntervalArithmetic.isdisjoint_interval(x, y, z, w...) = isdisjoint_interval(x, y) && isdisjoint_interval(x, z, w...) && isdisjoint_interval(y, z, w...)

should suffice.

It might also be worthwhile to add a comment about the support for more than two arguments. This could be useful for other boolean functions like issubset_interval , isstrictsubset and isinterior as well.

[OlivierHnt]

If your goal is to minimize amount of code [...]

Not necessarily, just not something too involved.

It would probably be beneficial to use && instead of & here, since otherwise it will always check all combinations even if the first one returns false.

Nice catch

[lbenet]

As a side remark, and probably too late to add to the discussion, Julia allows for multiple comparissons. I think this issue is close to the behaviour of

julia> 1 == 2 == 1
false

both in the sense and the result. So I also think it is good to have those multiple comparissons, including the result.