Intersect / Merge Ranges

Question

I am developing a programming language for which I want to provide a data type Range , which at the moment is, as usual, a list of value pairs int (x,y)with a restriction x < y. I’m not speaking as usual, because usually a range is just a couple, but in my case it’s more than what allows, for example, to have

1 to 5, 7 to 11, 13 to 22

all contained in one object.

I would like to provide two functions for creating a union and an increment of two ranges, which should contain the least number of non-overlapping intervals from a pair of ranges. for example

1 to 5 || 3 to 8 = 1 to 8
1 to 5 && 3 to 8 = 3 to 5
(1 to 3, 4 to 8) && 2 to 6 = (2 to 3, 4 to 6)

where ||is the union, and &&is the intersection.

Currently, their implementation, as indicated above, is a list. I know that there is a more suitable data structure (spanning tree), but for now I am more interested in creating new lists from the union / intersection of other lists ..

What are the modern algorithms for implementing these two functions?

Thanks in advance

Answer 1

Since you do not want to deal with interval trees and use only lists, I would suggest that you save the range representation as a list of disjoint intervals sorted by x coordinates.

, , , .

:

L1 L2:

L, .

x L1 L2 L.

, L , ( ) ( ) L , .

, L , x .

- .

Answer 2

, - - . , , , : tree1 tree2 . tree1, . / tree3, .

Answer 3

..... ... , " ":)

        (* "{ ... }" means "list" *)

function Union [{x1_,x2_},{y1_,y2_}] := 

      if {x1,x2}=={} then {x1,x2}={y1,y2} (* This is needed because the intersection *)
      if {y1,y2}=={} then {y1,y2}={x1,x2} (* may return an empty interval *)
                                          (* so, empty intervals need this code *)

      if {y1,y2}=={} then return[{}]      (* Both intervals were empty! *)

      if Min[x1,x2] > Min[y1,y2] 
      then   
          return[Union[{y1,y2},{x1,x2}]] (* or swap intervals *)
      else
          If Max[x1,x2] < Min[y1,y2]
          then                       (* Non Overlapping*)
              return[{{x1,x2},{y1,y2}}]
          else                       (* Overlapping intervals *)
              return[{Min[x1,x2],Max[x1,x2,y1,y2]}]

end function <Union>                      

function Intersection  [{x1_,x2_},{y1_,y2_}] := 

      if ({x1,x2}=={} OR {y1,y2}=={}) then return[{}] (* empty intervals do exist *)

      if Min[x1,x2] > Min[y1,y2]
      then   
          return[Intersection[{y1,y2},{x1,x2}]] (* or swap intervals *)
      else
          If Max[x1,x2] < Min[y1,y2]
          then                       (* Non Overlapping*)

              return[{}]             (* HERE we create an empty interval*)

          else                       (* Overlapping intervals *)

              return[{Min[y1,y2],Min[Max[x1,x2],Max[y1,y2]]}]

end function <Intersection>

a >

, n , .

- > ( )

        function GenUnion[{L:list of intervals}]:=

                 if (Tail[L] is interval)
                     return[Union[Head[L],Tail[L]]]
                 else                                                            
                     return[Union[Head[L], GenUnion[Head[Tail[L]],Tail[Tail[L]]]  

        end function <GenUnion>

Answer 4

, , .

, " ":

• ,
• , 1
• , 2
• , , 1

, .

, .

Answer 5

( ), , . , :

let rec calc c l1 l2 =
  match c,l1,l2 with                            
    None, (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 < f2 -> calc (Some (f1,t1)) y1 n2
    | None, n1, (f2,t2) :: y2 -> calc (Some (f2,t2)) n1 y2
    | None, _, _ -> []
    | (Some (fc,tc) as cur), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when t1 <= fc -> calc cur y1 n2
    | (Some (fc,tc) as cur), ((f1,t1) :: y1 as n1), (f2,t2) :: y2 when t2 <= fc -> calc cur n1 y2
    | Some (fc,tc), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 <= tc && t1 > fc -> calc (Some (fc,t1)) y1 n2
    | Some (fc,tc), ((f1,t1) :: y1 as n1), (f2,t2) :: y2 when f2 <= tc && t2 > fc -> calc (Some (fc,t2)) n1 y2
    | Some (fc,tc), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when f1 < f2 -> [fc,tc] @ calc (Some (f1,t1)) y1 n2
    | Some (fc,tc), (t :: e as n1), (f2,t2) :: y2 -> [fc,tc] @ calc (Some (f2,t2)) n1 y2
    | Some (fc,tc), [], (f,t) :: tr when f <= tc && t > tc -> calc (Some (fc,t)) [] tr
    | Some (fc,tc), [], (f,t) :: tr when f <= tc && t <= tc -> calc (Some (fc,tc)) [] tr
    | Some (fc,tc), [], x -> [fc,tc] @ x
    | Some (fc,tc), (f,t) :: tr, [] when f <= tc && t > tc -> calc (Some (fc,t)) tr []
    | Some (fc,tc), (f,t) :: tr, [] when f <= tc && t <= tc -> calc (Some (fc,tc)) tr []
    | Some (fc,tc), x, [] -> [fc,tc] @ x

c ( ), l1 l2 - int*int list.

, , c, l1 l2. :

(Some (fc,tc) as cur), (f1,t1) :: y1, ((f2,t2) :: y2 as n2) when t1 <= fc -> calc cur y1 n2

fc,tc, ( (f1,t1)::y1), , t1 <= fc, , cur, y1, , n2, , .

, , cur, cur .