Here's the bare bones version of the algorithm I was thinking of when I proposed improving line formatting by getting groff to shoulder the burden for some of the work we do manually. It's written out in brute-force pseudo-code; should be pretty clear.
The aim is not to find optimal breaks in Knuthian fashion, but to improve the uniformity of grey from line to line using a greedy algorithm. Key features are that letterspacing and wordspacing are orthogonal, and that NextWord can be read during optimization. The chief reason for opening discussion about this is because I don't want implementation of KP carved in stone in the mission statement unless we're fully committed to it. Our goal is to improve paragraph formatting; if it looks like there may be more than one way to make it happen, we should be considering the possibilities now. # Assumptions # =========== # WordSpace: # - can be shrunk # - is independent of letterspacing # - is stretchable when Line is printed # Line: # - letterspaced Width(Line) can be calculated # NextWord: # - can be read from a buffer # SpaceWidth(Opt) := WordSpace SpaceWidth(Min) := SpaceWidth(Opt) - n Unit(LetterSpace) := PointSize / 100 # 100 is arbitrary LetterSpace(Max) := LetterSpace + Units(LetterSpace) LetterSpace(Min) := LetterSpace - Units(LetterSpace) Width(Space) := SpaceWidth(Opt) LetterSpace := 0 SpaceLeft := LineLength for each Word in Text { # Line is short by Width(Space); apply positive letterspacing # Width(Space) is arbitrary; the value could be larger or smaller if (SpaceLeft > 0) and (SpaceLeft <= Width(Space)) { until (SpaceLeft = 0) or (LetterSpace = LetterSpace(Max)) { LetterSpace := LetterSpace + Unit(LetterSpace) letterspace Line by LetterSpace SpaceLeft := LineLength - Width(Line) } insert breakpoint before Word SpaceLeft := LineLength - (Width(Word) + Width(Space)) } # Line is long by Width(Space); apply negative letterspacing if (SpaceLeft < 0) and (SpaceLeft <= -(Width(Space)) { until (SpaceLeft = 0) or (LetterSpace = LetterSpace(Min)) { LetterSpace := LetterSpace - Unit(LetterSpace) letterspace Line by LetterSpace SpaceLeft := LineLength - Width(Line) } insert breakpoint before Word SpaceLeft := LineLength - (Width(Word) + Width(Space)) } # Word exceeds LineLength if Width(Word) > SpaceLeft { Num(Spaces) := Num(Spaces) -1 # remove discardable space Width(Space) := SpaceWidth(Min) WordSpace := Width(Space) SpaceLeft := Num(Spaces) * Width(Space) if HyphenateWord { for each Syllable in Word { if (Width(Syllable) + Width(Hyphen)) > SpaceLeft { insert breakpoint before Syllable } else { add Syllable to Line SpaceLeft := SpaceLeft - (Width(Syllable) + Width(Hyphen)) } } } else { read NextWord if Width(NextWord) > SpaceLeft { if HyphenateWord { for each Syllable in Word { if (Width(Syllable) + Width(Hyphen)) > SpaceLeft { insert breakpoint before Syllable } else { add Syllable to Line SpaceLeft := SpaceLeft - (Width(Syllable) + Width(Hyphen)) } } } } else { insert breakpoint before Word SpaceLeft := LineLength - (Width(Word) + Width(Space)) } } # Bring wordspace closer to optimum by negative track kerning # down to LetterSpace(Min) if (SpaceLeft / Num(Spaces)) < SpaceWidth(Opt) { until (SpaceLeft = 0) or (LetterSpacing = LetterSpace(Min)) { LetterSpace := LetterSpace - Unit(LetterSpace) letterspace Line by LetterSpace SpaceLeft := LineLength - Width(Line) } } # Bring wordspace closer to optimum by positive track kerning # up to LetterSpace(Max) if (SpaceLeft / Num(Spaces)) > SpaceWidth(Opt) { until (SpaceLeft = 0) or (LetterSpacing = LetterSpace(Max) { LetterSpace := LetterSpace + Unit(LetterSpace) letterspace Line by LetterSpace SpaceLeft := LineLength - Width(Line) } } WordSpace := SpaceWidth(Min) # WordSpace is stretchable print Line Num(Spaces) := 0 LetterSpace := 0 Width(Space) := SpaceWidth(Opt) WordSpace := Width(Space) } else { add Word to Line SpaceLeft := LineLength - (Width(Word) + Width(Space)) Num(Spaces) := Num(Spaces) + 1 } } -- Peter Schaffter http://www.schaffter.ca