[net.sources] Source for text justify fragment

silver (02/16/83)

/*
 * justify lines (part of fmt.c for testing)
 * compile with -DDEBUG for extra output
 */


#include <stdio.h>

#define	LENGTH	72		/* definitions from fmt.c */
int	pfx;
char	*outp;


main ()			/* test routine */
{
	char	buf[BUFSIZ];
	int	left, right;

	while (gets (buf) != NULL) {
		for (left = 0; (left < LENGTH) && (buf[left] == ' '); left++);
		for (right = left; buf[right]; right++);
		justify (buf, left, right-1, LENGTH);
		puts (buf);
	}
}



/*
 * Right-justify one line by padding with blanks:
 * Also sets global outp past new end of buffer.
 */

#define	MAXBLANKS	BUFSIZ/2	/* most blank fields on line */

struct	blank {
	int	pos;			/* where blank is in buf */
	int	size;			/* contiguous blanks in field */
	int	score;			/* total surrounding nonblanks */
	int	insert;			/* blanks to insert here */
};


justify (buf, left, right, margin)
	char	*buf;			/* line to justify */
	int	left;			/* leftmost nonblank character */
	int	right;			/* rightmost character of any kind */
	int	margin;			/* to justify against, base one */
{
	struct	blank	blank[MAXBLANKS];	/* one per blank field in buf */
	struct	blank	*bpa[MAXBLANKS];	/* one per blank[] entry */
	struct	blank	*bp;			/* temp pointer */
	int	blanks = 0;			/* valid entries in blank[] */
	int	b;				/* index into bpa */

	int	c, oldc;		/* positions in buf */
	int	ins, need;		/* number to insert, needed */
	int	to, from;		/* for copying characters */
	int	compare();

	if (left >= --margin)		/* adjust margin to base zero */
		return;			/* can't do anything */
/*
 * set right = last nonblank:
 */

	while ((right > left) && (buf[right] == ' '))
		right--;
	if ((right == left) || (right >= margin))
		return;				/* can't do anything */

#ifdef DEBUG
printf ("%s\nleft:%3d  right:%3d  margin:%3d  need:%3d\n",
	 buf, left, right, margin, margin-right);
#endif

/*
 * scan buf to set up blank[] and bpa[]:
 */

	for (c = oldc = left; c <= right; c++)
		if (buf[c] == ' ') {

			if (blanks)		/* finish previous blank */
				blank[blanks-1].score += c-oldc;

			bp = &blank[blanks];
			bp->pos    = c;
			bp->score  = c-oldc;	/* nonblanks to left */
			bp->insert = 0;		/* for now */

			oldc = c;		/* count and skip blanks */
			while (buf[++c] == ' ')
				;
			bp->size = c-oldc;	/* number of blanks in field */

			bpa[blanks++] = bp;	/* save & each blank[] */
			oldc = c;		/* for next word */
		}

	if (!blanks)	return;			/* no blanks on line */
	bp->score += c-oldc;			/* finish last entry */

/*
 * sort array of pointers to blank[] entries, by values in blank[]:
 */

	qsort (bpa, blanks, sizeof (bpa[0]), compare);

/*
 * assign number of blanks to insert at each field, by going through the
 * sorted pointer array, first adding one blank to those fields with only
 * one blank, then those with one or two, etc:
 */

	need = margin - right;			/* total to insert */

	for (ins = 1; need > 0; ins++) {	/* number to insert this pass */
		b = 0;

		while
		   (   (b < blanks)		/* more places to insert */
		    && ((bpa[b]->size + bpa[b]->insert) == ins) /* same level */
		    && need--)			/* more blanks needed */
			bpa[b++]->insert++;
	}

#ifdef DEBUG
for (b = 0; b < blanks; b++)
	printf ("field:%3d  pos:%3d  size:%3d  score:%3d  ins:%3d\n",
		bpa[b]-blank,  bpa[b]->pos,    bpa[b]->size,
		bpa[b]->score, bpa[b]->insert);
#endif

/*
 * insert blanks in buf:
 */

	from = right;				/* copy from */
	to   = margin;				/* copy to */
	bp   = &blank[blanks-1];		/* rightmost blank field */

	while (to > from) {			/* more to insert */
		buf[to--] = buf[from--];	/* copy one char */
		if (from == bp->pos) {		/* at blank field */
			while (bp->insert--)	/* insert as many as needed */
				buf[to--] = ' ';
			bp--;			/* previous field */
		}
	}

	outp = buf + LENGTH;			/* past new end of buffer */
	return;					/* we're done! */
}


/*
 * Compare two blank[] elements via bpa[] to sort bpa[] by size, ascending,
 * then score, descending:
 * (return > 0) means elements are swapped.
 * Multiply by BUFSIZ gives size priority over score.
 */

int
compare (lp, rp)
	struct	blank	**lp, **rp;
{
	return (BUFSIZ * ((**lp).size  - (**rp).size) +
			 ((**rp).score - (**lp).score));
}