The overlap, live¶

The length two half-open intervals share, |[a, a + m) ∩ [b, b + n)|: the later start to the earlier end, and nothing where they do not meet or only touch (lusine.events.overlap). It is generic over the unit the intervals are counted in, a step's ticks, a walk's shares or a lattice's cells. Below, an interval of 0 to 12 cells slides a cell a step past the fixed interval [0, 10), its length growing a cell each pass, and the library's overlap of the two runs on your GPU as you read. Beside it the program counts, on a strip of cells, the cells both intervals hold.

This page runs the program on your GPU through WebGPU, so it needs a browser with WebGPU (a recent Chrome, Edge, Safari or Firefox). Without it the program does not run and nothing is drawn below.

What it shows¶

The strip above the controls is green while every check holds, and turns red for good once one fails.
The slide: the chart draws the overlap and the cells counted against the sliding interval's start over the pass, a point a step, the one over the other: nothing while the two are apart, rising a cell a step as they meet, flat at the shorter's length while one holds the other, and falling as they part. Below it, the sliding interval's start and count, the overlap, the cells both hold, and the overlap in metres.
The checks: four pairs by hand, [0, 10) and [5, 15) sharing 5, [2, 5) within [0, 10) its 3, [0, 10) and [10, 14) end to end nothing, and [0, 10) and [12, 16) apart nothing; the cells both hold, the overlap the count of the cells in both intervals; in metres, the same law over intervals in metres giving the same length; either way round, the intervals swapped giving the same; never past the shorter; itself, the fixed interval sharing its own length with itself. Each is held at every step.

Every number here is computed by the program on the GPU; the page only reads the values back and draws them. The fixed interval, where the slide starts and stops and the longest it grows to are the program's settings, which the host may write; this page offers no control to change them yet.

The program¶

The pairs by hand, the strip of cells, the slide and the checks, the panels the page draws, and the one procedure, main, run each step: the pairs, the sliding interval moved, the overlaps, the cells counted, and the checks.

// The overlap's live page: one interval slid past another a cell a step, its length growing each pass, the library's
// overlap of the two beside a count of the cells both hold, the same law in metres, either way round, never more than
// the shorter, an interval with itself its own length, and four pairs by hand, with the page's checks computed here on
// the GPU and shown by the panels the program declares.

namespace overlap;

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

// The reader's settings: the fixed interval, its start and its count; where the sliding interval starts each pass and
// where it stops; and the longest it grows to.
host struct { integer start = 0; integer count = 10; integer from = -14; integer to = 14; integer longest = 12; }
  settings;

// Four pairs by hand: [0, 10) and [5, 15) share 5; [2, 5) within [0, 10) its 3; [0, 10) and [10, 14) end to end
// nothing; [0, 10) and [12, 16) apart nothing.
struct case {
  host integer a_start; host integer a_count; host integer b_start; host integer b_count; host integer want;
  integer got; bool held;
};
table<case> cases(capacity = 4) = {
  { a_start = 0, a_count = 10, b_start = 5, b_count = 10, want = 5 },
  { a_start = 0, a_count = 10, b_start = 2, b_count = 3, want = 3 },
  { a_start = 0, a_count = 10, b_start = 10, b_count = 4, want = 0 },
  { a_start = 0, a_count = 10, b_start = 12, b_count = 4, want = 0 },
};

// A strip of cells from -16 to 31, each its place, to count the cells both intervals hold.
struct cell { integer at; bool both; };
table<cell> cells(capacity = 48) = {
  { at = -16 }, { at = -15 }, { at = -14 }, { at = -13 }, { at = -12 }, { at = -11 }, { at = -10 }, { at = -9 },
  { at = -8 }, { at = -7 }, { at = -6 }, { at = -5 }, { at = -4 }, { at = -3 }, { at = -2 }, { at = -1 },
  { at = 0 }, { at = 1 }, { at = 2 }, { at = 3 }, { at = 4 }, { at = 5 }, { at = 6 }, { at = 7 },
  { at = 8 }, { at = 9 }, { at = 10 }, { at = 11 }, { at = 12 }, { at = 13 }, { at = 14 }, { at = 15 },
  { at = 16 }, { at = 17 }, { at = 18 }, { at = 19 }, { at = 20 }, { at = 21 }, { at = 22 }, { at = 23 },
  { at = 24 }, { at = 25 }, { at = 26 }, { at = 27 }, { at = 28 }, { at = 29 }, { at = 30 }, { at = 31 },
};

// The sliding interval, its start and its count; the library's overlap of the two, the same in metres, and with the
// intervals swapped; the cells both hold, counted; the fixed interval's overlap with itself; and the start, as a float
// for the chart.
struct {
  integer start = -15; integer count; integer shared; integer<m> common; integer swapped; integer counted;
  integer itself; float at; float shared_shown; float counted_shown;
} slide;

// The checks: the four pairs by hand; at every step the overlap the count of the cells both intervals hold, the same in
// metres and with the intervals swapped, never more than the shorter interval, and the fixed interval sharing its own
// length with itself.
struct {
  bool by_hand = true; bool counted = true; bool metres = true; bool either_way = true; bool shorter = true;
  bool itself = true;
} checks;

// A strip of lamps the page draws, lit green while every check holds and red once one fails.
struct lamp { vector<float, 4> colour; };
lattice<lamp, 2> lamps(spacing = 1 m, boundary = wall);

vector<float, 4> lamp_colour(bool holds)
{
  return holds ? vector<float, 4>(0.15, 0.6, 0.3, 1.0) : vector<float, 4>(0.75, 0.15, 0.15, 1.0);
}

integer missed(table<bool> held) { return count(held) where !held; }

// Whether a cell is in both intervals, each from its start for its count.
bool both(integer at, integer a_start, integer a_count, integer b_start, integer b_count)
{
  return at >= a_start && at < a_start + a_count && at >= b_start && at < b_start + b_count;
}

integer counted(table<bool> both) { return count(both) where both; }

integer<m> metres(integer cells) { return cells * 1 m; }

output table<lusine.widget> panels = {
  lusine.series { { panel = "the slide", chart = "shared", quantity = slide.shared_shown, steps = 29,
                    against = slide.at, label = "the overlap" } },
  lusine.series { { panel = "the slide", chart = "shared", quantity = slide.counted_shown, steps = 29,
                    against = slide.at, label = "cells counted" } },
  lusine.value { { panel = "the slide", quantity = slide.start, label = "sliding start" } },
  lusine.value { { panel = "the slide", quantity = slide.count, label = "sliding count" } },
  lusine.value { { panel = "the slide", quantity = slide.shared, label = "overlap" } },
  lusine.value { { panel = "the slide", quantity = slide.counted, label = "cells both hold" } },
  lusine.value { { panel = "the slide", quantity = slide.common, label = "in metres" } },
  lusine.value { { panel = "the checks", quantity = checks.by_hand, label = "four pairs by hand" } },
  lusine.value { { panel = "the checks", quantity = checks.counted, label = "the cells both hold" } },
  lusine.value { { panel = "the checks", quantity = checks.metres, label = "in metres" } },
  lusine.value { { panel = "the checks", quantity = checks.either_way, label = "either way round" } },
  lusine.value { { panel = "the checks", quantity = checks.shorter, label = "never past the shorter" } },
  lusine.value { { panel = "the checks", quantity = checks.itself, label = "itself" } },
};

void main()
{
  cases.got = lusine.events.overlap(cases.a_start, cases.a_count, cases.b_start, cases.b_count);
  cases.held = cases.got == cases.want;
  // Each pass the sliding interval moves a cell a step from the start to the stop, then grows a cell, up to the
  // longest, and round again from nothing.
  slide.count = slide.start >= settings.to ? (slide.count >= settings.longest ? 0 : slide.count + 1) : slide.count;
  slide.start = slide.start >= settings.to ? settings.from : slide.start + 1;
  slide.shared = lusine.events.overlap(a_start = settings.start, a_count = settings.count, b_start = slide.start,
                                       b_count = slide.count);
  slide.common = lusine.events.overlap(a_start = metres(cells = settings.start),
                                       a_count = metres(cells = settings.count),
                                       b_start = metres(cells = slide.start), b_count = metres(cells = slide.count));
  slide.swapped = lusine.events.overlap(a_start = slide.start, a_count = slide.count, b_start = settings.start,
                                        b_count = settings.count);
  slide.itself = lusine.events.overlap(a_start = settings.start, a_count = settings.count, b_start = settings.start,
                                       b_count = settings.count);
  cells.both = both(cells.at, a_start = settings.start, a_count = settings.count, b_start = slide.start,
                    b_count = slide.count);
  slide.counted = counted(cells.both);
  slide.at = float(slide.start);
  slide.shared_shown = float(slide.shared);
  slide.counted_shown = float(slide.counted);
  checks.by_hand = checks.by_hand && missed(cases.held) == 0;
  checks.counted = checks.counted && slide.shared == slide.counted;
  checks.metres = checks.metres && slide.common == metres(cells = slide.shared);
  checks.either_way = checks.either_way && slide.swapped == slide.shared;
  checks.shorter = checks.shorter && slide.shared <= slide.count && slide.shared <= settings.count;
  checks.itself = checks.itself && slide.itself == settings.count;
  lamps.colour = lamp_colour(holds = checks.by_hand && checks.counted && checks.metres && checks.either_way
                                     && checks.shorter && checks.itself);
}

The overlap's other proof (five hundred random pairs against the integers both hold) is on its proof page.