\def\covernote{Copyright 1987 Norman Ramsey -- Princeton University}\def\vbar{\.{|}}@*Directory Trees.Our object is to print out a directory hierarchy in some pleasant way.The program takes output from {\tt find * -type d -print \vbar\ sort}@^system dependencies@>and produces a nicer-looking listing.More precisely, our input, which is the output of {\tt find} followedby {\tt sort}, is a list of fully qualified directory names (parentand child separated by slashes |'/'|); everything has already beensorted nicely into lexicographic order.The {\tt treeprint} routine takes one option, |"-p"|, which tells itto use the printer's line-drawing set, rather than the terminal's.@c@<Global definitions@>@;@<Global include files@>@;@<Global declarations@>@;@#main(argc, argv)     int argc;     char **argv;{@<|main| variable declarations@>;@<Search for options and set special characters on |"-p"|@>;@<Read output from find and enter into tree@>;@<Write tree on standard output@>@;exit(0);}@We make all the siblings of a directory a linked list off of its left child, and the offspring a linked list off the right side.Data are just directory names.@d sibling left@d child right@<Global decl...@>=typedef struct tnode {  struct tnode *left, *right;  char *data;} TNODE;@ @<|main| variable...@>=struct tnode *root=NULL;@*Input.Reading the tree is simple---we read one line at a time, and call on the recursive |add_tree| procedure.@cread_tree (fp, rootptr)   FILE *fp;   struct tnode **rootptr;{   char buf[255], *p;   while ((fgets(buf, 255, fp))!=NULL) {     @<If |buf| contains a newline, make it end there@>;     add_tree(rootptr, buf);   } }@ @<Global include...@>=#include <stdio.h>@ Depending what system you're on, you may or may not get a newline in |buf|.@<If |buf| contains a newline...@>=     p=buf; while (*p!='\0'&&*p!='\n') p++;@^system dependencies@>     *p='\0';@ To add a string, we split off the first part of the name and insert it into the sibling list. We then do the rest of the string as a child of the new node.@cadd_tree(rootptr, p)     struct tnode **rootptr;     char *p;{     char *s;     int slashed;     if (*p=='\0') return;@<Break up the string so |p| is the first word,     |s| points at null-begun remainder,    and |slashed| tells whether |*s=='/'| on entry@>;     if (*rootptr==NULL) {@<Allocate new node to hold string of size |strlen(p)|@>;       strcpy((*rootptr)->data,p);     }      if (strcmp((*rootptr)->data,p)==0) {           if (slashed) ++s;           add_tree(&((*rootptr)->child),s);	 }       else {           if (slashed) *s='/';           add_tree(&((*rootptr)->sibling),p);	 }   }@ We perform some nonsense to cut off the string |p| so that |p| justholds the first word of a multiword name. Variable |s| points at whatwas either the end of |p| or a slash delimiting names. In either case|*s| is made |'\0'|.  Later, depending on whether we want to pass thewhole string or the last piece, we will restore the slash or advance|s| one character to the right.@<Break up...@>=     for (s=p;*s!='\0'&&*s!='/';) s++;     if (*s=='/') {       slashed=1;       *s='\0';     } else slashed=0;@ Node allocation is perfectly standard \dots@<Allocate new node...@>=       *rootptr=(struct tnode *) malloc (sizeof(struct tnode));       (*rootptr)->left = (*rootptr)->right = NULL;       (*rootptr)->data = malloc (strlen(p)+1);@@<Global decl...@>= char *malloc();@ In this simple implementation, we just read from standard input.@<Read...@>= read_tree(stdin,&root);@*Output.We begin by defining some lines, tees, and corners.The |s| stands for screen and the |p| for printer.You will have to change this for your line-drawing set.@^system dependencies@>@<Global definitions@>=#define svert '|'#define shoriz '-'#define scross '+'#define scorner '\\' /* lower left corner */#define pvert '|'#define phoriz '-'#define pcross '+'#define pcorner '\\' /* lower left corner */@ The default is to use the terminal's line drawing set.@<Global declarations@>=char vert=svert;char horiz=shoriz;char cross=scross;char corner=scorner;@ With option |"-p"| use the printer character set.@<Search for options...@>=while (--argc>0) {  if (**++argv=='-') {    switch (*++(*argv)) {      case 'p':         vert=pvert;        horiz=phoriz;        cross=pcross;        corner=pcorner;	break;      default:        fprintf(stderr,"treeprint: bad option -%c\n",**argv);	break;      }  }}@ We play games with a character stack to figure out when to put in verticalbars.A vertical bar connects every sibling with its successor, but the last siblingin a list is followed by blanks, not by vertical bars. The state of bar-ness or space-ness for each preceding sibling is recorded in the |indent_string| variable, one character (bar or blank) per sibling.@<Global decl...@>=char indent_string[100]="";@  Children get printed before siblings.We don't bother trying to bring children up to the same line as their parents,because the \UNIX/ filenames are so long.We define a predicate telling us when a sibling is the last in a series.@d is_last(S) (S->sibling==NULL)@cprint_node(fp, indent_string, node)     FILE *fp;     char *indent_string;     struct tnode *node;{  char string[255];     int i;     char *p, *is;  if (node==NULL) {  }  else {    *string='\0';    for (i=strlen(indent_string); i>0; i--)       strcat(string,@,      " |  ");    strcat(string,@t\ \ @>  " +--");@<Replace chars in |string| with chars from          line-drawing set and from |indent_string|@>;    fprintf(fp,"%s%s\n",string,node->data);@#    /* Add vertical bar or space for this sibling (claim |*is=='\0'|) */    *is++ = (is_last(node) ? ' ' : vert);    *is='\0';       print_node(fp, indent_string, node->child); /* extended |indent_string| */    *--is='\0';    print_node(fp, indent_string, node->sibling); /* original |indent_string| */  }}@ For simplicity, we originally wrote connecting lines with |'|'|, |'+'|, and|'-'|.Now we replace those characters with appropriate characters from the line-drawing set. We take the early vertical bars and replace them with characters from|indent_string|, and we replace the other characters appropriately.We are sure to put a |corner|, not a |cross|, on the last sibling in a group.@<Replace chars...@>=    is=indent_string;    for (p=string; *p!='\0'; p++) switch(*p) {       case '|': *p=*is++; break;       case '+': *p=(is_last(node) ? corner : cross); break;       case '-': *p=horiz; break;       default: break;	       }@ For this simple implementation, we just write on standard output.@<Write...@>= print_node(stdout, indent_string, root);@*Index.