src/cmd/mpm/page.cc - plan9 - Git at Google

 #include	"misc.h"
 #include	"slug.h"
 #include	"range.h"
 #include	"page.h"

 const int	MAXRANGES	= 1000;
 static range *ptemp[MAXRANGES];		// for movefloats()

 static void swapright(int n)		// used by movefloats()
 {
 	range *t = ptemp[n];
 	ptemp[n] = ptemp[n+1];
 	ptemp[n+1] = t;
 	ptemp[n]->setaccum( ptemp[n+1]->accum() -
 			    ptemp[n+1]->rawht() + ptemp[n]->rawht() );
 	ptemp[n+1]->setaccum( ptemp[n]->accum() + ptemp[n+1]->rawht() );
 }

 // Figure out the goal position for each floating range on scratch,
 // and move it past stream ranges until it's as close to its goal as possible.
 static void movefloats(stream *scratch, double scale)
 {
 	int nranges, i;
 	const int Huge = 100000;

 	for (nranges = 0; scratch->more(); scratch->advance())
 		ptemp[nranges++] = scratch->current();
 	scratch->freeall();
 	ufrange rtemp;
 	ptemp[nranges] = &rtemp;
 	rtemp.setgoal(Huge);
 	int accumV = 0;				// compute accum values and
 	for (i = 0; i < nranges; i++) {		// pick closest goal for floats
 		ptemp[i]->pickgoal(accumV, scale);
 		ptemp[i]->setaccum(accumV += ptemp[i]->rawht());
 	}
 	int j;					// index for inner loop below:
 	for (i = nranges; --i >= 0; )		// stably sort floats to bottom
 		for (j = i; j < nranges; j++)
 			if (ptemp[j]->goal() > ptemp[j+1]->goal())
 				swapright(j);
 			else
 				break;
 	if (dbg & 16)
 		printf("#movefloats:  before floating, from bottom:\n");
 	for (i = nranges; --i >= 0; ) {		// find topmost float
 		if (ptemp[i]->goal() == NOGOAL)
 			break;
 		if (dbg & 16)
 			printf("# serialno %d goal %d height %d\n",
 				ptemp[i]->serialno(), ptemp[i]->goal(),
 				ptemp[i]->rawht());
 	}					// i+1 is topmost float
 	for (i++ ; i < nranges; i++)		// move each float up the page
 		for (j = i; j > 0; j--)		// as long as closer to its goal
 			if (ptemp[j]->goal()
 			  <= ptemp[j-1]->accum() + ptemp[j]->rawht()/2
 			  && ptemp[j-1]->goal() == NOGOAL)
 				swapright(j-1);
 			else
 				break;
 	if (ptemp[nranges] != &rtemp)
 		ERROR "goal sentinel has disappeared from movefloats" FATAL;
 	for (i = 0; i < nranges; i++)		// copy sorted list back
 		scratch->append(ptemp[i]);
 }

 // Traverse the leaves of a tree of ranges, filtering out only SP and VBOX.
 static range *filter(generator *g)
 {
 	range *r;
 	while ((r = g->next()) != 0)
 		if (r->isvbox() || r->issp())
 			break;
 	return r;
 }

 // Zero out leading and trailing spaces; coalesce adjacent SP's.
 static void trimspace(stream *scratch)
 {
 	generator g;
 	range *r, *prevr = 0;

 	for (g = scratch; (r = filter(&g)) != 0 && r->issp(); prevr = r)
 		r->setheight(0);		// zap leading SP
 	for ( ; (r = filter(&g)) != 0; prevr = r)
 		if (r->issp())
 			if (prevr && prevr->issp()) {
 						// coalesce adjacent SPs
 				r->setheight(max(r->rawht(), prevr->height()));
 				prevr->setheight(0);
 			} else			// a VBOX intervened
 				r->setheight(r->rawht());
 	if (prevr && prevr->issp())		// zap *all* trailing space
 		prevr->setheight(0);		// (since it all coalesced
 						// into the last one)
 }

 // Pad the non-zero SP's in scratch so the total height is wantht.
 // Note that the SP values in scratch are not the raw values, and
 // indeed may already have been padded.
 static void justify(stream *scratch, int wantht)
 {
 	range *r;
 	int nsp = 0, hsp = 0;

 	int adjht = scratch->height();
 					// Find all the spaces.
 	generator g;
 	for (g = scratch; (r = g.next()) != 0; )
 		if (r->issp() && r->height() > 0) {
 			nsp++;
 			hsp += r->height();
 		}
 	int excess = wantht - adjht;
 	if (excess < 0)
 		ERROR "something on page %d is oversize by %d\n",
 			userpn, -excess WARNING;
 	if (dbg & 16)
 		printf("# justify %d: excess %d nsp %d hsp %d adjht %d\n",
 			userpn, excess, nsp, hsp, adjht);
 	if (excess <= 0 || nsp == 0)
 		return;
 					// Redistribute the excess space.
 	for (g = scratch; (r = g.next()) != 0; )
 		if (r->issp() && r->height() > 0) {
 			int delta = (int) ((float)(r->height()*excess)/hsp + 0.5);
 			if (dbg & 16)
 				printf("# pad space %d by %d: hsp %d excess %d\n",
 					r->height(), delta, hsp, excess);
 			r->setheight(r->height() + delta);
 		}
 }

 // If r were added to s, would the height of the composed result be at most maxht?
 int wouldfit(range *r, stream *s, int maxht)
 {
 	if (r->rawht() + s->rawht() <= maxht)
 		return 1;		// the conservative test succeeded
 	stream scratch;			// local playground for costly test
 	for (stream cd = *s; cd.more(); cd.advance())
 		scratch.append(cd.current());
 	scratch.append(r);
 	movefloats(&scratch, ((double) scratch.rawht())/maxht);
 	trimspace(&scratch);
 	int retval = scratch.height() <= maxht;
 	scratch.freeall();
 	return retval;
 }

 // If s1 were added to s, would the height of the composed result be at most maxht?
 // The computational structure is similar to that above.
 int wouldfit(stream *s1, stream *s, int maxht)
 {
 	if (s1->rawht() + s->rawht() <= maxht)
 		return 1;
 	stream scratch, cd;
 	for (cd = *s; cd.more(); cd.advance())
 		scratch.append(cd.current());
 	for (cd = *s1; cd.more(); cd.advance())
 		scratch.append(cd.current());
 	movefloats(&scratch, ((double) scratch.rawht())/maxht);
 	trimspace(&scratch);
 	int retval = scratch.height() <= maxht;
 	scratch.freeall();
 	return retval;
 }

 // All of stream *s is destined for one column or the other; which is it to be?
 void multicol::choosecol(stream *s, int goalht)
 {
 	stream *dest;
 	if (!leftblocked && wouldfit(s, &(column[0]), goalht))
 		dest = &(column[0]);
 	else {
 		dest = &(column[1]);
 		if (!s->current()->floatable())
 					// a stream item is going into the right
 					// column, so no more can go into the left.
 			leftblocked = 1;
 	}
 	for (stream cd = *s; cd.more(); cd.advance())
 		dest->append(cd.current());
 }

 double coltol = 0.5;

 // Try, very hard, to put everything in the multicol into two columns
 // so that the total height is at most htavail.
 void multicol::compose(int defonly)
 {
 	if (!nonempty()) {
 		setheight(0);
 		return;
 	}
 	scratch.freeall();	// fill scratch with everything destined
 				// for either column
 	stream cd;
 	for (cd = definite; cd.more(); cd.advance())
 		scratch.append(cd.current());
 	if (!defonly)
 		for (cd = *(currpage->stage); cd.more(); cd.advance())
 			if (cd.current()->numcol() == 2)
 				scratch.append(cd.current());
 	scratch.restoreall();		// in particular, floatables' goals
 	int i;
 	int rawht = scratch.rawht();
 	int halfheight = (int)(coltol*rawht);
 					// choose a goal height
 	int maxht = defonly ? halfheight : htavail;
 secondtry:
 	for (i = 0; i < 2; i++)
 		column[i].freeall();
 	leftblocked = 0;
 	cd = scratch;
 	while (cd.more()) {
 		queue ministage;	// for the minimally acceptable chunks
 		ministage.freeall();	// that are to be added to either column
 		while (cd.more() && !cd.current()->issentinel()) {
 			ministage.enqueue(cd.current());
 			cd.advance();
 		}
 		choosecol(&ministage, maxht);
 		if (cd.more() && cd.current()->issentinel())
 			cd.advance();	// past sentinel
 	}
 	if (height() > htavail && maxht != htavail) {
 					// We tried to balance the columns, but
 					// the result was too tall.  Go back
 					// and try again with the less ambitious
 					// goal of fitting the space available.
 		maxht = htavail;
 		goto secondtry;
 	}
 	for (i = 0; i < 2; i++) {
 		movefloats(&(column[i]), ((double) column[i].rawht())/currpage->pagesize);
 		trimspace(&(column[i]));
 	}
 	if (dbg & 32) {
 		printf("#multicol::compose: htavail %d maxht %d dv %d\n",
 			htavail, maxht, height());
 		dump();
 	}
 	if (defonly)
 		stretch(height());
 }

 // A sequence of two-column ranges waits on the stage.
 // So long as the page's skeleton hasn't changed--that is, the maximum height
 // available to the two-column chunk is the same--we just use the columns that
 // have been built up so far, and choose a column into which to put the stage.
 // If the skeleton has changed, however, then we may need to make entirely
 // new decisions about which column gets what, so we recompose the whole page.
 void multicol::tryout()
 {
 	if (htavail == prevhtavail)
 		choosecol(currpage->stage, htavail);
 	else
 		currpage->compose(DRAFT);
 	prevhtavail = htavail;
 }

 // Make both columns the same height.
 // (Maybe this should also be governed by minfull,
 // to prevent padding very underfull columns.)
 void multicol::stretch(int wantht)
 {
 	if (wantht < height())
 		ERROR "page %d: two-column chunk cannot shrink\n", userpn FATAL;
 	for (int i = 0; i < 2; i++)
 		justify(&(column[i]), wantht);
 	if (dbg & 16)
 		printf("#col hts: left %d right %d\n",
 			column[0].height(), column[1].height());
 }

 // Report an upper bound on how tall the current two-column object is.
 // The (possibly composed) heights of the two columns give a crude upper
 // bound on the total height.  If the result is more than the height
 // available for the two-column object, then the columns are each
 // composed to give a better estimate of their heights.
 int multicol::height()
 {
 	int retval = max(column[0].height(), column[1].height());
 	if (retval < htavail)
 		return retval;
 	for (int i = 0; i < 2; i++) {
 		movefloats(&(column[i]), ((double) column[i].height())/currpage->pagesize);
 		trimspace(&(column[i]));
 	}
 	return max(column[0].height(), column[1].height());
 }

 void multicol::dump()
 {
 	printf("####2COL dv %d\n", height());
 	printf("# left column:\n");
 	column[0].dump();
 	printf("# right column:\n");
 	column[1].dump();
 }

 // From the head of queue qp, peel off a piece whose raw height is at most space.
 int peeloff(stream *qp, int space)
 {
 	stream *s1 = qp->current()->children();
 	if (!(s1 && s1->more() && s1->current()->height() <= space))
 					// in other words, either qp's head is
 					// not nested, or its first subrange
 		return 0;		// is also too big, so we give up
 	qp->split();
 	s1 = qp->current()->children();
 	stream *s2 = qp->next()->children();
 	while (s2->more() && s2->current()->rawht() <= space) {
 		s1->append(s2->current());
 		space -= s2->current()->rawht();
 		s2->advance();
 	}
 	return 1;
 }

 // There are four possibilities for consecutive calls to tryout().
 // If we're processing a sequence of single-column ranges, tryout()
 // uses the original algorithm: (1) conservative test; (2) costly test;
 // (3) split a breakable item.
 // If we're processing a sequence of double-column ranges, tryout()
 // defers to twocol->tryout(), which gradually builds up the contents
 // of the two columns until they're as tall as they can be without
 // exceeding twocol->htavail.
 // If we're processing a sequence of single-column ranges and we
 // get a double-column range, then we use compose() to build a
 // skeleton page and set twocol->htavail, the maximum height that
 // should be occupied by twocol.
 // If we're processing a sequence of double-column ranges and we
 // get a single-column range, then we should go back and squish
 // the double-column chunk as short as possible before we see if
 // we can fit the single-column range.
 void page::tryout()
 {
 	if (!stage->more())
 		ERROR "empty stage in page::tryout()\n" FATAL;
 	int curnumcol = stage->current()->numcol();
 	if (dbg & 32) {
 		printf("#page::tryout(): ncol = %d, prevncol = %d; on stage:\n",
 			curnumcol, prevncol);
 		stage->dump();
 		printf("#END of stage contents\n");
 	}
 	switch(curnumcol) {
 	default:
 		ERROR "unexpected number of columns in tryout(): %d\n",
 			stage->current()->numcol() FATAL;
 		break;
 	case 1:
 		if (prevncol == 2)
 			compose(FINAL);
 		if (wouldfit(stage, &definite, pagesize - twocol->height()))
 			commit();
 		else if (stage->current()->breakable() || blank()
 			&& peeloff(stage,
 				pagesize - (definite.height() + twocol->height()))) {
 			// first add the peeled-off part that fits
 			adddef(stage->dequeue());
 			// then send the rest back for later
 			stage->current()->setbreaking();
 			welsh();
 		} else if (blank()) {
 			stage->current()->rdump();
 			ERROR "A %s is too big to continue.\n",
 			stage->current()->typename() FATAL;
 		} else
 			welsh();
 		break;
 	case 2:
 		if (prevncol == 1)
 			compose(DRAFT);
 		else
 			twocol->tryout();
 		if (scratch.height() <= pagesize)
 			commit();
 		else
 			welsh();
 		break;
 	}
 	prevncol = curnumcol;
 }

 // To compose the page, we (1) fill scratch with the stuff that's meant to
 // go on the page; (2) compose scratch as best we can; (3) set the maximum
 // height available to the two-column part of the page; (4) have the two-
 // column part compose itself.
 // In the computation of twocol->htavail, it does not matter that
 // twocol->height() is merely an upper bound, because it is merely being
 // subtracted out to give the exact total height of the single-column stuff.
 void page::compose(int final)
 {
 	makescratch(final);
 	int adjht = scratch.rawht();
 	if (dbg & 16)
 		printf("# page %d measure %d\n", userpn, adjht);
 	movefloats(&scratch, ((double) adjht)/pagesize);
 	trimspace(&scratch);
 	twocol->htavail = pagesize - (scratch.height() - twocol->height());
 	twocol->compose(final);
 	adjht = scratch.height();
 	if (dbg & 16)
 		printf("# page %d measure %d after trim\n", userpn, adjht);
 }

 // Fill the scratch area with ranges destined for the page.
 // If defonly == 0, then add anything that's on stage--this is a trial run.
 // If defonly != 0, use only what's definitely on the page.
 void page::makescratch(int defonly)
 {
 	scratch.freeall();
 	stream cd;
 	for (cd = definite; cd.more(); cd.advance())
 		scratch.append(cd.current());
 	if (!defonly)
 		for (cd = *stage; cd.more(); cd.advance())
 			if (cd.current()->numcol() == 1)
 				scratch.append(cd.current());
 	if (twocol->nonempty())
 		scratch.append(twocol);
 }

 // Accept the current contents of the stage.
 // If the stage contains two-column ranges, add a sentinel to indicate the end
 // of a chunk of stage contents.
 void page::commit()
 {
 	if (dbg & 4)
 		printf("#entering page::commit()\n");
 	int numcol = 0;
 	while (stage->more()) {
 		numcol = stage->current()->numcol();
 		adddef(stage->dequeue());
 	}
 	if (numcol == 2)
 		adddef(new sentrange);
 }

 // Send the current contents of the stage back to its source.
 void page::welsh()
 {
 	if (dbg & 4)
 		printf("#entering page::welsh()\n");
 	while (stage->more()) {
 		range *r = stage->dequeue();
 		r->enqueue(ANDBLOCK);
 	}
 }

 enum { USonly = 1 };

 // So long as anything is eligible to go onto the page, keep trying.
 // Once nothing is eligible, compose and justify the page.
 void page::fill()
 {
 	while (stage->prime())
 		stage->pend();
 	compose(FINAL);
 	if (dbg & 16)
 		scratch.dump();
 	if (anymore()) {
 		int adjht = scratch.height();
 		if (adjht > minfull*pagesize) {
 			justify(&scratch, pagesize);
 			adjht = scratch.height();
 			int stretchamt = max(pagesize - adjht, 0);
 			twocol->stretch(twocol->height() + stretchamt);
 					// in case the page's stretchability lies
 					// entirely in its two-column part
 		} else
 			ERROR "page %d only %.0f%% full; will not be adjusted\n",
 				userpn, 100*(double) adjht/pagesize WARNING;
 	}
 }

 void page::adddef(range *r)
 {
 	if (dbg & 4)
 		printf("#entering page::adddef()\n");
 	switch (r->numcol()) {
 	case 1:	definite.append(r);
 		break;
 	case 2: twocol->definite.append(r);
 		break;
 	default: ERROR "%d-column range unexpected\n", r->numcol() FATAL;
 	}
 }

 int multicol::print(int cv, int col)
 {
 	if (col != 0)
 		ERROR "multicolumn output must start in left column\n" FATAL;
 	int curv = cv, maxv = cv;	// print left column
 	for ( ; column[0].more(); column[0].advance()) {
 		curv = column[0].current()->print(curv, 0);
 		maxv = max(maxv, curv);
 	}
 	curv = cv;			// print right column
 	for ( ; column[1].more(); column[1].advance()) {
 		curv = column[1].current()->print(curv, 1);
 		maxv = max(maxv, curv);
 	}
 	return maxv;
 }

 void page::print()
 {
 	static int tops = 1, bots = 1;
 	if (!scratch.more()) {
 		ERROR "## Here's what's left on squeue:\n" WARNING;
 		squeue.dump();
 		ERROR "## Here's what's left on bfqueue:\n" WARNING;
 		bfqueue.dump();
 		ERROR "## Here's what's left on ufqueue:\n" WARNING;
 		ufqueue.dump();
 		ERROR "page %d appears to be empty\n", userpn WARNING;
 		fflush(stderr), fflush(stdout), exit(0);
 					// something is very wrong if this happens
 	}
 	printf("p%d\n", userpn);	// print troff output page number
 	if (ptlist.more()) {		// print page header
 		ptlist.current()->print(0, 0);
 		ptlist.advance();
 	} else if (tops) {
 		ERROR "ran out of page titles at %d\n", userpn WARNING;
 		tops = 0;
 	}
 	int curv = 0;
 	printf("V%d\n", curv = pagetop);// print page contents
 	for ( ; scratch.more(); scratch.advance()) {
 		curv = scratch.current()->print(curv, 0);
 	}
 	if (btlist.more()) {		// print page footer
 		btlist.current()->print(0, 0);
 		btlist.advance();
 	} else if (bots) {
 		ERROR "ran out of page bottoms at %d\n", userpn WARNING;
 		bots = 0;
 	}
 	printf("V%d\n", physbot);	// finish troff output page
 }

 int	pagetop	= 0;		// top printing margin
 int	pagebot = 0;		// bottom printing margin
 int	physbot = 0;		// physical bottom of page

 double minfull = 0.9;		// minimum fullness before padding

 int	pn	= 0;		// cardinal page number
 int	userpn	= 0;		// page number derived from PT slugs

 static void makepage()
 {
 	page pg(pagebot - pagetop);
 	++pn;
 	userpn = ptlist.more() ? ptlist.current()->pn() : pn;
 	pg.fill();
 	pg.print();
 }

 static void conv(FILE *fp)
 {
 	startup(fp);		// read slugs, etc.
 	while (anymore())
 		makepage();
 	lastrange->print(0, 0);	// trailer
 	checkout();		// check that everything was printed
 }

 int
 main(int argc, char **argv)
 {
 	static FILE *fp = stdin;
 	progname = argv[0];
 	while (argc > 1 && argv[1][0] == '-') {
 		switch (argv[1][1]) {
 		case 'd':
 			dbg = atoi(&argv[1][2]);
 			if (dbg == 0)
 				dbg = ~0;
 			break;
 		case 'm':
 			minfull = 0.01*atof(&argv[1][2]);
 			break;
 		case 'c':
 			coltol = 0.01*atof(&argv[1][2]);
 			break;
 		case 'w':
 			wantwarn = 1;
 			break;
 		}
 		argc--;
 		argv++;
 	}
 	if (argc <= 1)
 		conv(stdin);
 	else
 		while (--argc > 0) {
 			if (strcmp(*++argv, "-") == 0)
 				fp = stdin;
 			else if ((fp = fopen(*argv, "r")) == NULL)
 				ERROR "can't open %s\n", *argv FATAL;
 			conv(fp);
 			fclose(fp);
 		}
 	exit(0);
 	return 0;	/* gcc */
 }
	#include "misc.h"
	#include "slug.h"
	#include "range.h"
	#include "page.h"

	const int MAXRANGES = 1000;
	static range *ptemp[MAXRANGES]; // for movefloats()

	static void swapright(int n) // used by movefloats()
	{
	range *t = ptemp[n];
	ptemp[n] = ptemp[n+1];
	ptemp[n+1] = t;
	ptemp[n]->setaccum( ptemp[n+1]->accum() -
	ptemp[n+1]->rawht() + ptemp[n]->rawht() );
	ptemp[n+1]->setaccum( ptemp[n]->accum() + ptemp[n+1]->rawht() );
	}

	// Figure out the goal position for each floating range on scratch,
	// and move it past stream ranges until it's as close to its goal as possible.
	static void movefloats(stream *scratch, double scale)
	{
	int nranges, i;
	const int Huge = 100000;

	for (nranges = 0; scratch->more(); scratch->advance())
	ptemp[nranges++] = scratch->current();
	scratch->freeall();
	ufrange rtemp;
	ptemp[nranges] = &rtemp;
	rtemp.setgoal(Huge);
	int accumV = 0; // compute accum values and
	for (i = 0; i < nranges; i++) { // pick closest goal for floats
	ptemp[i]->pickgoal(accumV, scale);
	ptemp[i]->setaccum(accumV += ptemp[i]->rawht());
	}
	int j; // index for inner loop below:
	for (i = nranges; --i >= 0; ) // stably sort floats to bottom
	for (j = i; j < nranges; j++)
	if (ptemp[j]->goal() > ptemp[j+1]->goal())
	swapright(j);
	else
	break;
	if (dbg & 16)
	printf("#movefloats: before floating, from bottom:\n");
	for (i = nranges; --i >= 0; ) { // find topmost float
	if (ptemp[i]->goal() == NOGOAL)
	break;
	if (dbg & 16)
	printf("# serialno %d goal %d height %d\n",
	ptemp[i]->serialno(), ptemp[i]->goal(),
	ptemp[i]->rawht());
	} // i+1 is topmost float
	for (i++ ; i < nranges; i++) // move each float up the page
	for (j = i; j > 0; j--) // as long as closer to its goal
	if (ptemp[j]->goal()
	<= ptemp[j-1]->accum() + ptemp[j]->rawht()/2
	&& ptemp[j-1]->goal() == NOGOAL)
	swapright(j-1);
	else
	break;
	if (ptemp[nranges] != &rtemp)
	ERROR "goal sentinel has disappeared from movefloats" FATAL;
	for (i = 0; i < nranges; i++) // copy sorted list back
	scratch->append(ptemp[i]);
	}

	// Traverse the leaves of a tree of ranges, filtering out only SP and VBOX.
	static range filter(generator g)
	{
	range *r;
	while ((r = g->next()) != 0)
	if (r->isvbox() \|\| r->issp())
	break;
	return r;
	}

	// Zero out leading and trailing spaces; coalesce adjacent SP's.
	static void trimspace(stream *scratch)
	{
	generator g;
	range r, prevr = 0;

	for (g = scratch; (r = filter(&g)) != 0 && r->issp(); prevr = r)
	r->setheight(0); // zap leading SP
	for ( ; (r = filter(&g)) != 0; prevr = r)
	if (r->issp())
	if (prevr && prevr->issp()) {
	// coalesce adjacent SPs
	r->setheight(max(r->rawht(), prevr->height()));
	prevr->setheight(0);
	} else // a VBOX intervened
	r->setheight(r->rawht());
	if (prevr && prevr->issp()) // zap all trailing space
	prevr->setheight(0); // (since it all coalesced
	// into the last one)
	}

	// Pad the non-zero SP's in scratch so the total height is wantht.
	// Note that the SP values in scratch are not the raw values, and
	// indeed may already have been padded.
	static void justify(stream *scratch, int wantht)
	{
	range *r;
	int nsp = 0, hsp = 0;

	int adjht = scratch->height();
	// Find all the spaces.
	generator g;
	for (g = scratch; (r = g.next()) != 0; )
	if (r->issp() && r->height() > 0) {
	nsp++;
	hsp += r->height();
	}
	int excess = wantht - adjht;
	if (excess < 0)
	ERROR "something on page %d is oversize by %d\n",
	userpn, -excess WARNING;
	if (dbg & 16)
	printf("# justify %d: excess %d nsp %d hsp %d adjht %d\n",
	userpn, excess, nsp, hsp, adjht);
	if (excess <= 0 \|\| nsp == 0)
	return;
	// Redistribute the excess space.
	for (g = scratch; (r = g.next()) != 0; )
	if (r->issp() && r->height() > 0) {
	int delta = (int) ((float)(r->height()*excess)/hsp + 0.5);
	if (dbg & 16)
	printf("# pad space %d by %d: hsp %d excess %d\n",
	r->height(), delta, hsp, excess);
	r->setheight(r->height() + delta);
	}
	}

	// If r were added to s, would the height of the composed result be at most maxht?
	int wouldfit(range r, stream s, int maxht)
	{
	if (r->rawht() + s->rawht() <= maxht)
	return 1; // the conservative test succeeded
	stream scratch; // local playground for costly test
	for (stream cd = *s; cd.more(); cd.advance())
	scratch.append(cd.current());
	scratch.append(r);
	movefloats(&scratch, ((double) scratch.rawht())/maxht);
	trimspace(&scratch);
	int retval = scratch.height() <= maxht;
	scratch.freeall();
	return retval;
	}

	// If s1 were added to s, would the height of the composed result be at most maxht?
	// The computational structure is similar to that above.
	int wouldfit(stream s1, stream s, int maxht)
	{
	if (s1->rawht() + s->rawht() <= maxht)
	return 1;
	stream scratch, cd;
	for (cd = *s; cd.more(); cd.advance())
	scratch.append(cd.current());
	for (cd = *s1; cd.more(); cd.advance())
	scratch.append(cd.current());
	movefloats(&scratch, ((double) scratch.rawht())/maxht);
	trimspace(&scratch);
	int retval = scratch.height() <= maxht;
	scratch.freeall();
	return retval;
	}

	// All of stream *s is destined for one column or the other; which is it to be?
	void multicol::choosecol(stream *s, int goalht)
	{
	stream *dest;
	if (!leftblocked && wouldfit(s, &(column[0]), goalht))
	dest = &(column[0]);
	else {
	dest = &(column[1]);
	if (!s->current()->floatable())
	// a stream item is going into the right
	// column, so no more can go into the left.
	leftblocked = 1;
	}
	for (stream cd = *s; cd.more(); cd.advance())
	dest->append(cd.current());
	}

	double coltol = 0.5;

	// Try, very hard, to put everything in the multicol into two columns
	// so that the total height is at most htavail.
	void multicol::compose(int defonly)
	{
	if (!nonempty()) {
	setheight(0);
	return;
	}
	scratch.freeall(); // fill scratch with everything destined
	// for either column
	stream cd;
	for (cd = definite; cd.more(); cd.advance())
	scratch.append(cd.current());
	if (!defonly)
	for (cd = *(currpage->stage); cd.more(); cd.advance())
	if (cd.current()->numcol() == 2)
	scratch.append(cd.current());
	scratch.restoreall(); // in particular, floatables' goals
	int i;
	int rawht = scratch.rawht();
	int halfheight = (int)(coltol*rawht);
	// choose a goal height
	int maxht = defonly ? halfheight : htavail;
	secondtry:
	for (i = 0; i < 2; i++)
	column[i].freeall();
	leftblocked = 0;
	cd = scratch;
	while (cd.more()) {
	queue ministage; // for the minimally acceptable chunks
	ministage.freeall(); // that are to be added to either column
	while (cd.more() && !cd.current()->issentinel()) {
	ministage.enqueue(cd.current());
	cd.advance();
	}
	choosecol(&ministage, maxht);
	if (cd.more() && cd.current()->issentinel())
	cd.advance(); // past sentinel
	}
	if (height() > htavail && maxht != htavail) {
	// We tried to balance the columns, but
	// the result was too tall. Go back
	// and try again with the less ambitious
	// goal of fitting the space available.
	maxht = htavail;
	goto secondtry;
	}
	for (i = 0; i < 2; i++) {
	movefloats(&(column[i]), ((double) column[i].rawht())/currpage->pagesize);
	trimspace(&(column[i]));
	}
	if (dbg & 32) {
	printf("#multicol::compose: htavail %d maxht %d dv %d\n",
	htavail, maxht, height());
	dump();
	}
	if (defonly)
	stretch(height());
	}

	// A sequence of two-column ranges waits on the stage.
	// So long as the page's skeleton hasn't changed--that is, the maximum height
	// available to the two-column chunk is the same--we just use the columns that
	// have been built up so far, and choose a column into which to put the stage.
	// If the skeleton has changed, however, then we may need to make entirely
	// new decisions about which column gets what, so we recompose the whole page.
	void multicol::tryout()
	{
	if (htavail == prevhtavail)
	choosecol(currpage->stage, htavail);
	else
	currpage->compose(DRAFT);
	prevhtavail = htavail;
	}

	// Make both columns the same height.
	// (Maybe this should also be governed by minfull,
	// to prevent padding very underfull columns.)
	void multicol::stretch(int wantht)
	{
	if (wantht < height())
	ERROR "page %d: two-column chunk cannot shrink\n", userpn FATAL;
	for (int i = 0; i < 2; i++)
	justify(&(column[i]), wantht);
	if (dbg & 16)
	printf("#col hts: left %d right %d\n",
	column[0].height(), column[1].height());
	}

	// Report an upper bound on how tall the current two-column object is.
	// The (possibly composed) heights of the two columns give a crude upper
	// bound on the total height. If the result is more than the height
	// available for the two-column object, then the columns are each
	// composed to give a better estimate of their heights.
	int multicol::height()
	{
	int retval = max(column[0].height(), column[1].height());
	if (retval < htavail)
	return retval;
	for (int i = 0; i < 2; i++) {
	movefloats(&(column[i]), ((double) column[i].height())/currpage->pagesize);
	trimspace(&(column[i]));
	}
	return max(column[0].height(), column[1].height());
	}

	void multicol::dump()
	{
	printf("####2COL dv %d\n", height());
	printf("# left column:\n");
	column[0].dump();
	printf("# right column:\n");
	column[1].dump();
	}

	// From the head of queue qp, peel off a piece whose raw height is at most space.
	int peeloff(stream *qp, int space)
	{
	stream *s1 = qp->current()->children();
	if (!(s1 && s1->more() && s1->current()->height() <= space))
	// in other words, either qp's head is
	// not nested, or its first subrange
	return 0; // is also too big, so we give up
	qp->split();
	s1 = qp->current()->children();
	stream *s2 = qp->next()->children();
	while (s2->more() && s2->current()->rawht() <= space) {
	s1->append(s2->current());
	space -= s2->current()->rawht();
	s2->advance();
	}
	return 1;
	}

	// There are four possibilities for consecutive calls to tryout().
	// If we're processing a sequence of single-column ranges, tryout()
	// uses the original algorithm: (1) conservative test; (2) costly test;
	// (3) split a breakable item.
	// If we're processing a sequence of double-column ranges, tryout()
	// defers to twocol->tryout(), which gradually builds up the contents
	// of the two columns until they're as tall as they can be without
	// exceeding twocol->htavail.
	// If we're processing a sequence of single-column ranges and we
	// get a double-column range, then we use compose() to build a
	// skeleton page and set twocol->htavail, the maximum height that
	// should be occupied by twocol.
	// If we're processing a sequence of double-column ranges and we
	// get a single-column range, then we should go back and squish
	// the double-column chunk as short as possible before we see if
	// we can fit the single-column range.
	void page::tryout()
	{
	if (!stage->more())
	ERROR "empty stage in page::tryout()\n" FATAL;
	int curnumcol = stage->current()->numcol();
	if (dbg & 32) {
	printf("#page::tryout(): ncol = %d, prevncol = %d; on stage:\n",
	curnumcol, prevncol);
	stage->dump();
	printf("#END of stage contents\n");
	}
	switch(curnumcol) {
	default:
	ERROR "unexpected number of columns in tryout(): %d\n",
	stage->current()->numcol() FATAL;
	break;
	case 1:
	if (prevncol == 2)
	compose(FINAL);
	if (wouldfit(stage, &definite, pagesize - twocol->height()))
	commit();
	else if (stage->current()->breakable() \|\| blank()
	&& peeloff(stage,
	pagesize - (definite.height() + twocol->height()))) {
	// first add the peeled-off part that fits
	adddef(stage->dequeue());
	// then send the rest back for later
	stage->current()->setbreaking();
	welsh();
	} else if (blank()) {
	stage->current()->rdump();
	ERROR "A %s is too big to continue.\n",
	stage->current()->typename() FATAL;
	} else
	welsh();
	break;
	case 2:
	if (prevncol == 1)
	compose(DRAFT);
	else
	twocol->tryout();
	if (scratch.height() <= pagesize)
	commit();
	else
	welsh();
	break;
	}
	prevncol = curnumcol;
	}

	// To compose the page, we (1) fill scratch with the stuff that's meant to
	// go on the page; (2) compose scratch as best we can; (3) set the maximum
	// height available to the two-column part of the page; (4) have the two-
	// column part compose itself.
	// In the computation of twocol->htavail, it does not matter that
	// twocol->height() is merely an upper bound, because it is merely being
	// subtracted out to give the exact total height of the single-column stuff.
	void page::compose(int final)
	{
	makescratch(final);
	int adjht = scratch.rawht();
	if (dbg & 16)
	printf("# page %d measure %d\n", userpn, adjht);
	movefloats(&scratch, ((double) adjht)/pagesize);
	trimspace(&scratch);
	twocol->htavail = pagesize - (scratch.height() - twocol->height());
	twocol->compose(final);
	adjht = scratch.height();
	if (dbg & 16)
	printf("# page %d measure %d after trim\n", userpn, adjht);
	}

	// Fill the scratch area with ranges destined for the page.
	// If defonly == 0, then add anything that's on stage--this is a trial run.
	// If defonly != 0, use only what's definitely on the page.
	void page::makescratch(int defonly)
	{
	scratch.freeall();
	stream cd;
	for (cd = definite; cd.more(); cd.advance())
	scratch.append(cd.current());
	if (!defonly)
	for (cd = *stage; cd.more(); cd.advance())
	if (cd.current()->numcol() == 1)
	scratch.append(cd.current());
	if (twocol->nonempty())
	scratch.append(twocol);
	}

	// Accept the current contents of the stage.
	// If the stage contains two-column ranges, add a sentinel to indicate the end
	// of a chunk of stage contents.
	void page::commit()
	{
	if (dbg & 4)
	printf("#entering page::commit()\n");
	int numcol = 0;
	while (stage->more()) {
	numcol = stage->current()->numcol();
	adddef(stage->dequeue());
	}
	if (numcol == 2)
	adddef(new sentrange);
	}

	// Send the current contents of the stage back to its source.
	void page::welsh()
	{
	if (dbg & 4)
	printf("#entering page::welsh()\n");
	while (stage->more()) {
	range *r = stage->dequeue();
	r->enqueue(ANDBLOCK);
	}
	}

	enum { USonly = 1 };

	// So long as anything is eligible to go onto the page, keep trying.
	// Once nothing is eligible, compose and justify the page.
	void page::fill()
	{
	while (stage->prime())
	stage->pend();
	compose(FINAL);
	if (dbg & 16)
	scratch.dump();
	if (anymore()) {
	int adjht = scratch.height();
	if (adjht > minfull*pagesize) {
	justify(&scratch, pagesize);
	adjht = scratch.height();
	int stretchamt = max(pagesize - adjht, 0);
	twocol->stretch(twocol->height() + stretchamt);
	// in case the page's stretchability lies
	// entirely in its two-column part
	} else
	ERROR "page %d only %.0f%% full; will not be adjusted\n",
	userpn, 100*(double) adjht/pagesize WARNING;
	}
	}

	void page::adddef(range *r)
	{
	if (dbg & 4)
	printf("#entering page::adddef()\n");
	switch (r->numcol()) {
	case 1: definite.append(r);
	break;
	case 2: twocol->definite.append(r);
	break;
	default: ERROR "%d-column range unexpected\n", r->numcol() FATAL;
	}
	}

	int multicol::print(int cv, int col)
	{
	if (col != 0)
	ERROR "multicolumn output must start in left column\n" FATAL;
	int curv = cv, maxv = cv; // print left column
	for ( ; column[0].more(); column[0].advance()) {
	curv = column[0].current()->print(curv, 0);
	maxv = max(maxv, curv);
	}
	curv = cv; // print right column
	for ( ; column[1].more(); column[1].advance()) {
	curv = column[1].current()->print(curv, 1);
	maxv = max(maxv, curv);
	}
	return maxv;
	}

	void page::print()
	{
	static int tops = 1, bots = 1;
	if (!scratch.more()) {
	ERROR "## Here's what's left on squeue:\n" WARNING;
	squeue.dump();
	ERROR "## Here's what's left on bfqueue:\n" WARNING;
	bfqueue.dump();
	ERROR "## Here's what's left on ufqueue:\n" WARNING;
	ufqueue.dump();
	ERROR "page %d appears to be empty\n", userpn WARNING;
	fflush(stderr), fflush(stdout), exit(0);
	// something is very wrong if this happens
	}
	printf("p%d\n", userpn); // print troff output page number
	if (ptlist.more()) { // print page header
	ptlist.current()->print(0, 0);
	ptlist.advance();
	} else if (tops) {
	ERROR "ran out of page titles at %d\n", userpn WARNING;
	tops = 0;
	}
	int curv = 0;
	printf("V%d\n", curv = pagetop);// print page contents
	for ( ; scratch.more(); scratch.advance()) {
	curv = scratch.current()->print(curv, 0);
	}
	if (btlist.more()) { // print page footer
	btlist.current()->print(0, 0);
	btlist.advance();
	} else if (bots) {
	ERROR "ran out of page bottoms at %d\n", userpn WARNING;
	bots = 0;
	}
	printf("V%d\n", physbot); // finish troff output page
	}

	int pagetop = 0; // top printing margin
	int pagebot = 0; // bottom printing margin
	int physbot = 0; // physical bottom of page

	double minfull = 0.9; // minimum fullness before padding

	int pn = 0; // cardinal page number
	int userpn = 0; // page number derived from PT slugs

	static void makepage()
	{
	page pg(pagebot - pagetop);
	++pn;
	userpn = ptlist.more() ? ptlist.current()->pn() : pn;
	pg.fill();
	pg.print();
	}

	static void conv(FILE *fp)
	{
	startup(fp); // read slugs, etc.
	while (anymore())
	makepage();
	lastrange->print(0, 0); // trailer
	checkout(); // check that everything was printed
	}

	int
	main(int argc, char **argv)
	{
	static FILE *fp = stdin;
	progname = argv[0];
	while (argc > 1 && argv[1][0] == '-') {
	switch (argv[1][1]) {
	case 'd':
	dbg = atoi(&argv[1][2]);
	if (dbg == 0)
	dbg = ~0;
	break;
	case 'm':
	minfull = 0.01*atof(&argv[1][2]);
	break;
	case 'c':
	coltol = 0.01*atof(&argv[1][2]);
	break;
	case 'w':
	wantwarn = 1;
	break;
	}
	argc--;
	argv++;
	}
	if (argc <= 1)
	conv(stdin);
	else
	while (--argc > 0) {
	if (strcmp(*++argv, "-") == 0)
	fp = stdin;
	else if ((fp = fopen(*argv, "r")) == NULL)
	ERROR "can't open %s\n", *argv FATAL;
	conv(fp);
	fclose(fp);
	}
	exit(0);
	return 0; /* gcc */
	}