1 #ifndef lint
2 static char sccsid[] = "@(#)vsort.c	1.2 (CWI) 87/11/26";
3 #endif
4 /* vsort.c	1.11	84/05/29
5  *
6  *	Sorts and shuffles ditroff output for versatec wide printer.  It
7  *	puts pages side-by-side on the output, and fits as many as it can
8  *	on one horizontal span.  The versatec driver sees only pages of
9  *	full width, not the individual pages.  Output is sorted vertically
10  *	and bands are created NLINES pixels high.  Any object that has
11  *	ANY part of it in a band is put on that band.
12  *
13  *	Jaap Akkerhuis
14  *	de-Berkletized by #ifdef BERK
15  */
16 
17 
18 #include	<stdio.h>
19 #include	<ctype.h>
20 #include	<math.h>
21 
22 
23 /* #define DEBUGABLE	/* compile-time flag for debugging */
24 #define	FATAL	1
25 #define	NVLIST	3000	/* size of list of vertical spans */
26 #define	OBUFSIZ	250000	/* size of character buffer before sorting */
27 #define	SLOP	1000	/* extra bit of buffer to allow for passing OBUFSIZ */
28 #define MAXVECT	200	/* maximum number of points (vectors) in a polygon */
29 
30 #ifndef FONTDIR
31 #define FONTDIR "/usr/lib/font"
32 #endif FONTDIR
33 
34 #define POINT	72			/* number of points per inch */
35 
36 #ifndef VER80
37 #define WIDTH	7040			/* number of pixels across the page */
38 #else
39 #define WIDTH	2112			/* number of pixels across the page */
40 	/*
41 	 * Note that this does not work unless the input really is
42 	 * designed for the versatec, i.e., res = 200.  But that's
43 	 * OK, because it is only used for side-by-side pages, which
44 	 * we don't do anyway.
45 	 * DD
46 	 */
47 #endif VER80
48 
49 #define BAND	1			/* length of each band in inches */
50 #define NLINES	(int)(BAND * inch)	/* number of pixels in each band */
51 #define HALF	(inch/2)
52 
53 #define hgoto(n)	if((hpos = leftmarg + n) > maxh) maxh = hpos
54 #define hmot(n)		if((hpos += n) > maxh) maxh = hpos
55 #define vmot(n)		vpos += (n)
56 #define vgoto(n)	vpos = (n)
57 
58 
59 int	dbg = 0;	/* debug flag != 0 means do debug output */
60 
61 int	size	= 10;	/* current size (points) */
62 int	up	= 0;	/* number of pixels that the current size pushes up */
63 int	down	= 0;	/* # of pixels that the current size will hang down */
64 int	font	= 1;	/* current font */
65 char *	fontdir = FONTDIR;	/* place to find DESC.out file	*/
66 int	inch	= 200;	/* resolution of the device, in inches	*/
67 
68 /* #ifdef BERK		/* leave this one in for now */
69 int	thick	= 3;	/* line thickness */
70 
71 #ifdef BERK
72 int	stip	= 1;	/* current stipple */
73 int	style	= -1;	/* line style bit-mask */
74 #endif BERK
75 
76 #ifndef BERK
77 int	started;	/* see or we started */
78 #endif
79 
80 int	hpos	= 0;	/* horizontal position to be at next (left = 0) */
81 int	vpos	= 0;	/* current vertical position (down positive) */
82 
83 int	maxh	= 0;	/* farthest right we've gone on the current span */
84 int	leftmarg= 0;	/* current page offset */
85 int	spanno	= 0;	/* current span number for driver in 'p#' commands */
86 int	pageno	= 0;	/* number of pages spread across a physical page */
87 
88 
89 struct vlist {
90 	unsigned short	v;	/* vertical position of this spread */
91 	unsigned short	h;	/* horizontal position */
92 	unsigned short	t;	/* line thickness */
93 #ifdef BERK
94 	short	st;		/* style mask */
95 	unsigned char	l;	/* stipple number */
96 #endif BERK
97 	unsigned short	u;	/* upper extent of height */
98 	unsigned short	d;	/* depth of height */
99 	unsigned short	s;	/* point size */
100 	unsigned char	f;	/* font number */
101 	char	*p;		/* text pointer to this spread */
102 };
103 
104 struct	vlist	vlist[NVLIST + 1];
105 struct	vlist	*vlp;			/* current spread being added to */
106 int	nvlist	= 1;			/* number of spreads in list */
107 int	obufsiz	= OBUFSIZ;
108 char	obuf[OBUFSIZ + SLOP];
109 char	*op = obuf;			/* pointer to current spot in buffer */
110 
111 
112 
113 main(argc, argv)
114 int argc;
115 char *argv[];
116 {
117 	FILE *fp;
118 	double atof();
119 
120 
121 	vlp = &vlist[0];		/* initialize spread pointer */
122 	vlp->p = op;
123 	vlp->v = vlp->d = vlp->u = vlp->h = 0;
124 	vlp->s = size;
125 	vlp->f = font;
126 #ifdef BERK
127 	vlp->l = stip;
128 	vlp->st = style;
129 #endif BERK
130 	vlp->t = thick;
131 
132 	while (argc > 1 && **++argv == '-') {
133 	    switch ((*argv)[1]) {
134 		case 'f':
135 			fontdir = &(*argv)[2];
136 			break;
137 #ifdef DEBUGABLE
138 		case 'd':
139 			dbg = atoi(&(*argv)[2]);
140 			if (!dbg) dbg = 1;
141 			break;
142 		case 's':
143 			if((obufsiz = atoi(&(*argv)[2])) > OBUFSIZ)
144 			    obufsiz = OBUFSIZ;
145 			break;
146 #endif DEBUGABLE
147 	    }
148 	    argc--;
149 	}
150 
151 	if (argc <= 1)
152 	    conv(stdin);
153 	else
154 	    while (--argc > 0) {
155 		if ((fp = fopen(*argv, "r")) == NULL)
156 		    error(FATAL, "can't open %s", *argv);
157 		conv(fp);
158 		fclose(fp);
159 	    }
160 	done();
161 }
162 
163 			/* read number from input:  copy to output */
164 int
165 getnumber (fp)
166 register FILE *fp;
167 {
168 	register int k;
169 	register char c;
170 
171 	while (isspace(c = getc(fp)))
172 	    ;
173 	k = 0;
174 	if (c == '-') {
175 #ifndef BERK
176 	    *op++ = c;		/* should be output as well!!! */
177 #endif BERK
178 	    c = getc(fp);
179 	    do {
180 		k = 10 * k - ((*op++ = c) - '0');
181 	    } while (isdigit(c = getc(fp)));
182 	} else {
183 	    do {
184 		k = 10 * k + (*op++ = c) - '0';
185 	    } while (isdigit(c = getc(fp)));
186 	}
187 	ungetc(c, fp);
188 	return (k);
189 }
190 
191 			/* read number from input:  do _N_O_T copy to output */
192 int
193 ngetnumber (fp)
194 register FILE *fp;
195 {
196 	register int k;
197 	register char c;
198 
199 	while (isspace(c = getc(fp)))
200 	    ;
201 	k = 0;
202 	if (c == '-') {
203 	    c = getc(fp);
204 	    do {
205 		k = 10 * k - (c - '0');
206 	    } while (isdigit(c = getc(fp)));
207 	} else {
208 	    do {
209 		k = 10 * k + c - '0';
210 	    } while (isdigit(c = getc(fp)));
211 	}
212 	ungetc(c, fp);
213 	return (k);
214 }
215 
216 
217 conv(fp)
218 register FILE *fp;
219 {
220 	register int c;
221 	int m, n, m1, n1;
222 
223 	while ((c = getc(fp)) != EOF) {
224 #ifdef DEBUGABLE
225 	    if (dbg > 2) fprintf(stderr, "conv: got:<%c>, op-obuf=%d V=%d\n", c, op-obuf, vpos);
226 #endif DEBUGABLE
227 	    if (op > obuf + obufsiz) {
228 		error(!FATAL, "buffer overflow %d.", op - (obuf + obufsiz));
229 		oflush();
230 	    }
231 	    switch (c) {
232 		case '\0':	/* filter out noise */
233 			break;
234 		case '\n':	/* let text input through */
235 		case '\t':
236 		case ' ':
237 			*op++ = c;
238 			break;
239 		case '{':	/* push down current environment */
240 			*op++ = c;
241 			t_push();
242 			break;
243 		case '}':	/* pop up last environment */
244 			*op++ = c;
245 			t_pop();
246 			break;
247 		case '0': case '1': case '2': case '3': case '4':
248 		case '5': case '6': case '7': case '8': case '9':
249 				/* two motion digits plus a character */
250 			setlimit(vpos - up, vpos + down);
251 			/*
252 			*op++ = c;
253 			hmot((c-'0') * 10 + (*op++ = getc(fp)) - '0');
254 			*op++ = getc(fp);
255 			 */
256 			n = ((c - '0') * 10 + ( m = getc(fp)) - '0');
257 			hmot(n);
258 			sprintf(op, "%02d", n);
259 			op += strlen(op);
260 			*op++ = getc(fp);
261 			break;
262 		case 'c':	/* single ascii character */
263 			setlimit(vpos - up, vpos + down);
264 			*op++ = c;
265 			*op++ = getc(fp);
266 			break;
267 		case 'C':	/* white-space terminated funny character */
268 			setlimit(vpos - up, vpos + down);
269 			*op++ = c;
270 			do
271 			    *op++ = c = getc(fp);
272 			while (c != EOF && !isspace(c));
273 			break;
274 		case 't':	/* straight text */
275 			setlimit(vpos - up, vpos + down);
276 			*op++ = c;
277 			fgets(op, SLOP, fp);
278 			op += strlen(op);
279 			break;
280 		case 'D':	/* draw function */
281 			switch (c = getc(fp)) {
282 				int skip;
283 #ifdef BERK
284 			case 's':	/* "style" */
285 				sprintf(op, "Ds ");
286 				op += 3;
287 				style = getnumber(fp);
288 				break;
289 
290 			case 't':	/* thickness */
291 				sprintf(op, "Dt ");
292 				op += 3;
293 				thick = getnumber(fp);
294 				break;
295 #endif BERK
296 
297 			case 'l':	/* draw a line */
298 				n1 = ngetnumber(fp);
299 				m1 = ngetnumber(fp);
300 				n = n1;
301 				m = m1;
302 				if (m < 0) {
303 				    setlimit(vpos+m-thick/2, vpos+thick/2);
304 				} else {
305 				    setlimit(vpos-(1+thick/2),vpos+1+m+thick/2);
306 				}
307 				sprintf(op, "Dl %d %d", n, m);
308 				op += strlen(op);
309 				hmot(n1);
310 				vmot(m1);
311 #ifndef BERK
312 				/*
313 				 * note that this function is actually
314 				 * Dl n m .
315 				 * so we have to skip over the ".".
316 				 *
317 				 * Rhetoric question: Why doensn't Berkeley
318 				 * maintain compatability?
319 				 */
320 				do{
321 					skip = getc(fp);
322 					if( skip == EOF)
323 						error(FATAL,
324 						 "Cannot find . in Dl\n");
325 				}while( skip != '.');
326 #endif BERK
327 				break;
328 
329 			case 'e':	/* ellipse */
330 				n = ngetnumber(fp);
331 				m = ngetnumber(fp);
332 				setlimit(vpos-(m+thick)/2, vpos+(m+thick)/2);
333 				sprintf(op, "De %d %d", n, m);
334 				op += strlen(op);
335 				hmot(n);
336 				break;
337 
338 			case 'c':	/* circle */
339 				n = ngetnumber(fp);
340 				setlimit(vpos-(n+thick)/2, vpos+(n+thick)/2);
341 				sprintf(op, "Dc %d", n);
342 				op += strlen(op);
343 				hmot(n);
344 				break;
345 
346 			case 'a':	/* arc */
347 #ifdef BERK
348 				n = getnumber(fp);
349 				m = getnumber(fp);
350 				n1 = getnumber(fp);
351 				m1 = getnumber(fp);
352 #else
353 				n = ngetnumber(fp);
354 				m = ngetnumber(fp);
355 				n1 = ngetnumber(fp);
356 				m1 = ngetnumber(fp);
357 #endif BERK
358 				arcbounds(n, m, n1, m1);
359 				sprintf(op, "Da %d %d %d %d", n, m, n1, m1);
360 				op += strlen(op);
361 				hmot(n + n1);
362 				vmot(m + m1);
363 				break;
364 
365 #ifdef BERK
366 			case 'P':
367 			case 'p':
368 			    {
369 				register int nvect;
370 				int member;
371 				int border;
372 				int x[MAXVECT];
373 				int y[MAXVECT];
374 
375 
376 				border = (c == 'p');	/* type of polygon */
377 				member = ngetnumber(fp);/* and member number */
378 
379 				nvect = 1;		/* starting point for */
380 				x[1] = hpos;		/* points on polygon */
381 				y[1] = vpos;
382 				m = n = vpos;		/* = max/min vertical */
383 							/* position for curve */
384 				{
385 				    register int h;
386 				    register int v;
387 
388 
389 				    h = hpos;	/* calculate max and minimum */
390 				    v = vpos;		/* vertical position */
391 							/*    and get points */
392 				    do {
393 					h += ngetnumber(fp);
394 					v += ngetnumber(fp);
395 
396 					if (v < n) n = v;
397 					else if (v > m) m = v;
398 
399 					if (nvect < (MAXVECT-1))/* keep the */
400 					    nvect++;		/* points in */
401 					x[nvect] = h;		/* bounds */
402 					y[nvect] = v;		/* of arrays */
403 					c = getc(fp);
404 				    } while (c != '\n' && c != EOF);
405 				}
406 				if (border) {		/* output border as a */
407 				    register int *x1;	/*  bunch of lines */
408 				    register int *x2;	/*  instead of having */
409 				    register int *y1;	/*  the filter do it */
410 				    register int *y2;
411 				    register int extra = thick/2;
412 
413 				    x1 = &(x[0]);	/* x1, y1, x2, y2 are */
414 				    x2 = &(x[1]);	/* for indexing along */
415 				    y1 = &(y[0]);	/* coordinate arrays */
416 				    y2 = &(y[1]);
417 				    for (border = 0; ++border < nvect; ) {
418 					if (*++y1 > *++y2) {
419 					   setlimit(*y2-extra, vpos+extra);
420 					} else {
421 					   setlimit(vpos-(1+extra),*y2+1+extra);
422 						/* the extra 1's are to force */
423 						/* setlimit to know this is a */
424 						/* real entry (making sure it */
425 						/* doesn't get vpos as limit */
426 					}
427 					sprintf(op, "Dl %d %d\n",
428 						c = *++x2 - *++x1, *y2 - *y1);
429 					op += strlen(op);
430 					hmot(c);	/* update vpos for */
431 					vgoto(*y2);	/* the setlimit call */
432 				    }
433 				} else {
434 				    register int *x1;	/* x1, x2, are for */
435 				    register int *x2;	/* indexing points */
436 				    register int i;	/* random int */
437 
438 				    x1 = &(x[0]);
439 				    x2 = &(x[1]);
440 				    for (i = 0; ++i < nvect; ) {
441 					hmot(*++x2 - *++x1);
442 				    }
443 				    vgoto(y[nvect]);
444 				    sprintf(op, "H%dV%d", hpos, vpos);
445 				    op += strlen(op);
446 				}
447 				if (member) {
448 				    polygon(member, nvect, x, y, m, n);
449 				}
450 			    }
451 			    break;
452 #endif BERK
453 
454 			case '~':	/* wiggly line */
455 #ifdef BERK
456 			case 'g':	/* gremlin curve */
457 #endif BERK
458 			    startspan(vpos);		/* always put curve */
459 			    sprintf(op, "D%c ", c);	/* on its own span */
460 			    op += 3;
461 
462 			    m = n = vpos;		/* = max/min vertical */
463 			    do {			/* position for curve */
464 				/*
465 				hpos += getnumber(fp);
466 				*op++ = ' ';
467 				vpos += getnumber(fp);
468 				*op++ = ' ';
469 				 */
470 				n1 = ngetnumber(fp);
471 				m1 = ngetnumber(fp);
472 
473 				hmot(n1);
474 				vmot(m1);
475 				sprintf(op, "%d %d ", n1, m1);
476 				op += strlen(op);
477 
478 				if (vpos < n) n = vpos;
479 				else if (vpos > m) m = vpos;
480 				c = getc(fp);
481 			    } while (c != '\n' && c != EOF);
482 
483 			    vlp->u = n < 0 ? 0 : n;
484 			    vlp->d = m;
485 			    *op++ = '\n';
486 			    startspan(vpos);
487 			    break;
488 
489 			default:
490 				error(FATAL,"unknown drawing command %c", c);
491 				break;
492 			}
493 			break;
494 		case 's':
495 			*op++ = c;
496 			size = getnumber(fp);
497 			up = ((size + 1)*inch) / POINT;	/* ROUGH estimate */
498 			down = up / 3;			/* of max up/down */
499 			break;
500 		case 'f':
501 			*op++ = c;
502 			font = getnumber(fp);
503 			break;
504 #ifdef BERK
505 		case 'i':
506 			*op++ = c;
507 			stip = getnumber(fp);
508 			break;
509 #endif BERK
510 		case 'H':	/* absolute horizontal motion */
511 			hgoto(ngetnumber(fp));
512 			sprintf(op, "H%d", hpos);
513 			op += strlen(op);	/* reposition by page offset */
514 			break;
515 		case 'h':	/* relative horizontal motion */
516 			/*
517 			*op++ = c;
518 			hmot(getnumber(fp));
519 			 */
520 			n = ngetnumber(fp);
521 			hmot(n);
522 			sprintf(op, "h%d", n);
523 			op += strlen(op);
524 			break;
525 		case 'w':	/* useless */
526 			*op++ = c;	/* But put it out anyway */
527 			break;
528 		case 'V':	/* absolute vertical motion */
529 			/*
530 			*op++ = c;
531 			vgoto(getnumber(fp));
532 			 */
533 			vgoto(ngetnumber(fp));
534 			sprintf(op, "V%d", vpos);
535 			op += strlen(op);
536 			break;
537 		case 'v':
538 			/*
539 			*op++ = c;
540 			vmot(getnumber(fp));
541 			 */
542 			n = ngetnumber(fp);
543 			vmot(n);
544 			sprintf(op, "v%d", n);
545 			op += strlen(op);
546 			break;
547 		case 'p':	/* new page */
548 			t_page(ngetnumber(fp));
549 			vpos = 0;
550 #ifndef BERK
551 			if(!started)
552 				started++;
553 #endif BERK
554 			break;
555 		case 'n':	/* end of line */
556 			hpos = leftmarg;
557 			/*
558 			*op++ = c;
559 			do
560 			    *op++ = c = getc(fp);
561 			while (c != '\n' && c != EOF);
562 			 */
563 			*op++ = c;
564 			n = ngetnumber(fp);
565 			m = ngetnumber(fp);
566 			sprintf(op, "%d %d", n, m);
567 			op += strlen(op);
568 			break;
569 		case '#':	/* comment */
570 			do
571 			    c = getc(fp);
572 			while (c != '\n' && c != EOF);
573 			break;
574 		case 'x':	/* device control */
575 			devcntrl(fp);
576 			break;
577 		default:
578 			error(!FATAL, "unknown input character %o %c", c, c);
579 			done();
580 	    }
581 	}
582 }
583 
584 devcntrl(fp)	/* interpret device control functions */
585 FILE *fp;		/* returns -1 apon recieving "stop" command */
586 {
587         char str[20], str1[50], buf[50];
588 	char *p;
589 	int c, n, t1, t2;
590 
591 	fscanf(fp, "%s", str);
592 	switch (str[0]) {	/* crude for now */
593 	case 'r':	/* resolution assumed when prepared */
594 		/*
595 		fscanf(fp, "%d", &inRES);
596 		if (n!=RES) error(FATAL,"Input computed for wrong printer");
597 		 */
598 		fscanf(fp, "%d %d %d", &inch, &t1, &t2);
599 		sprintf(str1, "x res %d %d %d", inch, t1, t2);
600 		break;
601 	default:	/* reconstruct the string */
602 		fgets(buf, sizeof buf, fp);
603 		sprintf(str1, "x %s%s", str, buf);
604 	}
605 
606 	startspan(vpos);
607 	/*
608 	*op++ = c;
609 	do
610 	    *op++ = c = getc(fp);
611 	while (c != '\n' && c != EOF);
612 	 */
613 	p = str1;
614 	while (*p)
615 		*op++ = *p++;
616 }
617 
618 /*----------------------------------------------------------------------------*
619  | Routine:	setlimit
620  |
621  | Results:	using "newup" and "newdown" decide when to start a new span.
622  |		maximum rise and/or fall of a vertical extent are saved.
623  |
624  | Side Efct:	may start new span.
625  *----------------------------------------------------------------------------*/
626 
627 #define diffspan(x,y)	((x)/NLINES != (y)/NLINES)
628 
629 setlimit(newup, newdown)
630 register int newup;
631 register int newdown;
632 {
633 	register int currup = vlp->u;
634 	register int currdown = vlp->d;
635 
636 	if (newup < 0) newup = 0;	/* don't go back beyond start of page */
637 	if (newdown < 0) newdown = 0;
638 
639 	if (diffspan(currup, currdown)) {	/* now spans > one band */
640 	    if (diffspan(newup, currup) || diffspan(newdown, currdown)) {
641 		startspan (vpos);
642 		vlp->u = newup;
643 		vlp->d = newdown;
644 	    } else {
645 		if (newup < currup) vlp->u = newup;
646 		if (newdown > currdown) vlp->d = newdown;
647 	    }
648 	} else {
649 	    if (newup < currup) {	/* goes farther up than before */
650 		if (currup == vlp->v) {		/* is new span, just set "up" */
651 		    vlp->u = newup;
652 		} else {
653 		    if (diffspan(newup, currup)) {	/* goes up farther */
654 			startspan(vpos);		/* than previously */
655 			vlp->u = newup;			/* AND to a higher */
656 			vlp->d = newdown;		/* band.  */
657 			return;
658 		    } else {
659 			vlp->u = newup;
660 		    }
661 		}
662 	    }
663 	    if (newdown > currdown) {
664 		if (currdown == vlp->v) {
665 		    vlp->d = newdown;
666 		    return;
667 		} else {
668 		    if (diffspan(newdown, currdown)) {
669 			startspan(vpos);
670 			vlp->u = newup;
671 			vlp->d = newdown;
672 			return;
673 		    } else {
674 			vlp->d = newdown;
675 		    }
676 		}
677 	    }
678 	}
679 }
680 
681 
682 /*----------------------------------------------------------------------------*
683  | Routine:	arcbounds (h, v, h1, v1)
684  |
685  | Results:	using the horizontal positions of the starting and ending
686  |		points relative to the center and vertically relative to
687  |		each other, arcbounds calculates the upper and lower extent
688  |		of the arc which is one of:  starting point, ending point
689  |		or center + rad for bottom, and center - rad for top.
690  |
691  | Side Efct:	calls setlimit(up, down) to save the extent information.
692  *----------------------------------------------------------------------------*/
693 
694 arcbounds(h, v, h1, v1)
695 int h, v, h1, v1;
696 {
697 	register unsigned rad = (int)(sqrt((double)(h*h + v*v)) + 0.5);
698 	register int i = ((h >= 0) << 2) | ((h1 < 0) << 1) | ((v + v1) < 0);
699 
700 			/* i is a set of flags for the points being on the */
701 			/* left of the center point, and which is higher */
702 
703 	v1 += vpos + v;		/* v1 is vertical position of ending point */
704 				/* test relative positions for maximums */
705 	setlimit(		/* and set the up/down of the arc */
706 	    ((((i&3)==1) ? v1 : (((i&5)==4) ? vpos : vpos+v-rad)) - thick/2),
707 	    ((((i&3)==2) ? v1 : (((i&5)==1) ? vpos : vpos+v+rad)) + thick/2));
708 }
709 
710 
711 oflush()	/* sort, then dump out contents of obuf */
712 {
713 	register struct vlist *vp;
714 	register int notdone;
715 	register int topv;
716 	register int botv;
717 	register int i;
718 	register char *p;
719 
720 #ifdef DEBUGABLE
721 	if (dbg) fprintf(stderr, "GAG me with an into oflush, V=%d\n", vpos);
722 #endif DEBUGABLE
723 	if (op == obuf)
724 		return;
725 	*op = 0;
726 
727 	topv = 0;
728 	botv = NLINES - 1;
729 	do {
730 	    notdone = 0;
731 	    vp = vlist;
732 	    for (i = 0; i < nvlist; i++, vp++) {
733 #ifdef DEBUGABLE
734 		if(dbg>1)fprintf(stderr,"oflush: u=%d, d=%d,%.60s\n",vp->u,vp->d,vp->p);
735 #endif DEBUGABLE
736 		if (vp->u <= botv && vp->d >= topv) {
737 #ifdef BERK
738 		    printf("H%dV%ds%df%d\ni%d\nDs%d\nDt%d\n%s",
739 			 vp->h,vp->v,vp->s,vp->f,vp->l,vp->st,vp->t,vp->p);
740 #else
741 		if(started)
742 		    printf("H%dV%ds%df%d\n%s", vp->h,vp->v,vp->s,vp->f,vp->p);
743 		else
744 		    /*
745 		     * only the real string to put out, else dver
746 		     * complains since it didn't got an "x init
747 		     * command", so it doen't know about any font yet
748 		     */
749 		    printf("%s", vp->p);
750 #endif BERK
751 		}
752 		notdone |= vp->d > botv;	/* not done if there's still */
753 	    }					/* something to put lower */
754 	    if (notdone) putchar('P');		/* mark the end of the spread */
755 	    topv += NLINES;			/* unless it's the last one */
756 	    botv += NLINES;
757 	} while (notdone);
758 
759 	fflush(stdout);
760 	vlp = vlist;
761 	vlp->p = op = obuf;
762 	vlp->h = hpos;
763 	vlp->v = vpos;
764 	vlp->u = vpos;
765 	vlp->d = vpos;
766 	vlp->s = size;
767 	vlp->f = font;
768 #ifdef BERK
769 	vlp->l = stip;
770 	vlp->st = style;
771 #endif BERK
772 	vlp->t = thick;
773 	*op = 0;
774 	nvlist = 1;
775 }
776 
777 
778 done()
779 {
780 	oflush();
781 	exit(0);
782 }
783 
784 error(f, s, a1, a2, a3, a4, a5, a6, a7) {
785 	fprintf(stderr, "vsort: ");
786 	fprintf(stderr, s, a1, a2, a3, a4, a5, a6, a7);
787 	fprintf(stderr, "\n");
788 	if (f)
789 		done();
790 }
791 
792 #define	MAXSTATE	5
793 
794 struct state {
795 	int	ssize;
796 	int	sfont;
797 	int	shpos;
798 	int	svpos;
799 };
800 struct	state	state[MAXSTATE];
801 struct	state	*statep = state;
802 
803 t_push()	/* begin a new block */
804 {
805 	statep->ssize = size;
806 	statep->sfont = font;
807 	statep->shpos = hpos;
808 	statep->svpos = vpos;
809 	hpos = vpos = 0;
810 	if (statep++ >= state+MAXSTATE)
811 		error(FATAL, "{ nested too deep");
812 	hpos = vpos = 0;
813 }
814 
815 t_pop()	/* pop to previous state */
816 {
817 	if (--statep < state)
818 		error(FATAL, "extra }");
819 	size = statep->ssize;
820 	font = statep->sfont;
821 	hpos = statep->shpos;
822 	vpos = statep->svpos;
823 }
824 
825 
826 /*----------------------------------------------------------------------------*
827  | Routine:	t_page
828  |
829  | Results:	new Margins are calculated for putting pages side-by-side.
830  |		If no more pages can fit across the paper (WIDTH wide)
831  |		a real page end is done and the currrent page is output.
832  |
833  | Side Efct:	oflush is called on a REAL page boundary.
834  *----------------------------------------------------------------------------*/
835 
836 t_page(n)
837 int n;
838 {
839 #ifndef VER80
840     static int first = 1;		/* flag to catch the 1st time through */
841 
842     				/* if we're near the edge, we'll go over on */
843     if (leftmarg + 2*(pageno ? leftmarg/pageno : 0) > WIDTH	/* this page, */
844 	  || maxh > WIDTH - inch || first) {	/* or this is the first page */
845 	oflush();
846 	printf("p%d\n", spanno++);		/* make it a REAL page-break */
847 	first = pageno = leftmarg = maxh = 0;
848     } else {			    /* x = last page's width (in half-inches) */
849 	register int x = (maxh - leftmarg + (HALF - 1)) / HALF;
850 
851 	if (x > 11 && x <= 17)
852 	    leftmarg += (8 * inch) + HALF; 		/* if close to 8.5"  */
853 	else						/* then make it so   */
854 	    leftmarg = ((maxh + HALF) / HALF) * HALF;	/* else set it to the */
855 	pageno++;					/* nearest half-inch */
856     }
857 #else
858     oflush();
859 /*
860  *  printf("P");
861  */
862     printf("p%d\n", n);
863     pageno = leftmarg = maxh = 0;
864 #endif VER80
865 }
866 
867 
868 startspan(n)
869 register int n;
870 {
871 	*op++ = 0;
872 	if (nvlist >= NVLIST) {
873 #ifdef DEBUGABLE
874 	    error(!FATAL, "(startspan) ran out of vlist");
875 #endif DEBUGABLE
876 	    oflush();
877 	}
878 	vlp++;
879 	vlp->p = op;
880 	vlp->v = n;
881 	vlp->d = n;
882 	vlp->u = n;
883 	vlp->h = hpos;
884 	vlp->s = size;
885 	vlp->f = font;
886 #ifdef BERK
887 	vlp->l = stip;
888 	vlp->st = style;
889 #endif BERK
890 	vlp->t = thick;
891 	nvlist++;
892 }
893 
894 #ifdef BERK
895 
896 #define MAXX	0x7fff
897 #define MINX	0x8000
898 
899 typedef struct poly {
900 	struct poly *next;	/* doublely-linked lists of vectors */
901 	struct poly *prev;
902 	int param;	/* bressenham line algorithm parameter */
903 	short dx;	/* delta-x for calculating line */
904 	short dy;	/* delta-y for calculating line */
905 	short currx;	/* current x in this vector */
906 	short endy;	/* where vector ends */
907 } polyvector;
908 
909 
910 /*----------------------------------------------------------------------------*
911  | Routine:	polygon ( member, num_vectors, x_coor, y_coor, maxy, miny )
912  |
913  | Results:	outputs commands to draw a polygon starting at (x[1], y[1])
914  |		going through each of (x_coordinates, y_coordinates), and
915  |		filled with "member" stipple pattern.
916  |
917  |		A scan-line algorithm is simulated and pieces of the
918  |		polygon are put out that fit on bands of the versatec
919  |		output filter.
920  |
921  |		The format of the polygons put out are:
922  |			'Dp member num miny maxy [p dx dy curx endy]'
923  |		where "num" is the number of [..] entries in that
924  |		section of the polygon.
925  *----------------------------------------------------------------------------*/
926 
927 polygon(member, nvect, x, y, maxy, miny)
928 int member;
929 int nvect;
930 int x[];
931 int y[];
932 int maxy;
933 int miny;
934 {
935     int nexty;			/* at what x value the next vector starts */
936     register int active;	/* number of vectors in active list */
937     int firsttime;		/* force out a polgon the first time through */
938     polyvector *activehead;		/* doing fill, is active edge list */
939     polyvector *waitinghead;		/* edges waiting to be active */
940     register polyvector *vectptr;	/* random vector */
941     register int i;			/* random register */
942 
943 
944 				/* allocate space for raster-fill algorithm*/
945     vectptr = (polyvector *) malloc(sizeof(polyvector) * (nvect + 4));
946     if (vectptr == (polyvector *) NULL) {
947 	error(!FATAL, "unable to allocate space for polygon");
948 	return;
949     }
950 
951     waitinghead = vectptr;
952     vectptr->param = miny - 1;
953     (vectptr++)->prev = NULL;		/* put dummy entry at start */
954     waitinghead->next = vectptr;
955     vectptr->prev = waitinghead;
956     i = 1;					/* starting point of coords */
957     if (y[1] != y[nvect] || x[1] != x[nvect]) {
958 	y[0] = y[nvect];			/* close polygon if it's not */
959 	x[0] = x[nvect];
960 	i = 0;
961     }
962     active = 0;
963     while (i < nvect) {		/* set up the vectors */
964 	register int j;			/* indexes to work off of */
965 	register int k;
966 
967 	j = i;			/* j "points" to the higher (lesser) point */
968 	k = ++i;
969 	if (y[j] == y[k])		/* ignore horizontal lines */
970 	    continue;
971 
972 	if (y[j] > y[k]) {
973 	    j++;
974 	    k--;
975 	}
976 	active++;
977 	vectptr->next = vectptr + 1;
978 	vectptr->param = y[j];		/* starting point of vector */
979 	vectptr->dx = x[k] - x[j];	/* line-calculating parameters */
980 	vectptr->dy = y[k] - y[j];
981 	vectptr->currx = x[j];		/* starting point */
982 	(vectptr++)->endy = y[k];	/* ending point */
983 	vectptr->prev = vectptr - 1;
984     }
985 					/* if no useable vectors, quit */
986     if (active < 2)
987 	goto leavepoly;
988 
989     vectptr->param = maxy + 1;		/* dummy entry at end, too */
990     vectptr->next = NULL;
991 
992     activehead = ++vectptr;		/* two dummy entries for active list */
993     vectptr->currx = MINX;		/* head */
994     vectptr->endy = maxy + 1;
995     vectptr->param = vectptr->dx = vectptr->dy = 0;
996     activehead->next = ++vectptr;
997     activehead->prev = vectptr;
998     vectptr->prev = activehead;		/* tail */
999     vectptr->next = activehead;
1000     vectptr->currx = MAXX;
1001     vectptr->endy = maxy + 1;
1002     vectptr->param = vectptr->dx = vectptr->dy = 0;
1003 
1004 					/* if there's no need to break the */
1005 					/* polygon into pieces, don't bother */
1006     if (diffspan(miny, maxy)) {
1007 	active = 0;			/* will keep track of # of vectors */
1008 	firsttime = 1;
1009     } else {				/*   in the active list */
1010 	startspan(miny);
1011 	sprintf(op, "Dq %d %d %d %d", member, active, miny, maxy);
1012 	op += strlen(op);
1013 	for (vectptr = waitinghead->next; active--; vectptr++) {
1014 	    sprintf(op, " %d %d %d %d %d",
1015 		vectptr->param, vectptr->dx, vectptr->dy,
1016 		vectptr->currx, vectptr->endy);
1017 	    op += strlen(op);
1018 	}
1019 	*(op++) = '\n';
1020 	goto leavepoly;
1021     }
1022 			/* main loop -- gets vectors off the waiting list, */
1023 			/* then displays spans while updating the vectors in */
1024     			/* the active list */
1025     while (miny <= maxy) {
1026 	i = maxy + 1;		/* this is the NEXT time to get a new vector */
1027 	for (vectptr = waitinghead->next; vectptr != NULL; ) {
1028 	    if (miny == vectptr->param) {
1029 				/* the entry in waiting list (vectptr) is */
1030 				/*   ready to go into active list.  Need to */
1031 				/*   convert some vector stuff and sort the */
1032 				/*   entry into the list. */
1033 		register polyvector *p;	/* random vector pointers */
1034 		register polyvector *v;
1035 
1036 							/* convert this */
1037 		if (vectptr->dx < 0)			/* entry to active */
1038 		    vectptr->param = -((vectptr->dx >> 1) + (vectptr->dy >> 1));
1039 		else
1040 		    vectptr->param = (vectptr->dx >> 1) - (vectptr->dy >> 1);
1041 
1042 		p = vectptr;			/* remove from the */
1043 		vectptr = vectptr->next;	/* waiting list */
1044 		vectptr->prev = p->prev;
1045 		p->prev->next = vectptr;
1046 						/* find where it goes */
1047 						/* in the active list */
1048 						/* (sorted smallest first) */
1049 		for (v = activehead->next; v->currx < p->currx; v = v->next)
1050 		    ;
1051 		p->next = v;		/* insert into active list */
1052 		p->prev = v->prev;	/* before the one it stopped on */
1053 		v->prev = p;
1054 		p->prev->next = p;
1055 		active++;
1056 	    } else {
1057 		if (i > vectptr->param) {
1058 		    i = vectptr->param;
1059 		}
1060 		vectptr = vectptr->next;
1061 	    }
1062 	}
1063 	nexty = i;
1064 
1065 					/* print the polygon while there */
1066 					/* are no more vectors to add */
1067 	while (miny < nexty) {
1068 					/* remove any finished vectors */
1069 	    vectptr = activehead->next;
1070 	    do {
1071 		if (vectptr->endy <= miny) {
1072 		    vectptr->prev->next = vectptr->next;
1073 		    vectptr->next->prev = vectptr->prev;
1074 		    active--;
1075 		}
1076 	    } while ((vectptr = vectptr->next) != activehead);
1077 
1078 					/* output a polygon for this band */
1079 	    if (firsttime || !(miny % NLINES)) {
1080 		register int numwait;	/* number in the waiting list */
1081 		register int newmaxy;	/* max for this band (bottom or maxy)*/
1082 
1083 
1084 		startspan(miny);
1085 		if ((newmaxy = (miny / NLINES) * NLINES + (NLINES - 1)) > maxy)
1086 		    newmaxy = maxy;
1087 
1088 					/* count up those vectors that WILL */
1089 					/* become active in this band */
1090 		for (numwait = 0, vectptr = waitinghead->next;
1091 				vectptr != NULL; vectptr = vectptr->next) {
1092 		    if (vectptr->param <= newmaxy)
1093 			numwait++;
1094 		}
1095 
1096 		sprintf(op,"Dq %d %d %d %d",member,active+numwait,miny,newmaxy);
1097 		op += strlen(op);
1098 		for (i = active, vectptr = activehead->next; i--;
1099 						vectptr = vectptr->next) {
1100 		    sprintf(op, " %d %d %d %d %d",
1101 			    vectptr->param, vectptr->dx, -vectptr->dy,
1102 			    vectptr->currx, vectptr->endy);
1103 		    op += strlen(op);
1104 		}
1105 		for (vectptr = waitinghead->next; vectptr != NULL;
1106 						vectptr = vectptr->next) {
1107 		    if (vectptr->param <= newmaxy) {
1108 			sprintf(op, " %d %d %d %d %d",
1109 				vectptr->param, vectptr->dx, vectptr->dy,
1110 				vectptr->currx, vectptr->endy);
1111 			op += strlen(op);
1112 		    }
1113 		}
1114 		*(op++) = '\n';
1115 		firsttime = 0;
1116 	    }
1117 
1118 					/* update the vectors */
1119 	    vectptr = activehead->next;
1120 	    do {
1121 		if (vectptr->dx > 0) {
1122 		    while (vectptr->param >= 0) {
1123 			vectptr->param -= vectptr->dy;
1124 			vectptr->currx++;
1125 		    }
1126 		    vectptr->param += vectptr->dx;
1127 		} else if (vectptr->dx < 0) {
1128 		    while (vectptr->param >= 0) {
1129 			vectptr->param -= vectptr->dy;
1130 			vectptr->currx--;
1131 		    }
1132 		    vectptr->param -= vectptr->dx;
1133 		}
1134 					/* must sort the vectors if updates */
1135 					/* caused them to cross */
1136 					/* also move to next vector here */
1137 		if (vectptr->currx < vectptr->prev->currx) {
1138 		    register polyvector *v;		/* vector to move */
1139 		    register polyvector *p;	/* vector to put it after */
1140 
1141 		    v = vectptr;
1142 		    p = v->prev;
1143 		    while (v->currx < p->currx)	/* find the */
1144 			p = p->prev;		/* right vector */
1145 
1146 		    vectptr = vectptr->next;	/* remove from spot */
1147 		    vectptr->prev = v->prev;
1148 		    v->prev->next = vectptr;
1149 
1150 		    v->prev = p;		/* put in new spot */
1151 		    v->next = p->next;
1152 		    p->next = v;
1153 		    v->next->prev = v;
1154 		} else {
1155 		    vectptr = vectptr->next;
1156 		}
1157 	    } while (vectptr != activehead);
1158 
1159 	    ++miny;
1160 	} /* while (miny < nexty) */
1161     } /* while (miny <= maxy) */
1162 
1163 leavepoly:
1164     startspan(vpos);	/* make sure stuff after polygon is at correct vpos */
1165     free(waitinghead);
1166 }  /* polygon function */
1167 #endif BERK
1168