Generator

Two tests, one column

Rendered here at the parameters it defaults to, with every essay that calls it — which is the same list as the blast radius of changing it.
Two tests, one columnThe first 8 steps of a document listing over rows 476 to 489 — the rows of a 4-character pattern in a collection of 8 documents. At each step the range minimum returns a position; the published method compares the chain entry there against the start of the range, and this one asks whether the document at that position is already in the answer. The two columns are the same column, at every step and on every collection tried. The chain is therefore not read — and once it is not read it does not have to be stored, because the structure over it keeps the shape of an array and not its numbers.range consideredminimum atC[at] < lonew document[476, 489)483 · document 4yesyes[476, 483)477 · document 1yesyes[476, 477)476 · document 0yesyes[478, 483)482 · document 2yesyes[478, 482)478 · document 0nono[484, 489)486 · document 3yesyes[484, 486)484 · document 0nono[487, 489)487 · document 2nono8 steps, 5 documents, and the two columns never differrows 476–489 · 8 documents8 steps

Two tests, one column

The first 8 steps of a document listing over rows 476 to 489 — the rows of a 4-character pattern in a collection of 8 documents. At each step the range minimum returns a position; the published method compares the chain entry there against the start of the range, and this one asks whether the document at that position is already in the answer. The two columns are the same column, at every step and on every collection tried. The chain is therefore not read — and once it is not read it does not have to be stored, because the structure over it keeps the shape of an array and not its numbers.

Drawn at 700 × 476, wide on the page. Everything above is what chainless-listing returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

6 essays call chainless-listing. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.

Where it is called

Changing this generator changes every one of these figures.

① prose12,33512① code13,1508① revisions7,77410② essays12,33582② captions2302,214② history12,96314documentscharacters in a document① the first freeze · ② the secondmedian marked The index that replaces the text

Two thousand documents of two hundred characters

forward · wavelet tree18,377forward · rank directories5,037forward · C table100forward · sample marks8,193forward · sampled positions3,598reverse · wavelet tree18,377reverse · rank directories5,037reverse · C table100reverse · sample marks8,193droppedreverse · sampled positions3,598dropped8,192 characters · sampling every 3216.7% of both halves The other axis

An index that cannot locate

range consideredminimum atC[at] < lonew document[476, 489)483 · document 4yesyes[476, 483)477 · document 1yesyes[476, 477)476 · document 0yesyes[478, 483)482 · document 2yesyes[478, 482)478 · document 0nono[484, 489)486 · document 3yesyes[484, 486)484 · document 0nono[487, 489)487 · document 2nono8 steps, 5 documents, and the two columns never differrows 476–489 · 8 documents8 steps The index that replaces the text

The array the walk never reads

range consideredminimum atC[at] < lonew document[476, 489)483 · document 4yesyes[476, 483)477 · document 1yesyes[476, 477)476 · document 0yesyes[478, 483)482 · document 2yesyes[478, 482)478 · document 0nono[484, 489)486 · document 3yesyes[484, 486)484 · document 0nono[487, 489)487 · document 2nono8 steps, 5 documents, and the two columns never differrows 476–489 · 8 documents8 steps Structures

A document already in the answer

tree · suffix array2,363,886tree · text656,635tree · document array1,050,616tree · previous-occurrence chain2,363,886tree · range minimum4,727,772succinct · suffix array2,363,886succinct · text656,635succinct · document array1,050,616succinct · previous-occurrence chain2,363,886succinct · range minimum1,483,854chainless · suffix array2,363,886chainless · text656,635chainless · document array1,050,616chainless · range minimum1,483,854chainless · reported bitmap256131,327 characters · 256 documents6 parts The other axis

What the chain cost

a segment tree over the chain2.70x8,142,274 bitsa succinct range minimum over the chain1.62x4,898,356 bitsno chain at all0.84x2,534,726 bitsthe dashed rule is the index itself: a suffix array and the text131,327 characters · 256 documents2.70x → 0.84x What the libraries do

The apparatus that is smaller than its index

The library, page 1 of 5 — where chainless-listing sits