Report Number: CS-TR-79-770
Institution: Stanford University, Department of Computer Science
Title: Pretty printing
Author: Oppen, Derek C.
Date: October 1979
Abstract: An algorithm for pretty printing is given. For an input stream of length n and an output device with margin width m, the algorithm requires time O(n) and space O(m). The algorithrn is described in terms of two parallel processes; the first scans the input stream to determine the space required to print logical blocks of tokens; the second uses this information to decide where to break lines of text; the two processes communicate by means of a buffer of size O(m). The algorithm does not wait for the entire stream to be input, but begins printing as soon as it has received a linefull of input. The algorithm is easily implemented.
http://i.stanford.edu/pub/cstr/reports/cs/tr/79/770/CS-TR-79-770.pdf