0

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?

6
  • 4
    Do you have an issue using that algorithm with a variable-width font where every character just happens to have the same width? Dec 1, 2020 at 19:46
  • 1
    What are your requirements: maximum line size? equal sized lines for the whole para? do you neeed to block-justify the lines adding spaces?
    – Christophe
    Dec 1, 2020 at 22:02
  • 1
    en.wikipedia.org/wiki/Par_(command)
    – jmoreno
    Dec 2, 2020 at 0:58
  • 1
    @jmoreno: asking for an algorithm is not generally off-topic. In this case, the OP mentioned a complex algorithm for a specific problem and asks for a simpler one for an even more specific problem. That is IMHO focussed enough for making the question a good fit for this site, and I find it pretty ridicuolus that it already got 4 close votes.
    – Doc Brown
    Dec 2, 2020 at 7:18
  • 1
    ... it seems to me parts of the community here seem only to seek for reasons to close a question, instead of thinking about constructive ways to keep more of them open.
    – Doc Brown
    Dec 2, 2020 at 7:22

1 Answer 1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.