balancedCuts static method

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

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