prettyCuts static method

List<int>? prettyCuts(
  1. List<(int, int)> opp,
  2. double x(
    1. int
    ),
  3. double room,
  4. int lines, {
  5. double? firstRoom,
})

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;
}