How to separate joint and disjoint intervals from an interval vector?

General Usage
,
1

Hello,
I have a vector. Each element of the vector is a tuple that contains two elements, an interval, and a set of three intervals. I want to separate and take unions of those elements of the vector that contain an empty set in between. For example, I have a vector like-

9-element Vector{Any}:
 ([0, 2], ([100, 300], [1, 3], [10, 10]))
 ([2, 4], (∅, ∅, ∅))
 ([4, 6], (∅, ∅, ∅))
 ([6, 8], ([100, 300], [1, 3], [10, 10]))
 ([8, 10], ([100, 300], [1, 3], [10, 11]))
 ([10, 12], (∅, ∅, ∅))
 ([12, 14], (∅, ∅, ∅))
 ([14, 16], ([50, 252], [1.19, 3], [10, 10]))
 ([16, 18], ([100, 258], [1.16, 3], [10, 11]))

I want to get three IntervalBoxes, one is ([100, 300], [1, 3], [10, 10]), second is the union of a second tuple of 5th and 6th element of the vector, ([100, 300], [1, 3], [10, 11]), and third is a union of a second tuple of 8th and 9th elements of the vector, ([50, 258], [1.16, 3], [10, 11]). Could you please help me with how to do it using the ‘IntervalArithmetic.jl’ package?

Thank you in advance.

2

The criteria for grouping the intervals are not clear to me. Maybe something like this can help you


v=[
 ([0, 2], ([100, 300], [1, 3], [10, 10])),
 ([2, 4], (∅, ∅, ∅)),
 ([4, 6], (∅, ∅, ∅)),
 ([6, 8], ([100, 300], [1, 3], [10, 10])),
 ([8, 10], ([100, 300], [1, 3], [10, 11])),
 ([10, 12], (∅, ∅, ∅)),
 ([12, 14], (∅, ∅, ∅)),
 ([14, 16], ([50, 252], [1.19, 3], [10, 10])),
 ([16, 18], ([100, 258], [1.16, 3], [10, 11]))]

ne=filter(i-> ∅ ∉ i[2], v)
mrg(t1,t2)=[union(Interval.(zip(twint...)...)...) for twint in zip(t1,t2)]

i=1
while i<5
   if !isempty(intersect(Interval(ne[i][1]...),Interval(ne[i+1][1]...)))
      println(mrg(ne[i][2],ne[i+1][2]))
      i+=2
   else
      println(mrg(ne[i][2],ne[i][2]))
      i+=1
   end
end
3

Thank you @rocco_sprmnt21 but I am not able to get the correct output from the code.
Let me try to explain it again-
I have a vector containing a list of tuples. Each tuple contains two elements, an interval and a set of intervals.
In between 3rd and 6th tuples of the vector, there are two tuples whose 2nd elements are nonempty interval set, which are ([6, 8], ([100, 300], [1, 3], [10, 10])) and ([8, 10], ([100, 300], [1, 3], [10, 11])). So I will take the union of ([100, 300], [1, 3], [10, 10]) and ([100, 300], [1, 3], [10, 11]).

Similarly, after the first tuple of the vector, there is a tuple containing an empty interval set, so I will take the 2nd element of the first tuple as it is, that is ([100, 300], [1, 3], [10, 10]).

And, before the last two tuples, there is an empty interval so I will take a union of 2nd elements of the last two tuples, which are ([50, 252], [1.19, 3], [10, 10]) and ([100, 258], [1.16, 3], [10, 11]). In this way I will three interval sets, ([100, 300], [1, 3], [10, 10]), ([100, 300], [1, 3], [10, 11]), and ([50, 258], [1.16, 3], [10, 11]).
Could you please let me know if it is clear now?

4

I’ll start by saying that I don’t know the package used, but I would like to better understand why you think this is the most suitable structure to handle your problem.
Below I have structured my previous proposal better.
For the example provided, it seems to get the result you expected,.
My doubts concern whether your possible real situation has a more generic form that should be handled differently.
To explain myself better, I ask a couple of specific questions:

Are the sets of joint intervals only made up of 2 elements or can they also be 3 or more?

Is the vector of tuples containing an interval as the first element ordered in ascending order on this first element?

More generally, it would be better to understand what situation to manage in the most generic case possible.

Summary 
julia> using  IntervalArithmetic

julia> v=[
        ([0, 2], ([100, 300], [1, 3], [10, 10])),
        ([2, 4], (∅, ∅, ∅)),
        ([4, 6], (∅, ∅, ∅)),
        ([6, 8], ([100, 300], [1, 3], [10, 10])),
        ([8, 10], ([100, 300], [1, 3], [10, 11])),
        ([10, 12], (∅, ∅, ∅)),
        ([12, 14], (∅, ∅, ∅)),
        ([14, 16], ([50, 252], [1.19, 3], [10, 10])),
        ([16, 18], ([100, 258], [1.16, 3], [10, 11]))]
9-element Vector{Tuple{Vector{Int64}, Tuple{Any, Any, Any}}}:
 ([0, 2], ([100, 300], [1, 3], [10, 10]))
 ([2, 4], (∅, ∅, ∅))
 ([4, 6], (∅, ∅, ∅))
 ([6, 8], ([100, 300], [1, 3], [10, 10]))
 ([8, 10], ([100, 300], [1, 3], [10, 11]))
 ([10, 12], (∅, ∅, ∅))
 ([12, 14], (∅, ∅, ∅))
 ([14, 16], ([50, 252], [1.19, 3.0], [10, 10]))
 ([16, 18], ([100, 258], [1.16, 3.0], [10, 11]))

julia> ne=filter(i-> ∅ ∉ i[2], v)
5-element Vector{Tuple{Vector{Int64}, Tuple{Any, Any, Any}}}:
 ([0, 2], ([100, 300], [1, 3], [10, 10]))
 ([6, 8], ([100, 300], [1, 3], [10, 10]))
 ([8, 10], ([100, 300], [1, 3], [10, 11]))
 ([14, 16], ([50, 252], [1.19, 3.0], [10, 10]))
 ([16, 18], ([100, 258], [1.16, 3.0], [10, 11]))

julia> mrg(t1,t2)=[union(Interval.(zip(twint...)...)...) for twint in zip(t1,t2)]
mrg (generic function with 1 method)

julia> function sepdisj(ne)
          res=Vector{Interval{Float64}}[]
          i=1
          while i<5
             if !isempty(intersect(Interval(ne[i][1]...),Interval(ne[i+1][1]...)))
                push!(res,mrg(ne[i][2],ne[i+1][2]))
                i+=2
             else
                push!(res,mrg(ne[i][2],ne[i][2]))
                i+=1
             end
          end
          res
       end
sepdisj (generic function with 1 method)

julia> sepdisj(ne)
3-element Vector{Vector{Interval{Float64}}}:
 [[100, 300], [1, 3], [10, 10]]
 [[100, 300], [1, 3], [10, 11]]
 [[50, 258], [1.15999, 3], [10, 11]]
5

Dear @rocco_sprmnt21,

I am using only IntervalArithmetic.jl package.

Answers to your questions:
(I) Are the sets of joint intervals only made up of 2 elements or can they also be 3 or more?
-Yes, sets of joint intervals can be of any number; they can be of 100 elements also.

(II) Is the vector of tuples containing an interval as the first element ordered in ascending order on this first element?
-Yes.

6

A side note if you are using intervals frequently, is to use some of the JuliaIntervals packages:

People may not be aware of these efforts, so I am sharing them here.

1 Like
7

Is the following what you are expecting?

julia> using  IntervalArithmetic

julia> a=Interval(0,2)
[0, 2]

julia> b=Interval(3,4)
[3, 4]

julia> union(a,b)
[0, 4]

About the question (I), could you give a more genrale example?
(III) question: are the ‘keys’ intervals always contigous?

How do I determine the group of (3 or more) intervals to combine?
From the keys intervals that intersect or just from the fact that they (3 or more) are between two sets of empty intervals?

8 
julia> using  IntervalArithmetic

julia> v=[
        ([0, 2], ([100, 300], [1, 3], [10, 10])),
        ([2, 4], (∅, ∅, ∅)),
        ([4, 6], (∅, ∅, ∅)),
        ([6, 8], ([100, 300], [1, 3], [10, 10])),
        ([8, 10], ([100, 300], [1, 3], [10, 11])),
        ([10, 12], (∅, ∅, ∅)),
        ([12, 14], (∅, ∅, ∅)),
        ([14, 16], ([50, 252], [1.19, 3], [10, 10])),
        ([16, 18], ([100, 258], [1.16, 3], [10, 11]))]
...
julia> using IterTools

julia> grp=groupby(e-> e != (∅, ∅, ∅), last.(v))
IterTools.GroupBy{Vector{Tuple{Any, Any, Any}}, var"#45#46"}(var"#45#46"(), Tuple{Any, Any, Any}[([100, 300], [1, 3], [10, 10]), (∅, ∅, ∅), (∅, ∅, ∅), ([100, 300], [1, 3], [10, 10]), ([100, 300], [1, 3], [10, 11]), (∅, ∅, ∅), (∅, ∅, ∅), ([50, 252], [1.19, 3.0], [10, 10]), ([100, 258], [1.16, 3.0], [10, 11])])

julia> mrg(t1,t2)=[union(Interval.(zip(twint...)...)...) for twint in zip(t1,t2)]
mrg (generic function with 2 methods)

julia> mrg(t)=mrg(t,t)
mrg (generic function with 2 methods)

julia> map(g->reduce(mrg, g, init= mrg(g[1])), grp)
5-element Vector{Vector{Interval{Float64}}}:
 [[100, 300], [1, 3], [10, 10]]
 [∅, ∅, ∅]
 [[100, 300], [1, 3], [10, 10]]
 [∅, ∅, ∅]
 [[50, 252], [1.15999, 3], [10, 10]]
1 Like
9

Dear @rocco_sprmnt21,

(I) Could you give a more general example?
Answer: I will take a vector of only keys intervals,
v = [
([1, 3], [1, 3], [1, 2]),
(∅, ∅, ∅),
([2, 3], [1, 3], [1, 3]),
([8, 10], ([4, 5], [4, 5]),
([1, 2], [6, 7], [6, 9]),
(∅, ∅, ∅),
(∅, ∅, ∅),
([5, 6], [1, 3], [8, 9]),
([10, 25], [2, 7], [1, 1]),
(∅, ∅, ∅)
]

In this case, the output should be: 3 interval sets
(a) ([1, 3], [1, 3], [1, 2])
(b) hull(([2, 3], [1, 3], [1, 3]), ([8, 10], ([4, 5], [4, 5]), ([1, 2], [6, 7], [6, 9])) = ([1, 10], [1, 7], [1, 9])
(c) hull(([5, 6], [1, 3], [8, 9]), ([10, 25], [2, 7], [1, 1])) = ([5, 25], [1, 7], [1, 9])

(II) Are the ‘keys’ intervals always contiguous?
Answer: No, it is not necessary. ‘keys’ intervals will be either between the empty intervals or at the starting/end of the vector.

(III) How do I determine the group of (3 or more) intervals to combine?
Answer: They will be either between empty interval sets or at the beginning/end of the vector.

(IV) From the keys intervals that intersect or just from the fact that they (3 or more) are between two sets of empty intervals?
Answer: Keys interval may or may not intersect. Keys intervals (1 or 2 or 3 or more) are either between two sets of empty intervals or at the beginning/end of the vector.

10

try this and let us know

Summary 
julia> using IntervalArithmetic, IterTools

julia> v = [
       ([1, 3], [1, 3], [1, 2]),
       (∅, ∅, ∅),
       ([2, 3], [1, 3], [1, 3]),
       ([8, 10], [4, 5], [4, 5]),
       ([1, 2], [6, 7], [6, 9]),
       (∅, ∅, ∅),
       (∅, ∅, ∅),
       ([5, 6], [1, 3], [8, 9]),
       ([10, 25], [2, 7], [1, 1]),
       (∅, ∅, ∅)
       ]
10-element Vector{Tuple{Any, Any, Any}}:
 ([1, 3], [1, 3], [1, 2])
 (∅, ∅, ∅)
 ([2, 3], [1, 3], [1, 3])
 ([8, 10], [4, 5], [4, 5])
 ([1, 2], [6, 7], [6, 9])
 (∅, ∅, ∅)
 (∅, ∅, ∅)
 ([5, 6], [1, 3], [8, 9])
 ([10, 25], [2, 7], [1, 1])
 (∅, ∅, ∅)

julia> intv=[Base.splat(Interval).(e) for e in v]
10-element Vector{Tuple{Interval{Float64}, Interval{Float64}, Interval{Float64}}}:
 ([1, 3], [1, 3], [1, 2])
 (∅, ∅, ∅)
 ([2, 3], [1, 3], [1, 3])
 ([8, 10], [4, 5], [4, 5])
 ([1, 2], [6, 7], [6, 9])
 (∅, ∅, ∅)
 (∅, ∅, ∅)
 ([5, 6], [1, 3], [8, 9])
 ([10, 25], [2, 7], [1, 1])
 (∅, ∅, ∅)

julia> grp=groupby(e-> e != (∅, ∅, ∅), intv)
IterTools.GroupBy{Vector{Tuple{Interval{Float64}, Interval{Float64}, Interval{Float64}}}, var"#9#10"}(var"#9#10"(), Tuple{Interval{Float64}, Interval{Float64}, Interval{Float64}}[([1, 3], [1, 3], [1, 2]), (∅, ∅, ∅), ([2, 3], [1, 3], [1, 3]), ([8, 10], [4, 5], [4, 5]), ([1, 2], [6, 7], [6, 9]), (∅, ∅, ∅), (∅, ∅, ∅), ([5, 6], [1, 3], [8, 9]), ([10, 25], [2, 7], [1, 1]), (∅, ∅, ∅)])

julia> mrg(t1,t2)=[union(twint...) for twint in zip(t1,t2)]        
mrg (generic function with 1 method)

julia> map(g->reduce(mrg, g), grp)
6-element Vector{Vector{Interval{Float64}}}:
 [[1, 3], [1, 3], [1, 2]]
 [∅, ∅, ∅]
 [[1, 10], [1, 7], [1, 9]]
 [∅, ∅, ∅]
 [[5, 25], [1, 7], [1, 9]]
 [∅, ∅, ∅]

or


intv=[Base.splat(Interval).(e) for e in v]
grp=groupby(e-> e != (∅, ∅, ∅), intv)
bmrg(t1,t2)=Base.splat(union).(zip(t1,t2))
bmrg(t)=bmrg(t,t)
map(g->reduce(bmrg, g,init=g[1]),grp)

#or

intv=[Base.splat(Interval).(e) for e in v]
grp=groupby(e-> e != (∅, ∅, ∅), intv)
bmrg(t1,t2...)=bmrg(t1,bmrg(t2...))
bmrg(t1,t2)=Base.splat(hull).(zip(t1,t2))
bmrg(t)=bmrg(t,t)
Base.splat(bmrg).(grp)
11

I take this opportunity to ask if there is a way (or if there could be the theoretical line, in the sense that it is not an inconsistent thing) to do a sort of second level broadcasting (or more generally multilevel!?!?! ?).
That is, I mean a syntax similar to that of ‘.’ which in the following example replaces comphrension.

intv=[Base.splat(Interval).(e) for e in v]

like this !?!?!?!?

bbintv=Base.splat(Interval)..(v)
12

Whenever you want to change something within a structure, potentially nested – optics to the rescue! (:

julia> using Accessors

julia> v = [((1,2), (3,4)), ((5,6), (7,8))]
2-element Vector{Tuple{Tuple{Int64, Int64}, Tuple{Int64, Int64}}}:
 ((1, 2), (3, 4))
 ((5, 6), (7, 8))

# convert inner tuples to intervals:
julia> @modify(splat(Interval), v |> Elements() |> Elements())
2-element Vector{Tuple{ClosedInterval{Int64}, ClosedInterval{Int64}}}:
 (1 .. 2, 3 .. 4)
 (5 .. 6, 7 .. 8)

# neater syntax with AccessorsExtra:
julia> using AccessorsExtra

julia> @modify(splat(Interval), v[∗][∗])

# or even convert all real tuples no matter how nested they are:
julia> @modify(splat(Interval), v |> RecursiveOfType(NTuple{2,Real}))
2-element Vector{Tuple{ClosedInterval{Int64}, ClosedInterval{Int64}}}:
 (1 .. 2, 3 .. 4)
 (5 .. 6, 7 .. 8)
2 Likes
13

Thank you. I will take this into account on future occasions.
Among other things this

seems very close to what is ideally desired :grin::

bbintv=Base.splat(Interval)..(v)
14

Repeated dots seem better on the first glance (aside from the fact that .. is already used to create intervals, like 1..2). And such syntax may be useful for the simplest cases like here.
However, as long as you move from simple one-level map(f, x) / f.(x), it’s likely that in the majority of cases “multi-broadcast” won’t really help much. A basic example is

X = [(a=1, b=((1,2), (3,4))), (a=2, ...), ...]

where repeated broadcasting won’t let you apply f to each element of each b. But with optics it’s easy using the same syntax:

@modify(splat(Interval), v[∗].b[∗])

IME, multi-broadcast would have quite a small niche if it existed, probably that’s the reason why it doesn’t (:

1 Like
15

Dear @rocco_sprmnt21,

First of all, thank you so much for the help.

It is not working properly in my actual problem. In my problem, I should get [[100, 300], [1, 3], [10, 10]], [[100, 300], [1, 3], [10, 10]], [[100, 300], [1, 3], [10, 10]], three same sets, but should be separated. The code you provided is giving me only a single set [[100, 300], [1, 3], [10, 10]].

16

The script I proposed should respond to the following requirement, posted by you.

If you want to get a different result, write the expected output for these latter (more generic) sets of intervals

v = [
([1, 3], [1, 3], [1, 2]),
(∅, ∅, ∅),
([2, 3], [1, 3], [1, 3]),
([8, 10], ([4, 5], [4, 5]),
([1, 2], [6, 7], [6, 9]),
(∅, ∅, ∅),
(∅, ∅, ∅),
([5, 6], [1, 3], [8, 9]),
([10, 25], [2, 7], [1, 1]),
(∅, ∅, ∅)
]
17

Dear @rocco_sprmnt21,

Now, I am getting the expected result. I just rewritten the line grp=groupby(e-> e != (∅, ∅, ∅), intv) as grp=groupby(e-> e != IntervalBox(∅, ∅, ∅), intv) and I got the expected result.

Thank you so much for your kind help :slight_smile:

18

I’m glad you found a way to get what you’re looking for, but I’m still perplexed about what comes out by applying these changes to the groupby()

using IntervalArithmetic, IterTools
v = [
([1, 3], [1, 3], [1, 2]),
(∅, ∅, ∅),
([2, 3], [1, 3], [1, 3]),
([8, 10], ([4, 5], [4, 5]),
([1, 2], [6, 7], [6, 9]),
(∅, ∅, ∅),
(∅, ∅, ∅),
([5, 6], [1, 3], [8, 9]),
([10, 25], [2, 7], [1, 1]),
(∅, ∅, ∅)
]

intv=[Base.splat(Interval).(e) for e in v]
grp=groupby(e-> e != IntervalBox(∅, ∅, ∅), intv)
mrg(t1,t2)=[union(twint...) for twint in zip(t1,t2)]


julia> map(g->reduce(mrg, g,init=Base.splat(Interval).(g[1])), grp)
1-element Vector{Vector{Interval{Float64}}}:
 [[1, 25], [1, 7], [1, 9]]