From: albani@cadlab.sublink.org (Lanfranco Albani)
Newsgroups: comp.os.coherent
Subject: 'fmt' like program with Knuth optimal line break algorithm
Date: 15 Oct 92 09:55:40 GMT
Distribution: comp
Organization: CAD.LAB S.p.A., Bologna, Italia



Sorry for the bandwith waste, but I think this is really useful.
This was posted on comp.editors by Ross Paterson.

Remember: compile it with -VPSTR!

Here the original post:


I have a program that does something like this, though the weightings
are probably screwy, and there are presumably other bugs.  It has an
extra option -p that is sometimes useful, and is a bit more careful
with white space.
--
Ross Paterson <rap@doc.ic.ac.uk>
Department of Computing, Imperial College, London SW7

----------------------------- cut here --------------------------------
: This is a shell archive.
: To unwrap, feed this file as input to /bin/sh
set -e
umask 077
echo x - 'fmt.c'
sed 's/^X//' >'fmt.c' <<'=== End of fmt.c ==='
X#include <stdio.h>
X#include <ctype.h>
X#include "options.h"
X
X/*
X * NAME
X *	fmt - simple text formatter
X *
X * SYNOPSIS
X *	usage: fmt [ -cs ] [ -width ] [ -p prefix ] [ file ... ]
X *
X * DESCRIPTION
X *	Fmt is a simple text formatter, similar to the BSD program fmt(1),
X *	but uses best-fit line breaking, by a simple version of
X *
X *		"Breaking Paragraphs into Lines",
X *		Donald E. Knuth and Michael F. Plass,
X *		"Software--Practice and Experience" 11 (1981) 1119-1184.
X *
X *	Tabs are expanded on input and re-introduced on output.
X *
X * OPTIONS
X *	-c	Crown margin mode.  The indentation of the first line
X *		of a paragraph must be different from the indentation
X *		of the second.  Subsequent lines must have the same
X *		indentation as the second line.
X *
X *	-s	Split lines only.
X *
X *	-width	Maximum line width (default 75).  Fmt prefers to make
X *		lines about 7% shorter, to give it room to balance line
X *		lengths.
X *
X *	-p prefix
X *		Only lines whose non-white text begins with the prefix are
X *		re-arranged; the prefix is stripped for the formatting and
X *		re-attached to each formatted output line.  For example,
X *
X *			fmt -p ' * '
X *
X *		formats C comments laid out in the normal way, leaving
X *		the code unchanged.  The -p option may also be combined
X *		with the other options.
X *
X * BUGS
X *	Very long paragraphs break fmt's limits.  Please send bug reports
X *	and suggestions to the author.
X *
X * AUTHOR
X *	Ross Paterson <rap@doc.ic.ac.uk>
X */
X
X/*
X * The following parameters represent the program's idea of what is "best".
X * Adjust to taste, subject to the caveats given.
X */
X
X#define	WIDTH	75	/* longest permitted line length */
X#define	LEEWAY	15	/* 1/LEEWAY of line is best left unused */
X
X/*
X * Costs and bonuses are expressed as the equivalent departure from
X * the optimal line length, multiplied by 10.
X * e.g. assigning something a cost of 50 means that it is as bad as
X * a line 5 characters too short or long.
X * The definition of SHORT_COST(n) should not be changed.
X * However, EQUIV(n) may need tuning.
X */
X
Xtypedef	long	COST;
X#define	MAXCOST	(~(((COST)1)<<(8*sizeof(COST)-1)))
X
X#define	SQR(n)		((n)*(n))
X#define	EQUIV(n)	SQR((COST)(n))
X
X/* cost of a filled line longer or shorter than best_width */
X#define	SHORT_COST(n)	EQUIV((n)*10)
X/* cost of the difference between adjacent filled lines */
X#define	RAGGED_COST(n)	(SHORT_COST(n)/2)
X
X/* basic cost per line */
X#define	LINE_COST	EQUIV(70)
X/* line break after the first word of a sentence */
X#define	WIDOW_COST	EQUIV(200)
X/* line break before the last word of a sentence */
X#define	ORPHAN_COST	EQUIV(150)
X/* line break at the end of a sentence */
X#define	SENTENCE_BONUS	EQUIV(50)
X/* line break after close parenthesis */
X#define	PAREN_BONUS	EQUIV(40)
X/* line break after other punctuation */
X#define	PUNCT_BONUS	EQUIV(40)
X
X/*
X * program limits: max. words and characters in a paragraph.
X * These are not checked.
X */
X
X#define	MAXWORDS	2000
X#define	MAXCHARS	10000
X
X/*
X * Miscellaneous definitions
X */
X
X#define	reg	register
X
Xtypedef	unsigned natural;
Xtypedef	int	bool;
X#define	TRUE	1
X#define	FALSE	0
X
X/* small versions for use in records */
Xtypedef	char	sbool, sint;
X
X#define	when	break; case
X#define	or	: case
X#define	otherwise	break; default
X
X#define	repeat	for (;;)
X#define	until(c)	if (c) break
X
Xextern	void	trim_prefix();
Xextern	void	fmt();
Xextern	bool	get_paragraph();
Xextern	int	get_line(), get_prefix(), get_space();
Xextern	int	copy_rest();
Xextern	bool	same_para();
Xextern	void	fmt_paragraph();
Xextern	void	check_punctuation();
Xextern	COST	base_cost(), line_cost();
Xextern	void	put_paragraph(), put_line(), put_prefix(), put_space();
X
XFILE	*infile;
Xint	in_column = 0;
Xint	out_column = 0;
X
Xbool	crown = FALSE;
Xbool	split = FALSE;		/* each line is a paragraph on its own */
Xchar	*prefix = "";
Xint	prefix_length;
Xint	prefix_lead_space;
Xint	prefix_full_length;
Xint	max_width = WIDTH;
Xint	best_width;
X
Xmain(argc, argv)
Xreg	int	argc;
Xreg	char	*argv[];
X{
Xreg	int	i;
X
X	OPTIONS	("-cs -width -p prefix [ file ... ]")
X		FLAG	('c', crown)
X		FLAG	('s', split)
X		NUM_OPT	(max_width)
X		STRING	('p', prefix)
X	ENDOPTS
X	best_width = max_width*(LEEWAY-1)/LEEWAY;
X	trim_prefix();
X
X	if (argc == 1) {
X		infile = stdin;
X		fmt();
X	}
X	else
X		for (i = 1; i < argc; i++)
X			if ((infile = fopen(argv[i], "r")) == NULL)
X				fprintf(stderr, "%s: can't read file '%s'\n",
X					argv[0], argv[i]);
X			else {
X				fmt();
X				fclose(infile);
X			}
X	exit(0);
X}
X
Xvoid
Xtrim_prefix()
X{
Xreg	char	*s;
X
X	prefix_lead_space = 0;
X	while (*prefix == ' ') {
X		prefix_lead_space++;
X		prefix++;
X	}
X	prefix_full_length = strlen(prefix);
X	s = prefix + prefix_full_length;
X	while (s > prefix && s[-1] == ' ')
X		s--;
X	*s = '\0';
X	prefix_length = s - prefix;
X}
X
Xint	next_char;	/* one-character look-ahead */
Xchar	*to_match = "";
X
Xvoid
Xfmt()
X{
X	next_char = get_prefix();
X	while (get_paragraph()) {
X		fmt_paragraph();
X		put_paragraph();
X	}
X}
X
X#define	WORD	struct _WORD
X
XWORD {
X	/* static attributes determined during input */
X	char	*text;
X	sint	length;
X	sint	space;		/* the size of the following space */
X	sbool	paren;		/* starts with open paren */
X	sbool	period;		/* ends in [.?!])* */
X	sbool	punct;		/* ends in punctuation */
X	/* the remaining fields are computed during the optimization */
X	sint	line_length;	/* length of the best line starting here */
X	COST	best_cost;
X	WORD	*next_break;	/* break which achieves best_cost */
X};
X
XWORD	word[MAXWORDS];
XWORD	*word_limit;
Xchar	*wptr;
X
Xint	first_indent;	/* indentation of first line */
Xint	indent;		/* indentation of rest of current paragraph */
Xint	prefix_indent;
Xint	next_prefix_indent;
Xbool	tabs = FALSE;	/* tabs in input? */
X
X/*
X * Definitions.
X *
X * A <paragraph> is a maximal non-empty set of consecutive non-blank
X * lines at the same indent.
X * In split mode, a paragraph is a single non-blank line.
X * In crown mode, the second and subsequent lines must have the same
X * indentation, but differing from the first line.
X * If a prefix is in effect, it must also be at the same indent for
X * each line in the paragraph.
X *
X * A <word> is a maximal non-empty set of non-white characters.
X *
X * A <sentence break> is either the end of a paragraph or a word ending
X * in [.?!], possibly followed by ) or ], followed by a word beginning
X * with a capital.
X */
X
Xbool
Xget_paragraph()
X{
Xreg	int	c;
Xstatic	char	parabuf[MAXCHARS];	/* space for the paragraph text */
X
X	c = next_char;
X	/*
X	 * Scan (and copy) blank lines,
X	 * and lines not introduced by the prefix.
X	 */
X	while (c == '\n' || *to_match ||
X	       next_prefix_indent < prefix_lead_space ||
X	       in_column < next_prefix_indent + prefix_full_length) {
X		if (prefix_length != 0)
X			c = copy_rest(c);
X	until(c == EOF);
X		putchar('\n');
X		c = get_prefix();
X	}
X	if (c == EOF) {
X		next_char = EOF;
X		return FALSE;
X	}
X	prefix_indent = next_prefix_indent;
X	wptr = parabuf;
X	word_limit = word;
X	if (split) {
X		first_indent = indent = in_column;
X		c = get_line(c);
X	}
X	else if (crown) {
X		first_indent = in_column;
X		c = get_line(c);
X		if (same_para(c) && in_column != first_indent) {
X			indent = in_column;
X			do {	/* for each line till the end of the para */
X				c = get_line(c);
X			} while (same_para(c) && in_column == indent);
X		}
X		/*
X		 * If only one line, use the secondary indent
X		 * from last time (initially 0) if it splits.
X		 */
X	}
X	else {
X		first_indent = indent = in_column;
X		do {	/* for each line till the end of the para */
X			c = get_line(c);
X		} while (same_para(c) && in_column == indent);
X	}
X	(word_limit-1)->period = TRUE;
X	next_char = c;
X	return TRUE;
X}
X
X/*
X * Copy a line which failed to match the prefix to the output,
X * or which was blank after the prefix.
X *
X * In the former case, c is the character that failed to match *to_match.
X * In the latter, c is \n or EOF.
X * Returns the character ending the line.
X */
Xint
Xcopy_rest(c)
Xreg	int	c;
X{
Xreg	char	*s;
X
X	out_column = 0;
X	put_space(next_prefix_indent);
X	for (s = prefix; s != to_match; s++)
X		putchar(*s);
X	if (c != '\n' && c != EOF) {
X		out_column += to_match - prefix;
X		put_space(in_column - out_column);
X		do {
X			putchar(c);
X			c = getc(infile);
X		} while (c != '\n' && c != EOF);
X	}
X	return c;
X}
X
Xbool
Xsame_para(c)
Xreg	int	c;
X{
X	return next_prefix_indent == prefix_indent && *to_match == '\0' &&
X	       c != '\n' && c != EOF;
X}
X
X/*
X * Read a line, given first non-blank character c, and the following
X * indent, returning the first non-blank character of the next line.
X */
Xint
Xget_line(c)
Xreg	int	c;
X{
X	int	start;
X
X	do {	/* for each word in a line */
X		/* scan word */
X		if (islower(c) && word_limit != word)
X			(word_limit-1)->period = FALSE;
X		word_limit->text = wptr;
X		do {
X			*wptr++ = c;
X			c = getc(infile);
X		} while (c != EOF && ! isspace(c));
X		check_punctuation(word_limit, wptr-1);
X		in_column += word_limit->length = wptr - word_limit->text;
X		*wptr++ = '\0';
X		/* scan inter-word space */
X		start = in_column;
X		c = get_space(c);
X		word_limit->space = in_column - start;
X		word_limit++;
X		if (c == EOF)
X			return EOF;
X	} while (c != '\n');
X	c = get_prefix();
X	(word_limit-1)->space =
X		c != EOF && ! islower(c) && (word_limit-1)->period ? 2 : 1;
X	return c;
X}
X
Xint
Xget_prefix()
X{
Xreg	int	c;
X
X	in_column = 0;
X	c = get_space(getc(infile));
X	to_match = prefix;
X	if (prefix_length == 0)
X		next_prefix_indent = 0;
X	else {
X		next_prefix_indent = in_column;
X		while (*to_match && c == *to_match) {
X			in_column++;
X			to_match++;
X			c = getc(infile);
X		}
X		if (*to_match == '\0')
X			c = get_space(c);
X	}
X	return c;
X}
X
X/*
X * Scan blank characters, keeping in_column up-to-date.
X */
Xint
Xget_space(c)
Xreg	int	c;
X{
X	repeat {
X		if (c == ' ')
X			in_column++;
X		else if (c == '\t') {
X			tabs = TRUE;
X			in_column = (in_column/8 + 1)*8;
X		}
X		else
X			return c;
X		c = getc(infile);
X	}
X}
X
Xvoid
Xcheck_punctuation(w, finish)
Xreg	WORD	*w;
Xreg	char	*finish;
X{
Xreg	char	*start;
Xreg	int	c;
X
X	start = w->text;
X
X	c = *start;
X	w->paren = c == '(' || c == '[';
X
X	c = *finish;
X	w->punct = ispunct(c);
X	while ((c == ')' || c == ']' || c == '\'' || c == '"') &&
X	       finish > start)
X		c = *--finish;
X	w->period = c == '.' || c == '?' || c == '!';
X}
X
X/*
X * Compute the optimal formatting for the whole paragraph by computing and
X * remembering the optimal formatting for each suffix from the empty one
X * to the whole paragraph.
X */
Xvoid
Xfmt_paragraph()
X{
Xreg	WORD	*start, *w;
Xreg	int	len;
Xreg	COST	wcost, best;
X
X	word_limit->best_cost = 0;
X	word_limit->length = max_width;		/* sentinel */
X
X	for (start = word_limit-1; start >= word; start--) {
X		best = MAXCOST;
X		len = start == word ? first_indent : indent;
X		/* at least one word, however long, in the line */
X		w = start;
X		len += w->length;
X		do {
X			w++;
X			/* consider breaking before w */
X			wcost = line_cost(w, len) + w->best_cost;
X			if (wcost < best) {
X				best = wcost;
X				start->next_break = w;
X				start->line_length = len;
X			}
X			len += (w-1)->space;	/* w > start >= word */
X			len += w->length;
X		} while (len < max_width);
X		start->best_cost = best + base_cost(start);
X	}
X}
X
X/* constant component of cost of breaking before this word */
XCOST
Xbase_cost(this)
Xreg	WORD	*this;
X{
Xreg	COST	cost;
X
X	cost = LINE_COST;
X
X	if (this > word)
X		if ((this-1)->period)
X			cost -= SENTENCE_BONUS;
X		else if ((this-1)->punct)
X			cost -= PUNCT_BONUS;
X		else if (this > word+1 && (this-2)->period)
X			cost += WIDOW_COST/((this-1)->length+2);
X
X	if (this->paren)
X		cost -= PAREN_BONUS;
X	else if (this->period)
X		cost += ORPHAN_COST/(this->length+2);
X
X	return cost;
X}
X
X/* length-dependent component of cost of breaking at next */
XCOST
Xline_cost(next, len)
Xreg	WORD	*next;
Xreg	int	len;
X{
Xreg	int	n;
Xreg	COST	cost;
X
X	if (next == word_limit)
X		return 0;
X	n = best_width - len;
X	cost = SHORT_COST(n);
X	if (next->next_break != word_limit) {
X		n = len - next->line_length;
X		cost += RAGGED_COST(n);
X	}
X	return cost;
X}
X
Xvoid
Xput_paragraph()
X{
Xreg	WORD	*w;
X
X	out_column = 0;
X	put_prefix(first_indent);
X	put_line(word);
X	for (w = word->next_break; w != word_limit; w = w->next_break) {
X		put_prefix(indent);
X		put_line(w);
X	}
X}
X
Xvoid
Xput_line(w)
Xreg	WORD	*w;
X{
Xreg	WORD	*endline;
X
X	endline = w->next_break-1;
X	out_column += w->length;
X	fputs(w->text, stdout);
X	while (w != endline) {
X		put_space(w->space);
X		w++;
X		fputs(w->text, stdout);
X		out_column += w->length;
X	}
X	putchar('\n');
X}
X
Xvoid
Xput_prefix(space)
X	int	space;
X{
X	out_column = 0;
X	put_space(prefix_indent);
X	fputs(prefix, stdout);
X	out_column += prefix_length;
X	put_space(space - out_column);
X}
X
Xvoid
Xput_space(space)
X	int	space;
X{
Xreg	int	space_target, tab_target;
X
X	space_target = out_column + space;
X	if (tabs) {
X		tab_target = space_target/8*8;
X		if (out_column+1 < tab_target)
X			while (out_column < tab_target) {
X				putchar('\t');
X				out_column = (out_column/8 + 1)*8;
X			}
X	}
X	while (out_column < space_target) {
X		putchar(' ');
X		out_column++;
X	}
X}
=== End of fmt.c ===
chmod u=rw,g=r,o=r 'fmt.c'
echo x - 'options.h'
sed 's/^X//' >'options.h' <<'=== End of options.h ==='
X/*
X *	Option processing.
X *
X *	Conforms to intro(1) in System V.
X *
X *	Typical layout:
X *
X *		OPTIONS ("-b -t c -f file -w N +b file ...")
X *			FLAG	('b', flag)
X *			CHAR	('t', tab_ch)
X *			STRING	('f', filename)
X *				f = fopen(filename, "r");
X *			NUMBER	('w', width)
X *		MORE_OPTIONS('+')
X *			FLAG	('b', unflag)
X *		ENDOPTS
X *
X */
Xchar	*O_name, *O_usage;
X
Xvoid
Xusage()
X{
X	/*
X	 * Poor man's version of:
X	 *
X	 *	fprintf(stderr, "Usage: %s %s\n", O_name, O_usage);
X	 */
X	write(2, "Usage: ", 7);
X	write(2, O_name, strlen(O_name));
X	write(2, " ", 1);
X	write(2, O_usage, strlen(O_usage));
X	write(2, "\n", 1);
X	exit(1);
X}
X
X/*
X *	An argument "-" is interpreted as a program argument and stops
X *	option processing.
X *
X *	An argument "--" stops option processing and is discarded.
X *
X *	An option which takes an argument uses either the rest of the
X *	the current argument, or, if at the end of an argument, the
X *	next argument.
X */
X#define OPTIONS(usage)							\
X	O_usage = usage;						\
X	O_name = argv[0];						\
X	while (*++argv) {						\
X		register int O_cont = 1;				\
X									\
X		if (**argv == '-') {					\
X			if (argv[0][1] == '\0')				\
X				break;					\
X			argc--;						\
X			if (argv[0][1] == '-' && argv[0][2] == '\0') {	\
X				argv++;					\
X				break;					\
X			}						\
X			while (O_cont)					\
X				switch (*++*argv) {			\
X				case '\0':				\
X					O_cont = 0;
X
X#define FLAG(c,flag)		break;					\
X				case c:					\
X					flag = 1;
X
X#define NUMBER(c,num)		break;					\
X				case c:					\
X					if (*++*argv == '\0') {		\
X						if (--argc == 0)	\
X							usage();	\
X						argv++;			\
X					}				\
X					num = atoi(*argv);		\
X					O_cont = 0;
X
X#define NUM_OPT(num)		break;					\
X				case '0': case '1': case '2': case '3':	\
X				case '4': case '5': case '6': case '7':	\
X				case '8': case '9':			\
X					num = atoi(*argv);		\
X					O_cont = 0;
X
X#define STRING(c,str)		break;					\
X				case c:					\
X					if (*++*argv == '\0') {		\
X						if (--argc == 0)	\
X							usage();	\
X						argv++;			\
X					}				\
X					str = *argv;			\
X					O_cont = 0;
X
X#define CHAR(c,ch)		break;					\
X				case c:					\
X					if (*++*argv == '\0') {		\
X						if (--argc == 0)	\
X							usage();	\
X						argv++;			\
X					}				\
X					ch = **argv;			\
X					O_cont = 0;
X
X#define MORE_OPTIONS(c)		break;					\
X				default:				\
X					usage();			\
X				}					\
X		}							\
X		else if (**argv == (c)) {				\
X			if (argv[0][1] == '\0')				\
X				break;					\
X			argc--;						\
X			while (O_cont)					\
X				switch (*++*argv) {			\
X				case '\0':				\
X					O_cont = 0;
X
X#define ENDOPTS			break;					\
X				default:				\
X					usage();			\
X				}					\
X		}							\
X		else							\
X			break;						\
X	}								\
X	*--argv = O_name;
=== End of options.h ===
chmod u=rw,g=r,o=r 'options.h'
exit 0
----------------------------- cut here --------------------------------



Bye, Lanfranco

-- 
Lanfranco Albani - CAD.LAB s.p.a., v. Ronzani 7/29, Casalecchio, Italia
Email: (work:) albani@cadlab.sublink.org, (home:) bob@allan.sublink.org
Phone: (work:) ++39 (51) 6130360, (home:) ++39 (51) 727372; 
Fax: ++39 (51) 6130294 (work only), Fidonet: 2:332/407.1138 (home only).