#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAXSIZ (50)
#define T_TR (-2)
#define T_THD (-3)
#define CRITICAL (8)
#undef DBG

enum {CEN_CENTER,CEN_LEFT,CEN_RIGHT};

int hsiz[MAXSIZ],vsiz[MAXSIZ],procspan[MAXSIZ];
struct cell {
	char *txt;
	char halign;
	char valign;
	char spanned;
	int hspan,vspan,lines,curpos,prelin;
	} arr[MAXSIZ][MAXSIZ];
char buf[200];
char cell[10000];
int halign,valign,halign1,valign1,row=-1,clm,maxrow=0,maxclm=0;
int hspan,vspan,hspan1,vspan1;
int dhalign=CEN_LEFT,dvalign=CEN_LEFT;
int cellptr,lastspace=1;

FILE *fi,*fo;

int token(void)
{
int c,i,n,was;
char flag;
	c=fgetc(fi);
	if (c==-1) return-1;
	if (c=='\n') return(' ');
	if (c=='&') {
			i=0;
			while (1) {
				c=fgetc(fi);
				if (c==';') break;
				if (c==-1); exit(1);
				buf[i++]=c;
				}
			buf[i]=0;
			if (!stricmp(buf,"lt"))
				return('<');
			if (!stricmp(buf,"gt"))
				return('>');
			if (!stricmp(buf,"amp"))
				return('&');
			}
	if (c!='<') return c;
	i=0;
	while (1) {
		c=fgetc(fi);
		if (c=='>') break;
		if (c==-1) exit(1);
		buf[i++]=c;
		}
	buf[i]=0;
	for (n=0;n<i;n++)
		buf[n]=toupper(buf[n]);
	valign1=valign;
	halign1=halign;
	hspan1=hspan;
	vspan1=vspan;
	hspan=vspan=1;
	was=T_THD;
	if (!strncmp(buf,"TR",2)) {
		was=T_TR;
		dhalign=dvalign=CEN_LEFT;
		}
	if (!strncmp(buf,"TH",2)) {
		halign=valign=CEN_CENTER;
		}
	if (!strncmp(buf,"TD",2)) {
		halign=dhalign;
		valign=dvalign;
		}
	i=2;
for (;;) {
	while (buf[i]==' ') i++;
	flag=buf[i];
	while (buf[i]&&buf[i]!='=') i++;
	if (!buf[i]) return(was);
	i++;
	if (!strncmp(&buf[i],"LEFT",4)) {
		i+=4;
		if (was==T_TR) dhalign=CEN_LEFT;
		else halign=CEN_LEFT;
		}
	else if (!strncmp(&buf[i],"RIGHT",5)) {
		i+=5;
		if (was==T_TR) dhalign=CEN_RIGHT;
		else halign=CEN_RIGHT;
		}
	else if (!strncmp(&buf[i],"CENTER",6)) {
		i+=6;
		if (was==T_TR) dhalign=CEN_CENTER;
		else halign=CEN_CENTER;
		}
	else if (!strncmp(&buf[i],"TOP",3)) {
		i+=3;
		if (was==T_TR) dvalign=CEN_LEFT;
		else valign=CEN_LEFT;
		}
	else if (!strncmp(&buf[i],"BOTTOM",6)) {
		i+=6;
		if (was==T_TR) dvalign=CEN_RIGHT;
		else valign=CEN_RIGHT;
		}
	else if (!strncmp(&buf[i],"MIDDLE",6)) {
		i+=6;
		if (was==T_TR) dvalign=CEN_CENTER;
		else valign=CEN_CENTER;
		}
	else {
long mylong;
int start;
char save;
		start=i;
		while (isdigit(buf[i])) i++;
		save=buf[i]; buf[i]=0;
		mylong=atol(&buf[start]);
		buf[i]=save;
		if (flag=='R') vspan=mylong;
		if (flag=='C') hspan=mylong;
		}
	}
}

static void finish(void)
{
char *s;
int row1,clm1;
	if (clm==-1||row==-1) return;
	while (cellptr&&cell[cellptr-1]==' ') cellptr--;
/*	if (!cellptr) return;*/
	cell[cellptr]=0;
	while (arr[row][clm].spanned) clm++;
	s=malloc(cellptr+1);	if (!s) exit(1);
	strcpy(s,cell);
	arr[row][clm].txt=s;
	arr[row][clm].halign=halign1;
	arr[row][clm].valign=valign1;
	arr[row][clm].hspan=hspan1;
	arr[row][clm].vspan=vspan1;
	if (hsiz[clm]<cellptr) hsiz[clm]=cellptr;
	for (row1=row;row1<row+vspan1;row1++)
		for (clm1=clm;clm1<clm+hspan1;clm1++)
			if (row1!=row||clm1!=clm) {
				arr[row1][clm1].spanned=1;
				/*arr[row1][clm1].hspan=arr[row1][clm1].vspan=1*/;
				}
	if (maxclm<clm+hspan1-1) maxclm=clm+hspan1-1;
	if (maxrow<row+vspan1-1) maxrow=row+vspan1-1;
	vsiz[row]=1;
	cellptr=0; lastspace=1;
}

static void printclm(int row1,int clm)
{
int row,i,lspc,n,width=-3;
char c;
	if (procspan[clm]!=-1)
		row=procspan[clm];
	else {
		row=row1;
		procspan[clm]=row;
		}
	for (i=clm;i<=clm+arr[row][clm].hspan-1;i++)
		width+=hsiz[i]+3;

	if (arr[row][clm].prelin||arr[row][clm].txt[arr[row][clm].curpos]==0) {
		for (i=0;i<width;i++) fputc(' ',fo);
		if (arr[row][clm].prelin) arr[row][clm].prelin--;
		return;
		}
	i=0;
	for (;;) {
		c=arr[row][clm].txt[arr[row][clm].curpos++];
		if (c=='\n') {
			break;
			}
		if (c==0) {
			arr[row][clm].curpos--;
			break;
			}
		cell[i++]=c;
		}
	cell[i]=0;
/*	}
	else {
		row=row1;
		for (i=clm;i<=clm+arr[row][clm].hspan-1;i++)
			width+=hsiz[clm]+3;
		cell[i=0]=0;
		if (arr[row][clm].vspan>1)
			procspan[clm]=row;
		if (!arr[row][clm].spanned) if (arr[row][clm].txt) {
			if (arr[row][clm].prelin||arr[row][clm].txt[arr[row][clm].curpos]==0) {
				for (i=0;i<width;i++) fputc(' ',fo);
				if (arr[row][clm].prelin) arr[row][clm].prelin--;
				return;
				}
			strcpy(cell,arr[row][clm].txt);
			i=strlen(cell);

			}
		}*/
	if (arr[row][clm].halign==CEN_LEFT) lspc=0;
	else {
		lspc=width-i;
		if (arr[row][clm].halign==CEN_CENTER) lspc=(lspc+1)/2;
		}
	for (n=0;n<lspc;n++) fputc(' ',fo);
	fputs(cell,fo);
	lspc=width-i-lspc;
	for (n=0;n<lspc;n++) fputc(' ',fo);
}

int main(int argc,char **argv)
{
char *s;
int N=80,c,i,lspc;
int lastshrunk,maxhval,sum,maxhnum,spaceptr,rowcnt;
char nullbuf[5]="";
#ifdef DBG
	puts("***START");
#endif
	if (argc==4) {
		s=argv[1]+1;
		argv++;
		sscanf(s,"%d",&N);
		}
/*	for (row=0;row<MAXSIZ;row++)
	for (clm=0;clm<MAXSIZ;clm++)
		arr[row][clm].hspan=arr[row][clm].vspan=1;*/

	fi=fopen(argv[1],"rt");
	fo=fopen(argv[2],"wt");
	while ((c=token())!=-1) {
		switch (c) {
		case T_TR:
			finish();
			row++; clm=-1;
			break;
		case T_THD:
			finish();
			if (clm!=-1) clm+=arr[row][clm].hspan;
			else clm++;
			break;
		case 0: break;
		default:
			if (row==-1||clm==-1) break;
			if (c==' '&&lastspace) break;
			lastspace=(c==' ');
			cell[cellptr++]=c;
		}}
	finish();
	for (row=0;row<=maxrow;row++)
	for (clm=0;clm<=maxclm;clm++)
		if (!arr[row][clm].txt) arr[row][clm].txt=nullbuf;
	lastshrunk=-1;
	maxhval=-1;
	do {
		sum=1;
		for (clm=0;clm<=maxclm;clm++) {
			sum+=3+hsiz[clm];
			if (hsiz[clm]>maxhval) {
				maxhval=hsiz[clm];
				maxhnum=clm;
				}
			}
		if (sum>N) {
			lastshrunk=maxhnum;
			i=hsiz[maxhnum];
			hsiz[maxhnum]/=2;
			if (hsiz[maxhnum]<CRITICAL)
				hsiz[maxhnum]=CRITICAL;
			if (hsiz[maxhnum]==i) {
				printf("Table columns cannot be further shrunked!\n"
							 "Cannot complete request with required paper width.\n");
				exit(1);
				}
			}
		else if (sum<N)
			if (lastshrunk!=-1)
				hsiz[lastshrunk]+=N-sum;
		} while (lastshrunk!=-1&&sum!=N);

	for (row=0;row<=maxrow;row++)
		for (clm=0;clm<=maxclm;clm++) if (!arr[row][clm].spanned) {
			arr[row][clm].lines=1;
			sum=0;
			s=arr[row][clm].txt;
			spaceptr=-1;
			i=0;
			while (s[i]) {
				if (s[i]==' '||s[i]=='-') spaceptr=i;
				sum++;
				if (sum>hsiz[clm]) {
#ifdef DBG
					puts("BROKING");
#endif DBG
					if (spaceptr==-1) {
						printf("Cell cannot be broken to fit in:\n"
									 "row %d, column %d (width %d) at cell line %d!\n",
							row,clm,hsiz[clm],arr[row][clm].lines);
						exit(1);
						}
					if (s[spaceptr]==' ') s[spaceptr]='\n';
					else {
						s=arr[row][clm].txt=realloc(s,strlen(s)+2);
						memmove(&s[spaceptr+2],&s[spaceptr+1],strlen(s)-spaceptr-1);
						s[++spaceptr]='\n';
						}
					i=spaceptr;
					spaceptr=-1;
					arr[row][clm].lines++;
					sum=0;
					}
				i++;
				}
	sum=-1;
	for (i=row;i<=row+arr[row][clm].vspan-1;i++)
		sum+=vsiz[row]+1;
	if (sum<arr[row][clm].lines) {
		sum=arr[row][clm].lines-sum;
		if (!arr[row][clm].hspan) arr[row][clm].hspan=1;
		if (!arr[row][clm].vspan) arr[row][clm].vspan=1;
		while (sum) for (i=row;sum&&i<=row+arr[row][clm].vspan-1;i++) {
			vsiz[row]++;
			sum--;
			}
		}
	else if (sum>arr[row][clm].lines&&arr[row][clm].valign!=CEN_LEFT) {
		sum-=arr[row][clm].lines;
		if (arr[row][clm].valign==CEN_CENTER) sum/=2;
		arr[row][clm].prelin=sum;
		}
	}

	for (i=0;i<=maxclm;i++)
		procspan[i]=-1;

	for (row=0;row<=maxrow+1;row++) {
		fputc(row==0||row>maxrow?'+':'|',fo);
		for (clm=0;clm<=maxclm;clm++) {

			if (procspan[clm]==-1)
				for (i=0;i<hsiz[clm]+2;i++) fputc('-',fo);
			else { fputc(' ',fo); printclm(row,clm); fputc(' ',fo); }

			if (row==0||row>maxrow) {
				if (clm==maxclm) fputc('+',fo);
				else fputc('-',fo);
				}
			else if (clm==maxclm) fputc('|',fo);
			else fputc('+',fo);
			}
		fputc('\n',fo);

		if (row<=maxrow) {
			for (rowcnt=1;rowcnt<=vsiz[row];rowcnt++) {

		for (clm=0;clm<=maxclm;clm+=(arr[row][clm].hspan?arr[row][clm].hspan:1)) {
			fputc('|',fo); fputc(' ',fo);
			printclm(row,clm);
			fputc(' ',fo);
			}
		fputc('|',fo); fputc('\n',fo);

			}
			for (i=0;i<=maxclm;i++) if (procspan[i]!=-1) {
				if (!--arr[procspan[i]][i].vspan) procspan[i]=-1;
				}

			 }

		}
	fclose(fi);
	fclose(fo);
	return(0);
}