groff
[Top][All Lists]

## [Groff] Formatting algorithm

 From: Peter Schaffter Subject: [Groff] Formatting algorithm Date: Mon, 31 Mar 2014 19:44:07 -0400 User-agent: Mutt/1.5.21 (2010-09-15)

```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.

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 {
SpaceLeft := SpaceLeft - (Width(Syllable) + Width(Hyphen))
}
}
}
else {
if Width(NextWord) > SpaceLeft {
if HyphenateWord {
for each Syllable in Word {
if (Width(Syllable) + Width(Hyphen)) > SpaceLeft {
insert breakpoint before Syllable
}
else {
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 {
SpaceLeft   := LineLength - (Width(Word) + Width(Space))
Num(Spaces) := Num(Spaces) + 1
}
}

--
Peter Schaffter
http://www.schaffter.ca

```