сравнение двух диапазонов, которые могут иметь или не иметь границы

Question

Проблема довольно проста, но очень сложно найти решение, которое не состоит из сотен строк sphagetti else-ifs.

Есть 2 диапазона, которые могут иметь или не иметь границы,если есть границы, они могут быть включительными или нет.

псевдокод:

struct bound
{
    float val
    bool inclusive
}

struct range
{
    optional<bound> lower_bound
    optional<bound> upper_bound
}

Например, <3, 5] (числа> 3 и <= 5) будут <code>range: { lower_bound: {3, false}, upper_bound: {5, true} } и [8, (числа> = 8) будет range: { lower_bound: { 8, true }, upper_bound: null }

Для двух диапазонов определите отношение первого диапазона ко второму (идентичный, подмножество, супернабор, пересекаются, не пересекаются) (приведенные выше примеры диапазонов не пересекаются, поскольку ни одно из значений не может быть одновременно <= 5 и> = 8)

enum relation { identical, subset, superset, intersect, disjoint }

relation_first_to_second(range first, range second): relation
{
     // ???
}

Проблема заключается в том, что при написании функции необходимо соблюдать осторожность для обработки всех возможных угловых случаев.сделал примерную диаграмму, которая демонстрирует эти случаи (- означает, что границы отсутствуют).Мы можем предположить, что диапазоны всегда действительны сами по себе, другими словами, мы можем предположить, что (если они существуют) A всегда меньше или равно B, а X всегда меньше или равно Y (но мы не можем предполагать связь между: A /ХА / Yb / ВР / У).

lower upper   lower upper   relation first to second
  -     -       -     -      identical
  -     -       -     Y      superset
  -     -       X     -      superset
  -     -       X     Y      superset
  -     B       -     -      subset
  -     B       -     Y      B=Y: identical, B<Y: subset, B>Y superset
  -     B       X     -      B<X: disjoint, B>=X: intersect
  -     B       X     Y      B<X: disjoint, X<=B<=Y: intersect, B>Y: superset
  A     -       -     -      subset
  A     -       -     Y      A<=Y: intersect, A>Y: disjoint
  A     -       X     -      A=X: identical, A<X: superset, A>X: subset
  A     -       X     Y      A>Y: disjoint, X<=A<=Y: intersect, A<X: superset
  A     B       -     -      subset
  A     B       -     Y      Y<A: disjoint, A<=Y<=B: intersect, Y>B: subset
  A     B       X     -      X<A: subset, A<=X<=B: intersect, X>B: disjoint
  A     B       X     Y      this will be complex to check...

Обратите внимание, что эта диаграмма не учитывает inclusive.

---

Если у вас есть лучшее представление о реализации самих диапазонов - добро пожаловать, просто не надоПредположим, что <=3 совпадает с <4, и не полагайтесь на тот факт, что несвязанный диапазон может использовать минимальное / максимальное значение целого числа (фактическая проблемная область является более общей).Я не могу придумать лучшего представления, чем тип, состоящий из 2 границ (каждое из которых хранит значение и содержит ли он значение), которые могут существовать или не существовать.

---

Я ищу код (любой язык или псевдокод) как можно короче, который реализует функцию relation_first_to_second.Это не гольф-код, но я думаю, что «решение с кратчайшим кодом - лучший ответ» очень важно для этого вопроса.

Answer 1

Давайте решим случай, когда оба диапазона имеют границы для некоторого гипотетического императивного / объектно-ориентированного языка.

Предположим, что мы реализовали связанное сравнение, чтобы вернуть -1,0,1 (с оператором космического корабля <=> илизамените на compare() функцию), если хотите).

bound self <=> bound y
    return (self.val == y.val)
        ? (self.inclusive <=> y.inclusive) // assume that false < true
        : (self.val <=> y.val);

Теперь, если мы протестируем:

ax = a <=> x;
by = b <=> y;

If ax < by then ab is superset of xy;
If ax > by then ab is subset of xy;
If ax + by == 0 then ab equals xy;

Тогда остаются случаи пересечения и дизъюнкции, которые мы не можем решитьбез другого теста

bx = b <=> x;
ay = a <=> y;
If bx == ay then ab and xy are disjoint;
Else ab and xy intersect;

Я думаю, мы не можем сделать намного меньше для конечных границ.

Теперь, если вы введете либо +/- бесконечное val, либо +/- бесконечноеСвязанный, проблема решена.

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

Если вы придерживаетесь своего представления, которое не может отличить -infinity от + infinity, то вы не сможете легко выполнить сравнение b <=> x и a <=> y без введения другой связки if ...

Answer 2

Ваше представление диапазонов является неполным, так как оно не позволяет различать положительную и отрицательную бесконечность и, таким образом, представляет пустой диапазон как (+ ∞, -∞).Как только вы добавите + ∞ и -∞ к списку допустимых значений, все внезапно станет на свои места.

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

Теперь пересечение двух диапазонов r1 и r2 будет диапазоном от max(r1.left, r2.left) до min(r1.right, r2.right).Этот результат может быть пустым, равным r1, равным r2, равным обоим или ни одному.Это соответствует вашим непересекающимся, подмножествам, подмножествам, идентичным и пересекающимся отношениям.

Предостережение: два пустых диапазона всегда одинаковы и не пересекаются одновременно, но их представление не может быть равно (пустой диапазон имеет много представлений).Отдельная проверка необходима, если кто-то хочет, чтобы «идентичный» предикат корректно работал для пустых диапазонов.

Вот несколько поспешно запутавшихся в Haskell:

data Point = MinusInfinity |
             Finite Double Bool |
             PlusInfinity deriving (Eq, Ord, Show)

data Range = Range { left :: Point , right :: Point } deriving (Eq, Show)

min', max' :: Point -> Point -> Point
min' (Finite p1 i1) (Finite p2 i2) | p1 == p2 = Finite p1 (i1 && i2)
min' z1 z2 = min z1 z2
max' (Finite p1 i1) (Finite p2 i2) | p1 == p2 = Finite p1 (i1 && i2)
max' z1 z2 = max z1 z2

intersection r1 r2 = Range (max' (left r1) (left r2)) (min' (right r1) (right r2))

Добавление disjoint и т. Д. Является тривиальнымосуществление.