balancedCuts static method
cuts as Balance takes them, for a box that sets its own lines.
Implementation
static List<int>? balancedCuts(
List<(int, int)> opp,
double Function(int) x,
double room,
int lines, {
double? firstRoom,
}) {
// f[k][j]: the least cost of covering the first j breaks in k lines,
// and from[k][j] the break the last of those lines started after.
const huge = double.infinity;
final f = List.generate(lines + 1, (_) => List<double>.filled(opp.length + 1, huge));
final from = List.generate(lines + 1, (_) => List<int>.filled(opp.length + 1, -1));
f[0][0] = 0;
for (var k = 1; k <= lines; k++) {
for (var j = k; j <= opp.length; j++) {
final end = opp[j - 1].$1;
for (var i = k - 1; i < j; i++) {
if (f[k - 1][i] == huge) continue;
final start = i == 0 ? 0 : opp[i - 1].$2;
final w = x(end) - x(start);
// A line wider than the room is only allowed where it holds
// one unbreakable stretch, which CSS lets hang out of the box.
final r = k == 1 ? firstRoom ?? room : room;
if (w > r && j - i > 1) continue;
final over = r - w;
// A LINE THAT ENDS AT A HYPHEN COSTS A LITTLE MORE than one that
// ends at a space (Knuth-Plass's hyphen penalty). A phone-width
// hero can be `framework optimized / for building fast, /
// content-driven websites.` or `framework optimized for /
// building fast, content- / driven websites.`, seven apart in
// squared room out of twenty thousand, and Chrome sets the one
// without the hyphen; a twentieth of the room, squared, settles
// it and leaves `for content- / driven websites` (13,000 ahead)
// where it was.
final hyphen = j < opp.length && opp[j - 1].$1 == opp[j - 1].$2;
final cost = f[k - 1][i] + over * over + (hyphen ? room * room / 400 : 0);
if (cost < f[k][j]) {
f[k][j] = cost;
from[k][j] = i;
}
}
}
}
if (f[lines][opp.length] == huge) return null;
final cuts = <int>[];
var j = opp.length;
for (var k = lines; k > 0; k--) {
cuts.add(j);
j = from[k][j];
}
cuts.add(0);
return cuts;
}