1\def\covernote{Copyright 1987 Norman Ramsey -- Princeton University}
2
3\def\vbar{\.{|}}
4@*Directory Trees.
5Our object is to print out a directory hierarchy in some pleasant way.
6The program takes output from {\tt find * -type d -print \vbar\ sort}
7@^system dependencies@>
8and produces a nicer-looking listing.
9More precisely, our input, which is the output of {\tt find} followed
10by {\tt sort}, is a list of fully qualified directory names (parent
11and child separated by slashes |'/'|); everything has already been
12sorted nicely into lexicographic order.
13
14The {\tt treeprint} routine takes one option, |"-p"|, which tells it
15to use the printer's line-drawing set, rather than the terminal's.
16
17@c
18@<Global definitions@>@;
19@<Global include files@>@;
20@<Global declarations@>@;
21
22@#
23main(argc, argv)
24     int argc;
25     char **argv;
26{
27@<|main| variable declarations@>;
28@<Search for options and set special characters on |"-p"|@>;
29@<Read output from find and enter into tree@>;
30@<Write tree on standard output@>@;
31exit(0);
32}
33
34@
35We make all the siblings of a directory a linked list off of its left child,
36and the offspring a linked list off the right side.
37Data are just directory names.
38@d sibling left
39@d child right
40
41@<Global decl...@>=
42typedef struct tnode {
43  struct tnode *left, *right;
44  char *data;
45} TNODE;
46@ @<|main| variable...@>=
47struct tnode *root=NULL;
48
49
50
51@*Input.
52Reading the tree is simple---we read one line at a time, and call on the
53recursive |add_tree| procedure.
54
55@c
56read_tree (fp, rootptr)
57   FILE *fp;
58   struct tnode **rootptr;
59{
60   char buf[255], *p;
61
62   while ((fgets(buf, 255, fp))!=NULL) {
63     @<If |buf| contains a newline, make it end there@>;
64     add_tree(rootptr, buf);
65   }
66 }
67@ @<Global include...@>=
68#include <stdio.h>
69
70@ Depending what system you're on, you may or may not get a newline in |buf|.
71@<If |buf| contains a newline...@>=
72     p=buf; while (*p!='\0'&&*p!='\n') p++;
73@^system dependencies@>
74     *p='\0';
75
76@
77To add a string, we split off the first part of the name and insert it into
78the sibling list. We then do the rest of the string as a child of the new node.
79
80@c
81add_tree(rootptr, p)
82     struct tnode **rootptr;
83     char *p;
84{
85     char *s;
86     int slashed;
87
88     if (*p=='\0') return;
89
90@<Break up the string so |p| is the first word,
91     |s| points at null-begun remainder,
92    and |slashed| tells whether |*s=='/'| on entry@>;
93
94     if (*rootptr==NULL) {
95@<Allocate new node to hold string of size |strlen(p)|@>;
96       strcpy((*rootptr)->data,p);
97     }
98     if (strcmp((*rootptr)->data,p)==0) {
99           if (slashed) ++s;
100           add_tree(&((*rootptr)->child),s);
101	 }
102       else {
103           if (slashed) *s='/';
104           add_tree(&((*rootptr)->sibling),p);
105	 }
106   }
107
108@ We perform some nonsense to cut off the string |p| so that |p| just
109holds the first word of a multiword name. Variable |s| points at what
110was either the end of |p| or a slash delimiting names. In either case
111|*s| is made |'\0'|.  Later, depending on whether we want to pass the
112whole string or the last piece, we will restore the slash or advance
113|s| one character to the right.
114
115@<Break up...@>=
116     for (s=p;*s!='\0'&&*s!='/';) s++;
117     if (*s=='/') {
118       slashed=1;
119       *s='\0';
120     } else slashed=0;
121
122@ Node allocation is perfectly standard \dots
123@<Allocate new node...@>=
124       *rootptr=(struct tnode *) malloc (sizeof(struct tnode));
125       (*rootptr)->left = (*rootptr)->right = NULL;
126       (*rootptr)->data = malloc (strlen(p)+1);
127
128@
129@<Global decl...@>= char *malloc();
130
131@ In this simple implementation, we just read from standard input.
132@<Read...@>= read_tree(stdin,&root);
133
134@*Output.
135We begin by defining some lines, tees, and corners.
136The |s| stands for screen and the |p| for printer.
137You will have to change this for your line-drawing set.
138@^system dependencies@>
139
140@<Global definitions@>=
141#define svert '|'
142#define shoriz '-'
143#define scross '+'
144#define scorner '\\' /* lower left corner */
145
146#define pvert '|'
147#define phoriz '-'
148#define pcross '+'
149#define pcorner '\\' /* lower left corner */
150
151@ The default is to use the terminal's line drawing set.
152@<Global declarations@>=
153char vert=svert;
154char horiz=shoriz;
155char cross=scross;
156char corner=scorner;
157
158@ With option |"-p"| use the printer character set.
159@<Search for options...@>=
160while (--argc>0) {
161  if (**++argv=='-') {
162    switch (*++(*argv)) {
163      case 'p':
164        vert=pvert;
165        horiz=phoriz;
166        cross=pcross;
167        corner=pcorner;
168	break;
169      default:
170        fprintf(stderr,"treeprint: bad option -%c\n",**argv);
171	break;
172      }
173  }
174}
175
176@ We play games with a character stack to figure out when to put in vertical
177bars.
178A vertical bar connects every sibling with its successor, but the last sibling
179in a list is followed by blanks, not by vertical bars. The state of
180bar-ness or space-ness for each preceding sibling is recorded in the
181|indent_string| variable, one character (bar or blank) per sibling.
182
183@<Global decl...@>=
184char indent_string[100]="";
185
186@  Children get printed
187before siblings.
188We don't bother trying to bring children up to the same line as their parents,
189because the \UNIX/ filenames are so long.
190
191We define a predicate telling us when a sibling is the last in a series.
192@d is_last(S) (S->sibling==NULL)
193
194@c
195print_node(fp, indent_string, node)
196     FILE *fp;
197     char *indent_string;
198     struct tnode *node;
199{
200  char string[255];
201     int i;
202     char *p, *is;
203
204  if (node==NULL) {
205  }
206  else {
207    *string='\0';
208    for (i=strlen(indent_string); i>0; i--)
209      strcat(string,@,      " |  ");
210    strcat(string,@t\ \ @>  " +--");
211@<Replace chars in |string| with chars from
212         line-drawing set and from |indent_string|@>;
213    fprintf(fp,"%s%s\n",string,node->data);
214
215@#
216    /* Add vertical bar or space for this sibling (claim |*is=='\0'|) */
217    *is++ = (is_last(node) ? ' ' : vert);
218    *is='\0';
219
220    print_node(fp, indent_string, node->child); /* extended |indent_string| */
221    *--is='\0';
222    print_node(fp, indent_string, node->sibling); /* original |indent_string| */
223  }
224
225}
226@ For simplicity, we originally wrote connecting lines with |'|'|, |'+'|, and
227|'-'|.
228Now we replace those characters with appropriate characters from the
229line-drawing set.
230We take the early vertical bars and replace them with characters from
231|indent_string|, and we replace the other characters appropriately.
232We are sure to put a |corner|, not a |cross|, on the last sibling in
233a group.
234@<Replace chars...@>=
235    is=indent_string;
236    for (p=string; *p!='\0'; p++) switch(*p) {
237       case '|': *p=*is++; break;
238       case '+': *p=(is_last(node) ? corner : cross); break;
239       case '-': *p=horiz; break;
240       default: break;
241	       }
242
243
244@ For this simple implementation, we just write on standard output.
245
246@<Write...@>= print_node(stdout, indent_string, root);
247
248@*Index.
249