linebreak

A Go library demonstrating line-breaking algorithms with optimal text formatting.

Overview

This project implements two line-breaking algorithms to format text within specified width constraints:

• Greedy Algorithm: Fast, simple approach that fits as many words as possible on each line
• Knuth-Plass Algorithm: Sophisticated dynamic programming solution that optimizes line breaks based on penalty functions

Features

• Multiple Algorithms: Choose between greedy and Knuth-Plass line breaking
• Dynamic Programming: Efficiently computes optimal line breaks. It uses a penalty for trailing spaces to promote balanced text.
• Unit Tested: Includes unit tests to ensure quality and to allow future changes with confidence.

Installation and Running

To run the app:

go run github.com/tomconder/linebreak/cmd/linebreak

To use the package in your project, you can get it using Go modules:

go get github.com/tomconder/linebreak/pkg/linebreak

Algorithms

Greedy

The greedy algorithm breaks a sequence of words into lines. At each step it fits as many words as possible on each line within the given width.

For example, the following text with a given width of 14:

The lazy yellow dog was caught by the slow red fox as he lay sleeping in the sun

gives the following result

The lazy
yellow dog was
caught by the
slow red fox
as he lay
sleeping in
the sun

Knuth-Plass

The Knuth-Plass line breaking algorithm breaks a sequence of words into lines that do not exceed the given width. It uses dynamic programming to determine optimal breakpoints based on a penalty function that discourages trailing empty spaces.

For example, the following text with a given width of 14:

The lazy yellow dog was caught by the slow red fox as he lay sleeping in the sun

gives the following result

The lazy
yellow dog
was caught by
the slow red
fox as he lay
sleeping in
the sun