Пересечение/объединение диапазонов

Поскольку вы не хотите иметь дело с деревьями интервалов и использовать только списки, я бы посоветовал вам сохранить представление диапазона в виде списка непересекающихся интервалов, отсортированных по координатам x.

Имея два списка, вы можете вычислить объединение и пересечение, выполнив своего рода шаг слияния, как мы делаем при слиянии отсортированных списков.

Пример:

Для объединения L1 и L2:

Создайте L как пустой список.

Возьмите интервал с наименьшим x из L1 и L2 и положите на L.

Теперь снова возьмите наименьший, сравните с последним элементом L и решите, нужно ли их объединить (если они перекрываются) или добавить новый интервал (если они не перекрываются) в конце L и продолжить обработку, как мы делаем в объединение двух отсортированных списков.

Когда вы закончите, L будет объединением, интервалы которого отсортированы по x и не пересекаются.

Для пересечения вы можете сделать что-то подобное.

Мне кажется, что лучший способ хранения интервалов — деревья интервалов — это еще и средства для выполнения над ними операций. Поскольку выполнение пересечений дерева точек является основным случаем, поддерживаемым запросом дерева интервалов, не кажется слишком сложным распространить это на пересечение интервалов: для каждого интервала в tree1 запросите tree2 для обеих конечных точек. Для пересечения вычтите пересекающийся интервал из tree1, а для объединения добавьте пересекающийся интервал. Для каждой операции вычитания/добавления вы получите новый набор интервалов для добавления к вашему новому tree3, который в конечном итоге станет результатом вашей операции.

Без деревьев интервалов..... Никакого специального заказа не нужно... Наверное, не "современно" :)

        (* "{ ... }" 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>

Изменить>

Возможно, обобщение на 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>

Я собираюсь предположить, что каждый диапазон сам по себе не перекрывается, минимален и упорядочен.

Если это так, вы можете просто «заархивировать» их:

1. Возьмите интервал, который начинается раньше
2. Если следующий интервал из диапазона other начинается после окончания этого, выведите этот интервал и перейдите к 1
3. Если следующий интервал из диапазона other заканчивается раньше этого, отбросить этот другой интервал и перейти к шагу 2.
4. Установить начало другого интервала равным началу этого, отбросить этот интервал и перейти к 1

После этого вы можете просмотреть и объединить соседние интервалы, если это необходимо.

Могут быть доступны некоторые незначительные оптимизации, но это в основном реализует операцию объединения и должно показать общий процесс реализации пересечения.

Пока я опубликую свою собственную реализацию (просто операция объединения), я использую функциональный язык, поэтому будьте осторожны... это может сбивать с толку:

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 как элемент окончательного ответа и начинаю снова с пустого.