Algorithm for line breaking in monospace text

Question

Is there a de facto standard algorithm for finding good places to put line breaks in a paragraph of text rendered in a monospace font (e.g. to a text console)?

The algorithm should aim to output lines of an equal length (which is given as an argument), inserting a variable number of spaces between each pair of adjacent words on the same line to produce a pleasing result.

The TeX algorithm (Breaking Paragraphs into Lines, Knuth & Plass 1981) is the go-to algorithm for fancy typesetting with variable-width fonts. It should be usable with fixed-width fonts by treating them like variable-width fonts, but is there a simpler algorithm tailor-made for monospace fonts?

Answer 1

How about:

• Scan forward in the text X characters.
  • While scanning forward if you encounter a line break, stop immediately and respect it.
  • While scanning forward count how many sections of white text there are as white space sections.
• If the current character is not white space, or a breaking character (such as -)
  • walk back and count as white space to insert till a whitespace or breaking character is encountered
  • if its a white space keep walk back till discovering a non-whitespace character, and subtract 1 from white space sections
• Return to the start of the line.
• walk forward printing each character
  • if the character is a whitespace keep printing till the first non whitespace character.
  • print floor(white space to insert / white space sections) spaces.
  • subtract that number from white space to insert
  • subtract 1 from white space sections
  • keep walking forward

This is a rough algorithm.

• You could count the total amount of whitespace and rejustify each time you encounter any amount of it. Just count each string of whitespace as a single section, and don't emit any when walking forward normally.
• I didn't account for the size of tab, depends on whether you want it to be aligned, or just a fixed size.
• You could add in auto justification for tab such that following lines align to it till a return is encountered. You will need to track the tab depth, and shorten the length of string walked forward.