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

**URL:** <https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422>\
**Category:** General Usage\
**Tags:** question\
**Created:** [May 6, 2023, 9:55pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422 "2023-05-06T21:55:04Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ashu](https://avatars.discourse-cdn.com/v4/letter/a/4bbf92/32.png) [@Ashu](https://discourse.julialang.org/u/Ashu)\
**Post date:** [May 6, 2023, 9:55pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/1 "2023-05-06T21:55:04Z")

</div>

Hello,

I have an interval vector of the form as

```julia
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

```julia
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)?

Thank you in advance

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [May 6, 2023, 10:06pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/2 "2023-05-06T22:06:13Z")

</div>

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] ]`.

```julia
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

```

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [May 7, 2023, 6:47am UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/3 "2023-05-07T06:47:33Z")

</div>

You could use [Home · Intervals.jl (invenia.github.io)](https://invenia.github.io/Intervals.jl/latest/#Sets-1) which has the `intersect` function for `IntervalSets` that returns a vector of intervals.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [May 7, 2023, 7:36am UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/4 "2023-05-07T07:36:19Z")

</div>

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}`?

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [May 7, 2023, 10:19am UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/5 "2023-05-07T10:19:23Z")

</div>

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

```julia

using IterTools

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

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

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

res=tuple.(ff,ll)

```

```julia

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

```

```julia
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))

```

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [May 7, 2023, 10:44am UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/6 "2023-05-07T10:44:25Z")

</div>

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

```julia
julia> using Intervals

julia> [Interval(v[1],v[2]) 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[1],v[2]) for v in X])
3-interval IntervalSet{Interval{Float64, Closed, Closed}}:
[0.0 .. 0.3]
[1.0 .. 3.0]
[9.0 .. 11.0]

```

> [@SteffenPL](#):
>
> has the `intersect` function

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

BTW:

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

```

Intervals seems very efficient.

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [May 7, 2023, 12:30pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/7 "2023-05-07T12:30:13Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [May 7, 2023, 12:40pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/8 "2023-05-07T12:40:22Z")

</div>

```julia
julia> @btime IntervalSet([Interval(v[1],v[2]) 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[1],v[2]) 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

---

<div class="post-metadata">

**Author:** ![Ashu](https://avatars.discourse-cdn.com/v4/letter/a/4bbf92/32.png) [@Ashu](https://discourse.julialang.org/u/Ashu)\
**Post date:** [May 7, 2023, 2:51pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/9 "2023-05-07T14:51:27Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![Ashu](https://avatars.discourse-cdn.com/v4/letter/a/4bbf92/32.png) [@Ashu](https://discourse.julialang.org/u/Ashu)\
**Post date:** [May 7, 2023, 2:59pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/10 "2023-05-07T14:59:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![denius](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/denius/32/3607_2.png) [@denius](https://discourse.julialang.org/u/denius)\
**Post date:** [May 7, 2023, 3:58pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/11 "2023-05-07T15:58:39Z")

</div>

There is also exist an [UnitRangesSortedSets.jl](https://github.com/denius/UnitRangesSortedSets.jl) with standard `union` and `intersect` operations.

---

<div class="post-metadata">

**Author:** ![lbenet](https://avatars.discourse-cdn.com/v4/letter/l/35a633/32.png) [@lbenet](https://discourse.julialang.org/u/lbenet)\
**Post date:** [May 7, 2023, 5:38pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/12 "2023-05-07T17:38:21Z")

</div>

You could do something like within IntervalArithemtic:

```julia
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]

```

---

<div class="post-metadata">

**Author:** ![Ashu](https://avatars.discourse-cdn.com/v4/letter/a/4bbf92/32.png) [@Ashu](https://discourse.julialang.org/u/Ashu)\
**Post date:** [May 7, 2023, 6:07pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/13 "2023-05-07T18:07:07Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [May 7, 2023, 8:50pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/14 "2023-05-07T20:50:18Z")

</div>

what should be the output for this X?

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

```

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [May 7, 2023, 9:17pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/15 "2023-05-07T21:17:19Z")

</div>

To demonstrate rocco\_sprmnt21’s point:

```julia
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] :(

```

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [May 7, 2023, 10:40pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/16 "2023-05-07T22:40:44Z")

</div>

Another option for ArithmeticIntervals package:

```julia
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
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]

```

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [May 8, 2023, 5:16am UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/17 "2023-05-08T05:16:05Z")

</div>

```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

```

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

---

<div class="post-metadata">

**Author:** ![Ashu](https://avatars.discourse-cdn.com/v4/letter/a/4bbf92/32.png) [@Ashu](https://discourse.julialang.org/u/Ashu)\
**Post date:** [May 9, 2023, 1:01pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/18 "2023-05-09T13:01:14Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [May 10, 2023, 2:26pm UTC](https://discourse.julialang.org/t/how-to-take-union-of-interval-elements-in-interval-vector/98422/19 "2023-05-10T14:26:57Z")

</div>

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.

```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

```

> **Summary**
>
> ```julia
> 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
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?