\datethis @*Intro. This program contains two implementations of the Koda--Ruskey algorithm for generating all ideals of a given forest poset [{\sl Journal of Algorithms\/ \bf15} (1993), 324--340]. The common goal of both implementations is, in essence, to generate all binary strings $b_0\ldots b_{n-1}$ in which certain bits are required to be less than or equal to specified bits that lie to their right. (For some values of $j$ there is a value of $k>j$ such that we don't allow $b_k$ to be 0 when $b_j=1$.) Moreover, each binary string should differ from its predecessor in exactly one bit position; the algorithm therefore defines a generalized reflected Gray code. The given forest is represented by $n$ pairs of nested parentheses. For example, \.{()()()()()} represents five independent bits, while \.{((((()))))} represents five bits with $b_0\le b_1\le b_2\le b_3\le b_4$. A more interesting example, \.{((())(()()))}, represents six bits subject to the conditions $b_0\le b_1$, $b_1\le b_5$, $b_2\le b_4$, $b_3\le b_4$, $b_4\le b_5$. Each pair of parentheses corresponds to a bit that must not exceed the bit of its enclosing pair, if any, and the pairs are ordered by the appearances of their right parentheses. The first implementation uses $n$ coroutines, which call each other in a hierarchical fashion. The second uses multilinked data structures in a loopless way, so that each generation step performs a bounded number of operations to obtain the next element. I couldn't resist writing this program, because both implementations turn out to be quite interesting and instructive. Indeed, I think it's a worthwhile challenge for people who study the science of computer programming to verify that these two implementations both define the same sequence of bitstrings. Even more challenging would be to derive the second implementation automatically'' from the first. @c #include @@; @@; @# int main(int argc, char *argv[]) { register int j,k,l; @; printf("Bitstrings generated from \"%s\":\n",argv[1]); @; printf("\nTrying again, looplessly:\n"); @; return 0; } @ In this step we parse the forest into an array of scopes'': |scope[j]| is the index of the smallest descendant of node~|j|, including node~|j| itself. @d abort(m,i) {@+fprintf(stderr,m,argv[i]);@+return -1;@+} @d stacksize 100 /* max levels in the forest */ @d forestsize 100 /* max nodes in the forest */ @= if (argc!=2 || argv[1][0]!='(') abort("Usage: %s \"nestedparens\"\n",0); for (j=k=l=0; argv[1][k]; k++) if (argv[1][k]=='(') { stack[l++]=j; if (l==stacksize) abort("Stack overflow --- \"%s\" is too deep for me!\n",1); }@+else if (argv[1][k]==')') { if (--l<0) abort("Extra right parenthesis in \"%s\"!\n",1); scope[j++]=stack[l]; if (j==forestsize) abort("Memory overflow --- \"%s\" is too big!\n",1); }@+else abort("The forest spec \"%s\" should contain only parentheses!\n",1); if (l) abort("Missing right parenthesis in \"%s\"!\n",1); nn=j; @ @= int stack[stacksize]; /* nodes preceding each open leftparen, while parsing */ int scope[forestsize]; /* table that exhibits each rightparen's influence */ int nn; /* the actual number of nodes in the forest */ @* The coroutine implementation. Our first implementation uses a system of $n$ cooperating programs, each of which represents a node in the forest. For convenience we will call the associated record a cnode.'' If |p| points to a cnode, |p->child| points to the cnode representing its rightmost child, and |p->sib| points to the cnode representing its nearest sibling on the left, in the given forest. Each cnode corresponds to a coroutine whose job is to generate all the ideals of the subforest it represents. Whenever the coroutine is invoked, it either changes one of the bits in its scope and returns |true|, or it changes nothing and returns |false|. Initially all the bits are~0; when it first returns |false|, it will have generated all legitimate bit patterns, ending with some nonzero pattern. Subsequently it will generate the patterns again in reverse order, ending with all 0s, after which it will return |false| a second time. Invoking it again and again will repeat the same process, going forwards and backwards, ad infinitum. Each coroutine has the same basic structure, which can be described as follows in an ad hoc extension of \CEE/ language: \vbox{\halign{#\hfil\cr \&{coroutine} |p()|\cr \quad|{|\cr \quad\quad|while(1) {|\cr \quad\quad\quad|p->bit=1;@+return true;|\cr \quad\quad\quad|while (p->child()) return true;|\cr \quad\quad\quad|return p->sib();|\cr \quad\quad\quad|while (p->child()) return true;|\cr \quad\quad\quad|p->bit=0;@+return true;|\cr \quad\quad\quad|return p->sib();|\cr \quad\quad|}|\cr \quad|}|\cr }} If either |p->child| or |p->sib| is |NULL|, the corresponding coroutine |NULL()| is assumed to simply return |false|. Suppose |p->child()| first returns |false| after it has been called |r| times; thus |p->child()| generates |r| different patterns, including the initial pattern of all~0s. Similarly, suppose that |p->sib()| generates |l| different patterns before first returning |false|. Then the coroutine |p()| itself will generate |l(r+1)| patterns in between the times when it returns |false|. The final bit pattern for |p| will be the final bit pattern for |p->sib|, together with either |p->bit=1| and the final bit pattern of |p->child| (if |l| is odd) or with |p->bit=0| and all 0s in |p->child| (if |l| is even). @= typedef enum{@!false,@!true} boolean; @# typedef struct cnode_struct { char bit; /* either 0 or 1; always 1 when a child's bit is set */ char state; /* the current place in this cnode's coroutine */ struct cnode_struct *child; /* rightmost child in the given forest */ struct cnode_struct *sib; /* nearest left sibling in the given forest */ struct cnode_struct *caller; /* which coroutine invoked this one */ } cnode; @ When coroutine |p| calls coroutine |q|, it sets |p->state| to an appropriate number and also sets |q->caller=p|. Then control passes to |q| at the place determined by |q->state|. When coroutine |q| wants to return a boolean value, it sets |coresult| to this value; then it passes control to |p=q->caller| at the place determined by |p->state|. This program simulates coroutine linkage with a big switch statement. Actually the notion of passing control'' really means that we simply assign a value to the variable |cur_cnode|. The value of |q->caller| for every cnode |q| is completely determined by the structure of the given forest, so we could set it once and for all during the initialization instead of setting it dynamically as done here. But what the heck. @d cocall(q,s) {@+cur_cnode->state=s; if (q) q->caller=cur_cnode, cur_cnode=q; else coresult=false; goto cogo;@+} @d bitchange(b,s) {@+cur_cnode->bit=b, coresult=true;@+ coreturn(s);@+} @d coreturn(s) {@+cur_cnode->state=s, cur_cnode=cur_cnode->caller; goto cogo;@+} @= cogo:@+ switch (cur_cnode->state) { @; default: abort("%s: Unknown state code (this can't happen)!\n",0); } @ In its initial state~0, a coroutine turns its bit on, returns~|true|, and enters state~1. @= case 0: bitchange(1,1); @ The purpose of state 1 is to run through all bit patterns of the current node's children, starting with all 0s and ending when they reach their final pattern. At that point we invoke the current node's nearest left sibling and enter state~3. An intermediate state~2 is defined for the purpose of examining the result after calling the child coroutine. The purpose of state 3 is simply to return to whoever called us, passing along the information in |coresult|, which tells whether any of our left siblings has changed one of its bits. Then we will continue in state 4. @= case 1: cocall(cur_cnode->child,2); case 2:@+ if (coresult) coreturn(1); cocall(cur_cnode->sib,3); case 3: coreturn(4); @ State 4 is rather like state 1, except that the child coroutine is now running through its bit patterns in reverse order. Finally it reduces them all to 0s, and returns |false| the next time we attempt to invoke it. At that point we reset the current bit, return |true|, and enter state~6. State 6 invokes the sibling coroutine, leading to state 7. And state 7 is like state 3, but it takes us back to state 0 instead of state 4. @= case 4: cocall(cur_cnode->child,5); case 5:@+ if (coresult) coreturn(4); bitchange(0,6); case 6: cocall(cur_cnode->sib,7); case 7: coreturn(0); @ Hey, the implementation is done already, except that we have to get it started and write the code that controls it at the outermost level. @= { register cnode *cur_cnode; @; @; } @ We allocate a special cnode to represent the external world outside of the given forest. @d root_cnode cnode_table[nn].child @= scope[nn]=0; for (k=0; k<=nn; k++) if (scope[k]scope[k]; j=scope[j]-1) cnode_table[j].sib=cnode_table+scope[j]-1; } cur_cnode=cnode_table+nn; goto upward_step; @ @= cnode cnode_table[forestsize+1]; /* the cnodes */ boolean coresult; /* value returned by a coroutine */ @ States 8 and greater are reserved for the external (outermost) level, which simply invokes the coroutine for the entire forest and prints out the results, until the bit patterns have been generated in both the forward and reverse directions. @= case 8:@+ if (coresult) { upward_step: @; cocall(root_cnode,8); } printf("... and now we generate them in reverse:\n"); goto downward_step; case 9:@+ if (coresult) { downward_step: @; cocall(root_cnode,9); } break; @ @= for (k=0;kleft| and |p->right| are the neighbors of |p| on the left and right. A special node |head| is provided to make the list circular; thus |head->right| and |head->left| are the leftmost and rightmost fringe nodes. A fringe node is said to be said to be either {\it active\/} or {\it passive}. Every node is active when it joins the fringe, but it becomes passive for at least a short time when its bit changes value; at such times the node is essentially shifting direction between going forward or backward, as in the coroutine implementation. (A passive node corresponds roughly to a coroutine that is asking its siblings to make the next move.) We save time jumping across such call-chains by using a special link field called the |focus|: If |p| is a passive fringe node whose righthand neighbor |p->right| is active, |p->focus| is the rightmost active node to the left of~|p| in the fringe; otherwise |p->focus=p|. (The special |head| node is always considered to be active, for purposes of this definition, but it is not strictly speaking a member of the fringe.) The loopless implementation works with records called lnodes, just as the coroutine implementation worked with cnodes. Besides the dynamic |bit| and |left| and |right| and |focus| fields already mentioned, each lnode also has a static field called |lchild|, representing its leftmost child. (There is no need for an |rchild| field, since |p->rchild=p-1| when |p->lchild!=NULL|.) If |p| is not in the fringe, |p->focus| should equal |p|. Also, |p->left| and |p->right| are assumed to equal the nearest siblings of |p| to the left and right, respectively, if such siblings exist; otherwise |p->left| and/or |p->right| are undefined. @= typedef struct lnode_struct { char bit; /* either 0 or 1; always 1 when a child's bit is set */ struct lnode_struct *left,*right; /* neighbors in the forest and/or fringe */ struct lnode_struct *lchild; /* leftmost child */ struct lnode_struct *focus; /* red-tape cutter for efficiency */ } lnode; @ Here now is the basic outline of the loopless implementation: @= { register lnode *p,*q,*r; @; while (1) { @; @; if (p!=head) { if (p->bit==0) { p->bit=1; /* moving forward */ @; }@+else { p->bit=0; /* moving backward */ @; } }@+else if (been_there_and_done_that) break; else { printf("... and now we generate them in reverse:\n"); been_there_and_done_that=true;@+ continue; } @; } } @ Initialization of the lnodes is similar to initialization of the cnodes, but more links need to be set up. @d head (lnode_table+nn) @= for (k=0; k<=nn; k++) { lnode_table[k].focus=lnode_table+k; if (scope[k]scope[k]; j=scope[j]-1) { lnode_table[j].left=lnode_table+scope[j]-1; lnode_table[scope[j]-1].right=lnode_table+j; } lnode_table[k].lchild=lnode_table+j; } } head->left=head-1, (head-1)->right=head; head->right=head->lchild, head->lchild->left=head; @ @= lnode lnode_table[forestsize+1]; /* the lnodes */ boolean been_there_and_done_that; @ @= q=head->left; p=q->focus; q->focus=q; @ @= if (p->lchild) { q=p->right; q->left=p-1, (p-1)->right=q; p->right=p->lchild, p->lchild->left=p; } @ @= if (p->lchild) { q=(p-1)->right; p->right=q, q->left=p; } @ At this point we know that |p->right| is active. @= p->focus=p->left->focus; p->left->focus=p->left; @ @= for (k=0;k= for (k=0;k<=nn;k++) { printf("lnode %d: bit=%d, ",k,lnode_table[k].bit); printf("focus=%d, left=%d, right=%d, lchild=%d\n", rel(focus),rel(left),rel(right),rel(lchild)); } @* Index.