[Groff] Formatting algorithm

[Peter Schaffter]

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