@*Intro. This (hastily written) program computes a floorplan that corresponds to a given Baxter permutation. See exercises MPR--135 and 7.2.2.1--372 (as revised in the third and subsequent printings of {\sl The Art of Computer Programming}, Volume~4, Fascicle~5) for an introduction to the relevant concepts and terminology. The input permutation is supposed to satisfy special conditions. When $k$ is given, let's say that a number~$s$ less than~$k$ is small'' and a number~$l$ greater than~$k+1$ is large''. Then $$\displaylines{ \hskip3em\hbox{if k occurs after k+1, we don't have two consecutive elements sl between them;}\hfill(*)\cr \hskip3em\hbox{if k+1 occurs after k, we don't have two consecutive elements ls between them.}\hfill(**)\cr}$$ In other words, if $k+1$ occurs before $k$ in~$P$, any small elements between them must follow any large ones between them~$(*)$; otherwise any small elements between them must {\it precede\/} any large ones between them~$(**)$. A {\it Baxter permutation\/} is a permutation that satisfies $(*)$ and $(**)$. Let's call the given Baxter permutation $P=p_1p_2\ldots p_n$. We'll construct a floorplan whose rooms are the numbers $\{1,2,\ldots,n\}$. The diagonal order of those rooms will be simply $12\ldots n$; and their antidiagonal order will be $p_1p_2\ldots p_n$. Floorplans have an interesting four-way'' order, under which any two distinct rooms $j$ and $k$ are in exactly one of four relationships to each other: Either $j$ is left of $k$ (written $j\Rightarrow k$), or $j$ is above $k$ (written $j\Downarrow k$), or $j$ is right of $k$ (written $j\Leftarrow j$), or $j$ is below $k$ (written $j\Uparrow j$). The diagonal order is the linear order above or left''; the antidiagonal order is the linear order below or left''. Therefore we must have the following (nice) situation: \eqalign{ j\Rightarrow k&\iff\hbox{jk and j follows k in P};\cr j\Uparrow k&\iff\hbox{j>k and j precedes k in P}.\cr } Furthermore, $j$ precedes $k$ in $P$ if and only $q_jp_{k+1}$); and the number of vertical bounds is two more than the number of {\it ascents\/} (where $p_k #include @; void main(void) { register int i,j,k,l,m,n; @; @; @; @; } @ @= for (m=n=0;fscanf(stdin,"%d", &inx)==1;n++) { if (inx<=0 || inx>maxn) panic("element out of range",inx); if (inx>m) m=inx; p[n+1]=inx; } if (m>n) panic("too few elements",m-n); if (m>n) panic("too many elements",n-m); for (k=1;k<=n;k++) q[p[k]]=k; /* compute the inverse */ for (k=1;k<=n;k++) if (q[k]==0) panic("missing element",k); @ @= int inx; /* data input with |fscanf| */ int p[maxn+1],q[maxn+1]; @ The following test might take quadratic time, because I tried to make it as simple as possible. But if you want to test the Baxter property in linear time, there's a tricky way to do it: (1)~Omit this test. (2)~Pipe the output of this program to {\mc FLOORPLAN-TO-TWINTREE-TTFORM}; the rooms will be in an order that makes that program efficient. (3)~Pipe the output of {\it that\/} program to {\mc TWINTREE-TO-BAXTER}. (4)~Compare that result to~$P$. If$P$is Baxter, you'll get it back again. Even better is to use the efficient method of a much simpler program, {\mc OFFLINE-TREE-INSERTION}, to make the twin tree directly from the given permutation; then do steps (3) and~(4). [An almost equivalent method was in fact published by Johnson M. Hart, {\sl International Journal of Computer and Information Sciences\/ \bf9} (1980), 307--321, and it's instructive to compare the two approaches.] @= for (k=2;kk && p[l+1]k) panic("not Baxter *",k); } } @*The key algorithm. We get to use a particularly nice method here, thanks to the insights of Eyal Ackerman, Gill Barequet, and Ron Y. Pinter [{\sl Discrete Applied Mathematics\/ \bf154} (2006), 1674--1684]. The four bounds |lft|, |bot|, |rt|, and |top| of each room can be filled in systemically as we march through~$P\$, taking linear time because we spend only a small bounded number of steps between the times when we make a contribution to the final plan. The algorithm maintains two stacks, |RLmin| and |RLmax|, which record the current right-to-left minima and maxima in the permutation read so far. The rooms on |RLmin| are precisely those for which |lft| and |bot| have been filled, but not yet |top|. The rooms on |RLmax| are precisely those for which |lft| and |bot| have been filled, but not yet |rt|. Values in the |bot| and |top| arrays are indices of horizontal bounds; values in the |lft| and |rt| arrays are indices of vertical bounds. At the end, we needn't fill in the missing values of |rt| and |top|, because they are zero (and that's what we want). This algorithm is almost too good to be true! It's valid, however, because it can be seen to create the antidiagonal floorplan, step by step. @= minptr=maxptr=1,RLmin[0]=RLmax[0]=j=p[1],lft[j]=bot[j]=n; for (k=1;k@; else @; } @ @= { lft[j]=rt[i]=n-k,maxptr--,RLmin[minptr++]=j; while (maxptr && RLmax[maxptr-1]= { bot[j]=top[i]=n-k,minptr--,RLmax[maxptr++]=j; while (minptr && RLmin[minptr-1]>j) top[RLmin[--minptr]]=n-k; lft[j]=(minptr? rt[RLmin[minptr-1]]: n); RLmin[minptr++]=j; } @ @= int lft[maxn+1],bot[maxn+1],rt[maxn+1],top[maxn+1]; int RLmin[maxn],RLmax[maxn]; /* the stacks */ int minptr,maxptr; /* the current stack sizes */ @ @= for (k=1;k<=n;k++) printf("%d h%d h%d v%d v%d\n", k,top[k],bot[k],lft[k],rt[k]); @*Index.