"""Wrap.py Break paragraphs into lines, attempting to avoid short lines. We use the dynamic programming idea of Knuth-Plass to find the optimal set of breaks according to a penalty function that penalizes short lines quadratically; this can be done in linear time via the OnlineConcaveMinima algorithm in SMAWK.py. D. Eppstein, August 2005. """ from SMAWK import OnlineConcaveMinima def wrap(text, # string or unicode to be wrapped target = 76, # maximum length of a wrapped line longlast = False, # True if last line should be as long as others frenchspacing = False, # Single space instead of double after periods measure = len, # how to measure the length of a word overpenalty = 1000, # penalize long lines by overpen*(len-target) nlinepenalty = 1000, # penalize more lines than optimal onewordpenalty = 25, # penalize really short last line hyphenpenalty = 25): # penalize breaking hyphenated words """Wrap the given text, returning a sequence of lines.""" # Make sequence of tuples (word, spacing if no break, cum.measure). words = [] total = 0 spacings = [0, measure(' '), measure(' ')] for hyphenword in text.split(): if words: total += spacings[words[-1][1]] parts = hyphenword.split('-') for word in parts[:-1]: word += '-' total += measure(word) words.append((word,0,total)) word = parts[-1] total += measure(word) spacing = 1 if word.endswith('.') and (len(hyphenword) > 2 or not hyphenword[0].isupper()): spacing = 2 - frenchspacing words.append((word,spacing,total)) # Define penalty function for breaking on line words[i:j] # Below this definition we will set up cost[i] to be the # total penalty of all lines up to a break prior to word i. def penalty(i,j): if j > len(words): return -i # concave flag for out of bounds total = cost.value(i) + nlinepenalty prevmeasure = i and (words[i-1][2] + spacings[words[i-1][1]]) linemeasure = words[j-1][2] - prevmeasure if linemeasure > target: total += overpenalty * (linemeasure - target) elif j < len(words) or longlast: total += (target - linemeasure)**2 elif i == j-1: total += onewordpenalty if not words[j-1][1]: total += hyphenpenalty return total # Apply concave minima algorithm and backtrack to form lines cost = OnlineConcaveMinima(penalty,0) pos = len(words) lines = [] while pos: breakpoint = cost.index(pos) line = [] for i in range(breakpoint,pos): line.append(words[i][0]) if i < pos-1 and words[i][1]: line.append(' '*words[i][1]) lines.append(''.join(line)) pos = breakpoint lines.reverse() return lines