prettyCuts static method
cuts as Pretty takes them, for a box that sets its own lines. A
FIRST LINE OF A ROOM OF ITS OWN (text-indent) is broken greedily in
that room and scored against it where the tail reaches it: 61 of 61
Chrome paragraphs hung by -6 to -24px agree
(fixtures/indent-hanging-pretty).
Implementation
static List<int>? prettyCuts(
List<(int, int)> opp,
double Function(int) x,
double room,
int lines, {
double? firstRoom,
}) {
double width(int i, int j) => x(opp[j - 1].$1) - x(i == 0 ? 0 : opp[i - 1].$2);
double roomOf(int line) => line == 0 ? firstRoom ?? room : room;
// The greedy break: each line takes what fits, and one unbreakable
// stretch hangs out where nothing does.
final greedy = <int>[];
var start = 0;
while (start < opp.length) {
var j = start + 1;
while (j < opp.length && width(start, j + 1) <= roomOf(greedy.length)) {
j++;
}
greedy.add(j);
start = j;
}
final n = greedy.length;
// The same count Skia found, or the block would change height.
if (n < 2 || n != lines) return null;
// The trigger: one word on the last line, under a third of the room.
final lastStart = greedy[n - 2];
if (opp.length - lastStart != 1 || width(lastStart, opp.length) >= roomOf(n - 1) / 3) return null;
// The tail: the last four lines, re-broken over the same count.
final k = math.min(tail, n);
final from0 = n == k ? 0 : greedy[n - k - 1];
const huge = double.infinity;
final f = List.generate(k + 1, (_) => List<double>.filled(opp.length + 1, huge));
final prev = List.generate(k + 1, (_) => List<int>.filled(opp.length + 1, -1));
f[0][from0] = 0;
for (var line = 1; line <= k; line++) {
final last = line == k;
for (var j = from0 + line; j <= opp.length; j++) {
if (last != (j == opp.length)) continue;
for (var i = from0 + line - 1; i < j; i++) {
if (f[line - 1][i] == huge) continue;
// The last line holds two words at least; it costs nothing.
if (last && j - i < 2) continue;
final w = width(i, j), r = roomOf(n - k + line - 1);
if (w > r && j - i > 1) continue;
final hyphen = !last && opp[j - 1].$1 == opp[j - 1].$2;
final over = r - w;
final cost = f[line - 1][i] + (last ? 0 : over * over + (hyphen ? room * room / 400 : 0));
if (cost < f[line][j]) {
f[line][j] = cost;
prev[line][j] = i;
}
}
}
}
if (f[k][opp.length] == huge) return null;
final cuts = <int>[];
var j = opp.length;
for (var line = k; line > 0; line--) {
cuts.add(j);
j = prev[line][j];
}
for (var h = n - k - 1; h >= 0; h--) {
cuts.add(greedy[h]);
}
cuts.add(0);
return cuts;
}