How can this Line-Breaking algorithm consider spaces as having width different than 1.0?


The Divide & Conquer Algorithm for Line-Breaking described here is given below, both in Python and in Dart (which is similar to Java/C#).

Line-breaking is also known as “line wrap”, “word wrap”, or “paragraph formation”, and this algorithm is used for achieving minimum raggedness.

This algorithm works, but it considers each space as having exactly width = 1.0 .

My Question:

How can I modify this algorithm so that it ignores spaces? In other words, make it consider spaces as having width 0.0? (or it would also work for me if I could define any width I wanted for the spaces, including 0.0).

Python Implementation:

def divide(text, width):     words = text.split()     count = len(words)     offsets = [0]     for w in words:         offsets.append(offsets[-1] + len(w))      minima = [0] + [10 ** 20] * count     breaks = [0] * (count + 1)      def cost(i, j):         w = offsets[j] - offsets[i] + j - i - 1         if w > width:             return 10 ** 10         return minima[i] + (width - w) ** 2      def search(i0, j0, i1, j1):         stack = [(i0, j0, i1, j1)]         while stack:             i0, j0, i1, j1 = stack.pop()             if j0 < j1:                 j = (j0 + j1) // 2                 for i in range(i0, i1):                     c = cost(i, j)                     if c <= minima[j]:                         minima[j] = c                         breaks[j] = i                 stack.append((breaks[j], j+1, i1, j1))                 stack.append((i0, j0, breaks[j]+1, j))      n = count + 1     i = 0     offset = 0     while True:         r = min(n, 2 ** (i + 1))         edge = 2 ** i + offset         search(0 + offset, edge, edge, r + offset)         x = minima[r - 1 + offset]         for j in range(2 ** i, r - 1):             y = cost(j + offset, r - 1 + offset)             if y <= x:                 n -= j                 i = 0                 offset += j                 break         else:             if r == n:                 break             i = i + 1      lines = []     j = count     while j > 0:         i = breaks[j]         lines.append(' '.join(words[i:j]))         j = i     lines.reverse()     return lines 

Dart implementation:

class MinimumRaggedness {    /// Given some [boxWidths], break it into the smallest possible number   /// of lines such as each line has width not larger than [maxWidth].   /// It also minimizes the difference between width of each line,   /// achieving a "balanced" result.   /// Spacing between boxes is 1.0.   static List<List<int>> divide(List<num> boxWidths, num maxWidth) {      int count = boxWidths.length;     List<num> offsets = [0];      for (num boxWidth in boxWidths) {       offsets.add(offsets.last + min(boxWidth, maxWidth));     }      List<num> minimum = [0]..addAll(List<num>.filled(count, 9223372036854775807));     List<int> breaks = List<int>.filled(count + 1, 0);      num cost(int i, int j) {       num width = offsets[j] - offsets[i] + j - i - 1;       if (width > maxWidth)         return 9223372036854775806;       else         return minimum[i] + pow(maxWidth - width, 2);     }      void search(int i0, int j0, int i1, int j1) {       Queue<List<int>> stack = Queue()..add([i0, j0, i1, j1]);        while (stack.isNotEmpty) {         List<int> info = stack.removeLast();         i0 = info[0];         j0 = info[1];         i1 = info[2];         j1 = info[3];          if (j0 < j1) {           int j = (j0 + j1) ~/ 2;            for (int i = i0; i < i1; i++) {             num c = cost(i, j);             if (c <= minimum[j]) {               minimum[j] = c;               breaks[j] = i;             }           }            stack.add([breaks[j], j + 1, i1, j1]);           stack.add([i0, j0, breaks[j] + 1, j]);         }       }     }      int n = count + 1;     int i = 0;     int offset = 0;      while (true) {       int r = min(n, pow(2, i + 1));       int edge = pow(2, i) + offset;       search(0 + offset, edge, edge, r + offset);       num x = minimum[r - 1 + offset];        bool flag = true;       for (int j = pow(2, i); j < r - 1; j++) {         num y = cost(j + offset, r - 1 + offset);         if (y <= x) {           n -= j;           i = 0;           offset += j;           flag = false;           break;         }       }        if (flag) {         if (r == n) break;         i = i + 1;       }     }      int j = count;      List<List<int>> indexes = [];      while (j > 0) {       int i = breaks[j];       indexes.add(List<int>.generate(j - i, (index) => index + i));       j = i;     }      return indexes.reversed.toList();   } }