Given two ranges:
R1 = {n : b1 ≤ n < b1 + s1}
R2 = {n : b2 ≤ n < b2 + s2}
determine whether they overlap.
The ranges are specified using two values: an inclusive beginning b and a size s.
Tuple comparison is defined canonically (first differing element decides):
(b1, s1) > (b2, s2) iff (b1 > b2) ∨ (b1 = b2 ∧ s1 > s2)
There is an exhaustive list of cases how two ranges may overlap:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | name | blue | orange | first | second | left comparison value | right comparison value | comparison result | overlap observed | comparison matches observation | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| beginning | size | beginning | size | beginning | size | beginning | size | ||||||||||||||||
| (base range) | |||||||||||||||||||||||
| after | 3 | 4 | 0 | 2 | 0 | 2 | 3 | 4 | 2 | 3 | ⊥ | ⊥ | ⊤ | ||||||||||
| start touching | 3 | 4 | 0 | 3 | 0 | 3 | 3 | 4 | 3 | 3 | ⊥ | ⊥ | ⊤ | ||||||||||
| start inside | 3 | 4 | 0 | 4 | 0 | 4 | 3 | 4 | 4 | 3 | ⊤ | ⊤ | ⊤ | ||||||||||
| inside start touching | 3 | 4 | 3 | 7 | 3 | 4 | 3 | 7 | 7 | 3 | ⊤ | ⊤ | ⊤ | ||||||||||
| enclosing start touching | 3 | 4 | 3 | 3 | 3 | 3 | 3 | 4 | 6 | 3 | ⊤ | ⊤ | ⊤ | ||||||||||
| enclosing | 3 | 4 | 4 | 2 | 3 | 4 | 4 | 2 | 7 | 4 | ⊤ | ⊤ | ⊤ | ||||||||||
| enclosing end touching | 3 | 4 | 4 | 3 | 3 | 4 | 4 | 3 | 7 | 4 | ⊤ | ⊤ | ⊤ | ||||||||||
| exact match | 3 | 4 | 3 | 4 | 3 | 4 | 3 | 4 | 7 | 3 | ⊤ | ⊤ | ⊤ | ||||||||||
| inside | 3 | 4 | 0 | 10 | 0 | 10 | 3 | 4 | 10 | 3 | ⊤ | ⊤ | ⊤ | ||||||||||
| inside end touching | 3 | 4 | 0 | 7 | 0 | 7 | 3 | 4 | 7 | 3 | ⊤ | ⊤ | ⊤ | ||||||||||
| end inside | 3 | 4 | 6 | 4 | 3 | 4 | 6 | 4 | 7 | 6 | ⊤ | ⊤ | ⊤ | ||||||||||
| end touching | 3 | 4 | 7 | 3 | 3 | 4 | 7 | 3 | 7 | 7 | ⊥ | ⊥ | ⊤ | ||||||||||
| before | 3 | 4 | 8 | 2 | 3 | 4 | 8 | 2 | 7 | 8 | ⊥ | ⊥ | ⊤ | ||||||||||