The overlap¶

The length two intervals share, |[a, a + m) intersect [b, b + n)|: the later start to the earlier end, and nothing where they do not meet or only touch.

Generic over the unit the intervals are counted in (a step's ticks, a walk's shares, a lattice's cells): all four in one unit, which the result takes. Each interval is its start and its count, half-open, so two intervals end to end share nothing. Source: a definition, the intersection of two half-open intervals. Checked against a reference in numpy, which has its own tests.

Source

a definition, the intersection of two half-open intervals.

Proof

reference, invariant, limit.

overlap.trait

namespace lusine.events;

integer<_> overlap(integer<_> a_start, integer<_> a_count, integer<_> b_start, integer<_> b_count)
{
  let from = a_start > b_start ? a_start : b_start;
  let to = a_start + a_count < b_start + b_count ? a_start + a_count : b_start + b_count;
  let zero = from - from;
  return to > from ? to - from : zero;
}

The length two half-open intervals share, the later start to the earlier end and nothing where they do not meet; generic over the unit the intervals are counted in.

In [1]:

import os, sys
root = os.getcwd()
while not os.path.isfile(os.path.join(root, 'docsite.json')):
    root = os.path.dirname(root)
sys.path.insert(0, os.path.join(root, 'tools'))
import numpy as np
import matplotlib.pyplot as plt
from lusine import trait_run
F32 = np.float32
U = float(np.finfo(F32).eps) / 2        # binary32's unit roundoff, 2^-24

import os, sys root = os.getcwd() while not os.path.isfile(os.path.join(root, 'docsite.json')): root = os.path.dirname(root) sys.path.insert(0, os.path.join(root, 'tools')) import numpy as np import matplotlib.pyplot as plt from lusine import trait_run F32 = np.float32 U = float(np.finfo(F32).eps) / 2 # binary32's unit roundoff, 2^-24

The kernel¶

The law as the library states it, and as this page runs it.

In [2]:

print(trait_run.source('events/overlap.trait'))

print(trait_run.source('events/overlap.trait'))

// lusine.events.overlap: the length two intervals share, |[a, a + m) intersect [b, b + n)|: the later start to the
// earlier end, and nothing where they do not meet or only touch. Generic over the unit the intervals are counted in
// (a step's ticks, a walk's shares, a lattice's cells): all four in one unit, which the result takes. Each interval
// is its start and its count, half-open, so two intervals end to end share nothing.
// Source: a definition, the intersection of two half-open intervals.
// Checked against a reference in numpy, which has its own tests.

namespace lusine.events;

integer<_> overlap(integer<_> a_start, integer<_> a_count, integer<_> b_start, integer<_> b_count)
{
  let from = a_start > b_start ? a_start : b_start;
  let to = a_start + a_count < b_start + b_count ? a_start + a_count : b_start + b_count;
  let zero = from - from;
  return to > from ? to - from : zero;
}

The program¶

A lattice of pairs, each two intervals as their starts and counts, the host's, the kernel bound twice by the one law: to a walk's shares (a count, no unit) and to a span of cells, in metres.

In [3]:

PAIRS = """namespace pairs;

lusine.version version = { { number = 1 } };

struct pair {
  host integer a_start; host integer a_count; host integer b_start; host integer b_count; integer shared;
  host integer<m> a_from; host integer<m> a_span; host integer<m> b_from; host integer<m> b_span; integer<m> common;
};
lattice<pair, 1> pairs(spacing = 1 m, boundary = wall);

void main()
{
  pairs.shared = lusine.events.overlap(pairs.a_start, pairs.a_count, pairs.b_start, pairs.b_count);
  pairs.common = lusine.events.overlap(a_start = pairs.a_from, a_count = pairs.a_span,
                                       b_start = pairs.b_from, b_count = pairs.b_span);
}
"""
print(PAIRS)


def shared(a, m, b, n):
    """Each pair's shared length, as shares and as metres."""
    k = max(np.size(x) for x in (a, m, b, n))
    run = trait_run.Program(['events/overlap.trait'], PAIRS, {'pairs.pairs': [k]})
    for field, v in (('a_start', a), ('a_count', m), ('b_start', b), ('b_count', n),
                     ('a_from', a), ('a_span', m), ('b_from', b), ('b_span', n)):
        run.store('pairs.pairs', field, np.broadcast_to(np.asarray(v), (k,)))
    s, c = run.steps('pairs.main', 1, [('pairs.pairs', 'shared'), ('pairs.pairs', 'common')])
    return s[0], c[0]

PAIRS = """namespace pairs; lusine.version version = { { number = 1 } }; struct pair { host integer a_start; host integer a_count; host integer b_start; host integer b_count; integer shared; host integer<m> a_from; host integer<m> a_span; host integer<m> b_from; host integer<m> b_span; integer<m> common; }; lattice<pair, 1> pairs(spacing = 1 m, boundary = wall); void main() { pairs.shared = lusine.events.overlap(pairs.a_start, pairs.a_count, pairs.b_start, pairs.b_count); pairs.common = lusine.events.overlap(a_start = pairs.a_from, a_count = pairs.a_span, b_start = pairs.b_from, b_count = pairs.b_span); } """ print(PAIRS) def shared(a, m, b, n): """Each pair's shared length, as shares and as metres.""" k = max(np.size(x) for x in (a, m, b, n)) run = trait_run.Program(['events/overlap.trait'], PAIRS, {'pairs.pairs': [k]}) for field, v in (('a_start', a), ('a_count', m), ('b_start', b), ('b_count', n), ('a_from', a), ('a_span', m), ('b_from', b), ('b_span', n)): run.store('pairs.pairs', field, np.broadcast_to(np.asarray(v), (k,))) s, c = run.steps('pairs.main', 1, [('pairs.pairs', 'shared'), ('pairs.pairs', 'common')]) return s[0], c[0]

namespace pairs;

lusine.version version = { { number = 1 } };

struct pair {
  host integer a_start; host integer a_count; host integer b_start; host integer b_count; integer shared;
  host integer<m> a_from; host integer<m> a_span; host integer<m> b_from; host integer<m> b_span; integer<m> common;
};
lattice<pair, 1> pairs(spacing = 1 m, boundary = wall);

void main()
{
  pairs.shared = lusine.events.overlap(pairs.a_start, pairs.a_count, pairs.b_start, pairs.b_count);
  pairs.common = lusine.events.overlap(a_start = pairs.a_from, a_count = pairs.a_span,
                                       b_start = pairs.b_from, b_count = pairs.b_span);
}

Reference: four pairs¶

[0, 10) and [5, 15) share 5; [2, 5) within [0, 10) shares its 3; [0, 10) and [10, 14) end to end share nothing; [0, 10) and [12, 16) apart share nothing. The same in metres.

In [4]:

s, c = shared([0, 0, 0, 0], [10, 10, 10, 10], [5, 2, 10, 12], [10, 3, 4, 4])
assert list(s) == [5, 3, 0, 0], s
assert list(c) == [5, 3, 0, 0], c
print(s, c)

s, c = shared([0, 0, 0, 0], [10, 10, 10, 10], [5, 2, 10, 12], [10, 3, 4, 4]) assert list(s) == [5, 3, 0, 0], s assert list(c) == [5, 3, 0, 0], c print(s, c)

[5 3 0 0] [5 3 0 0]

Invariant: the integers both hold, either way round¶

Five hundred random pairs: the shared length is the count of the integers both intervals hold, the same with the intervals swapped, and the same in metres.

In [5]:

from lusine.kernels.events.overlap import overlap as reference
rng = np.random.default_rng(421)
a, b = rng.integers(0, 100, 500), rng.integers(0, 100, 500)
m, n = rng.integers(0, 40, 500), rng.integers(0, 40, 500)
s, c = shared(a, m, b, n)
counted = np.array([len(set(range(x, x + p)) & set(range(y, y + q))) for x, p, y, q in zip(a, m, b, n)])
assert np.array_equal(s, counted) and np.array_equal(c, counted) and np.array_equal(s, reference(a, m, b, n))
t, _ = shared(b, n, a, m)
assert np.array_equal(t, s)
print(int((s > 0).sum()), 'of 500 pairs overlap; the longest shared run is', int(s.max()))
fig, ax = plt.subplots(figsize=(7, 3))
ax.hist(s, bins=np.arange(0, 41) - 0.5)
ax.set_xlabel('shared length')
ax.set_ylabel('pairs')
plt.show()

from lusine.kernels.events.overlap import overlap as reference rng = np.random.default_rng(421) a, b = rng.integers(0, 100, 500), rng.integers(0, 100, 500) m, n = rng.integers(0, 40, 500), rng.integers(0, 40, 500) s, c = shared(a, m, b, n) counted = np.array([len(set(range(x, x + p)) & set(range(y, y + q))) for x, p, y, q in zip(a, m, b, n)]) assert np.array_equal(s, counted) and np.array_equal(c, counted) and np.array_equal(s, reference(a, m, b, n)) t, _ = shared(b, n, a, m) assert np.array_equal(t, s) print(int((s > 0).sum()), 'of 500 pairs overlap; the longest shared run is', int(s.max())) fig, ax = plt.subplots(figsize=(7, 3)) ax.hist(s, bins=np.arange(0, 41) - 0.5) ax.set_xlabel('shared length') ax.set_ylabel('pairs') plt.show()

147 of 500 pairs overlap; the longest shared run is 29

Limit: the shorter, itself, and nothing¶

Never more than the shorter interval; an interval with itself shares its own length; an empty interval shares nothing wherever it starts.

In [6]:

assert np.all(s <= np.minimum(m, n))
own, _ = shared(a, m, a, m)
assert np.array_equal(own, m)
none, _ = shared([3, 3, 3], [0, 0, 0], [0, 3, 5], [10, 10, 10])
assert list(none) == [0, 0, 0], none
print('bounded by the shorter; itself:', own[:5], '; empty:', none)

assert np.all(s <= np.minimum(m, n)) own, _ = shared(a, m, a, m) assert np.array_equal(own, m) none, _ = shared([3, 3, 3], [0, 0, 0], [0, 3, 5], [10, 10, 10]) assert list(none) == [0, 0, 0], none print('bounded by the shorter; itself:', own[:5], '; empty:', none)

bounded by the shorter; itself: [34  2 25 16  5] ; empty: [0 0 0]