# How to take union of interval elements in Interval Vector?

Hello,

I have an interval vector of the form as

``````X = [ [0,0.1], [1,2], [0.1,0.2], [9,10], [2,3], [0.2,0.3], [10,11], [2,3], [9,10] ]
``````

I wish to get it in the form as

``````Y = [ [0,0.3], [1,3], [9,11] ]
``````

I am using the “IntervalArithmetic.jl” package.
In an actual case, there are 100s of such elements.
How can I get the union of interval elements which are continuous (the higher end point of one interval is the same as the lower end point of the second interval, e.g. [1,2] and [2,3] are continuous)?

What do you want to do with intervals that are inside another e.g. `[ [0, 3], [1, 2] ]` or partially overlap e.g. `[ [0, 2], [1, 3] ]`?

Assuming you just want unions, this is a straightforward way. However, bear in mind that the way you wrote X, it is promoted to `Vector{Vector{Float64}}`, that is all the integers become floats. You could try to change the type of `X` to contain `Vector{Int64}` too, but the code has to become more complicated to update intervals when int intervals and float intervals overlap e.g. `[ [0, 2], [1.2, 3.1] ]`.

``````function XtoY!(X) # sorts X in-place
Y = eltype(X)[]
# sort X in-place by inner vector's 1st element
sort!(X; by = function (x) x[begin] end)
# start Y with sorted X's 1st element
push!(Y, first(X))
for Xi in X
# extend end if interval overlaps
if Xi[begin] <= last(Y)[end]
last(Y)[end] = Xi[end]
else # add new interval to Y
push!(Y, Xi)
end
end
return Y
end
``````
1 Like

You could use Home · Intervals.jl (invenia.github.io) which has the `intersect` function for `IntervalSets` that returns a vector of intervals.

5 Likes

A vector does not seem like an appropriate data structure for representing intervals, since they do not structurally encode the information that an interval is described by exactly two numbers. Vectors are also inefficient.

Have you considered using an more lightweight and efficient data structure like `Tuple{Float64, Float64}`?

1 Like

It’s not meant to be an actual alternative to @Benny’s solution, but just an exercise on Julia’s functions

``````
using IterTools

X1=unique(sort(X, by=first))

ie(f,vi)=f.(f.(groupby(let s=[vi]; c-> s = c == last(s)  ? push!(s,c) : [c]  end, vi)))

ff=ie(first,X1)
ll=ie(last,X1)

res=tuple.(ff,ll)

``````
``````
reduce((s,c)-> c <=last(s) ? [s[1:end-1];[[s[end],c]]] : [s;[c]], sort(X, by=first),init=[X])

``````
``````using Base.Iterators
Xu=[-Inf; unique(sort(X,by=first));+Inf]

collect(partition(collect(flatten(Iterators.filter(x->first(x)< last(x),partition(flatten(Xu),2))))[2:end-1],2))

``````
1 Like

To make SteffenPL’s answer more explicit, here is some code:

``````julia> using Intervals

julia> [Interval(v,v) for v in X]
9-element Vector{Interval{Float64, Closed, Closed}}:
Interval{Float64, Closed, Closed}(0.0, 0.1)
Interval{Float64, Closed, Closed}(1.0, 2.0)
Interval{Float64, Closed, Closed}(0.1, 0.2)
Interval{Float64, Closed, Closed}(9.0, 10.0)
Interval{Float64, Closed, Closed}(2.0, 3.0)
Interval{Float64, Closed, Closed}(0.2, 0.3)
Interval{Float64, Closed, Closed}(10.0, 11.0)
Interval{Float64, Closed, Closed}(2.0, 3.0)
Interval{Float64, Closed, Closed}(9.0, 10.0)

julia> IntervalSet([Interval(v,v) for v in X])
3-interval IntervalSet{Interval{Float64, Closed, Closed}}:
[0.0 .. 0.3]
[1.0 .. 3.0]
[9.0 .. 11.0]
``````

`intersect` is useful, but why would it be needed here?

BTW:

``````julia> @btime IntervalSet([Interval(v,v) for v in \$X]);
70.044 ns (1 allocation: 208 bytes)
``````

Intervals seems very efficient.

5 Likes

Could you check something? I looked into the docs and source code, and the method that does the work seems to be `union!(intervals::IntervalSet)`. Interestingly, `union!`/`union` is not called in the `IntervalSet` constructor, but in the `Base.show` method for displaying `IntervalSet` in the REPL. Since trailing semicolons suppress REPL display, maybe your benchmark is not doing `union` at all. However, I’m not sure whether semicolons elide `show` or ignore it after its call. Could you benchmark a `union!` call and see if that changes things?

2 Likes
``````julia> @btime IntervalSet([Interval(v,v) for v in \$X])
70.460 ns (1 allocation: 208 bytes)
3-interval IntervalSet{Interval{Float64, Closed, Closed}}:
[0.0 .. 0.3]
[1.0 .. 3.0]
[9.0 .. 11.0]

julia> @btime union!(IntervalSet([Interval(v,v) for v in \$X]))
255.945 ns (2 allocations: 272 bytes)
3-interval IntervalSet{Interval{Float64, Closed, Closed}}:
[0.0 .. 0.3]
[1.0 .. 3.0]
[9.0 .. 11.0]
``````

Slower, but still efficient. Good observation @Benny

2 Likes

Dear @Benny

Thank you.

Yes, I want to do union with intervals that are inside another e.g. ` [ [0, 3], [1, 2] ]` or partially overlap e.g. `[ [0, 2], [1, 3] ]`.
Also, I am using “IntervalArithmetic.jl” package to solve my problem.

1 Like

Dear @Dan,

Thank you.

When I am using “Intervals.jl” with “IntervalArithmetic.jl” package, then my code is showing some errors, e.g. `..` and `mince` are not defined. I am using “IntervalArithmetic.jl” package in my algorithm. Can’t we use both packages together?

Thank you

There is also exist an UnitRangesSortedSets.jl with standard `union` and `intersect` operations.

1 Like

You could do something like within IntervalArithemtic:

``````julia> using IntervalArithmetic

julia> X = [Interval(0.0, 0.1), Interval(1,2), Interval(0.1, 0.2), Interval(9,10), Interval(2,3), Interval(0.2, 0.3), Interval(10,11), Interval(2,3), Interval(9,10)];

julia> XY = Set{Interval{Float64}}()
Set{Interval{Float64}}()

julia> for x in X
any(x .⊆ XY) && continue
for y in X
(x == y || isempty(x ∩ y)) && continue
x = hull(x, y)
end
push!(XY, x)
end

julia> XY
Set{Interval{Float64}} with 3 elements:
[0, 0.3]
[1, 3]
[9, 11]
``````
2 Likes

Thank you so much @lbenet. This solution worked really well for my problem.

1 Like

what should be the output for this X?

``````X1= [Interval(1,2), Interval(0.1, 0.2),  Interval(0.0, 0.1),   Interval(0.3,0.4), Interval(0.2, 0.3)]
``````
2 Likes

To demonstrate rocco_sprmnt21’s point:

``````julia> X= [Interval(1, 2),  Interval(3,4), Interval(2, 3)];

julia> XY = Set{Interval{Float64}}();

julia> for x in X
any(x .⊆ XY) && continue
for y in X
(x == y || isempty(x ∩ y)) && continue
x = hull(x, y)
end
push!(XY, x)
end

julia> XY
Set{Interval{Float64}} with 2 elements:
[1, 3]
[2, 4] :(
``````
2 Likes

Another option for ArithmeticIntervals package:

``````function mergeclosed(X)
b=-1
r=Interval[]
foldl(sort!([[(x,-1) for x in inf.(X)];
[(x,1) for x in sup.(X)]]); init=0) do s,(p,e)
s==0 && (b = p)
s=s+e
s==0 && push!(r,Interval(b,p))
s
end
r
end
``````

Example:

``````julia> X = [Interval(0.0, 0.1), Interval(1,2), Interval(0.1, 0.2), Interval(9,10), Interval(2,3), Interval(0.2, 0.3), Interval(10,11), Interval(2,3), Interval(9,10)]
9-element Vector{Interval{Float64}}:
[0, 0.100001]
[1, 2]
[0.1, 0.200001]
[9, 10]
[2, 3]
[0.2, 0.3]
[10, 11]
[2, 3]
[9, 10]

julia> mergeclosed(X)
3-element Vector{Interval}:
[0, 0.3]
[1, 3]
[9, 11]
``````
``````
function hullify(X)
XY = Set{Interval{Float64}}()
for x in X
any(x .⊆ XY) && continue
for y in X
(x == y || isempty(x ∩ y)) && continue
x = hull(x, y)
end
push!(XY, x)
end
XY==X && return XY
hullify(XY)
end
``````

PS
Convergence should be ensured by the fact that at each step the length of X decreases by 1, eventually reaching 1.

1 Like

Thank you so much @rocco_sprmnt21. It’s really helpful.

This function (not thoroughly tested) should be more efficient as it avoids the second for loop nested in the first and takes advantage of recursion, which would be necessary anyway.

``````function hullify1(X)
XY = Vector{Interval{Float64}}()
push!(XY,first(X))
for y in X[2:end]
h=findfirst(e->!isempty(e ∩ y),XY)
if isnothing(h)
push!(XY,y)
else
XY[h]=hull(XY[h],y)
end
end
#println(XY)
XY==X && return XY
hullify1(XY)
end

``````
Summary
``````julia> using IntervalArithmetic, BenchmarkTools

julia> X = [Interval(0.0, 0.1), Interval(1,2), Interval(0.1, 0.2), Interval(9,10), Interval(2,3), Interval(0.2, 0.3), Interval(10,11), Interval(2,3), Interval(9,10)];

julia> function hullify1(X)
XY = Vector{Interval{Float64}}()
push!(XY,first(X))
for y in X[2:end]
h=findfirst(e->!isempty(e ∩ y),XY)
if isnothing(h)
push!(XY,y)
else
XY[h]=hull(XY[h],y)
end
end
#println(XY)
XY==X && return XY
hullify1(XY)
end
hullify1 (generic function with 1 method)

julia> function hullify(X)
XY = Set{Interval{Float64}}()
for x in X
any(x .⊆ XY) && continue
for y in X
(x == y || isempty(x ∩ y)) && continue
x = hull(x, y)
end
push!(XY, x)
end
XY==X && return XY
hullify(XY)
end
hullify (generic function with 1 method)
``````
``````julia> X = [Interval(0.0, 0.1), Interval(1,2), Interval(0.1, 0.2), Interval(9,10), Interval(2,3), Interval(0.2, 0.3), Interval(10,11), Interval(2,3), Interval(9,10)];

julia> @btime hullify(X)
1.610 μs (45 allocations: 3.31 KiB)
Set{Interval{Float64}} with 3 elements:
[0, 0.3]
[1, 3]
[9, 11]

julia> @btime hullify1(X)
371.717 ns (6 allocations: 704 bytes)
3-element Vector{Interval{Float64}}:
[0, 0.3]
[1, 3]
[9, 11]
``````

In fact, the version that uses only one level of for loops is faster.
PS
Does anyone have any idea why the print on the REPL in the second case has those weird indentations?