1 /*
2 * lists.c -- utilities for ilist, glist, and g2list
3 *
4 */
5
6 #include "header.h"
7
8 /* ============================================================ ilist */
9
10 /*************
11 *
12 * free_ilist_list()
13 *
14 *************/
15
free_ilist_list(struct ilist * p)16 void free_ilist_list(struct ilist *p)
17 {
18 if (p != NULL) {
19 free_ilist_list(p->next);
20 free_ilist(p);
21 }
22 } /* free_ilist_list */
23
24 /*************
25 *
26 * ilist_tack_on()
27 *
28 *************/
29
ilist_tack_on(struct ilist * a,int i)30 struct ilist *ilist_tack_on(struct ilist *a, int i)
31 {
32 if (a == NULL) {
33 struct ilist *b = get_ilist();
34 b->i = i;
35 return b;
36 }
37 else {
38 a->next = ilist_tack_on(a->next, i);
39 return a;
40 }
41 } /* ilist_tack_on */
42
43 /*************
44 *
45 * iset_add()
46 *
47 *************/
48
iset_add(int i,struct ilist * p)49 struct ilist *iset_add(int i, struct ilist *p)
50 {
51 if (p == NULL) {
52 p = get_ilist();
53 p->i = i;
54 return p;
55 }
56 else if (p->i == i)
57 return p;
58 else if (p->i > i) {
59 struct ilist *q = get_ilist();
60 q->i = i;
61 q->next = p;
62 return q;
63 }
64 else {
65 p->next = iset_add(i, p->next);
66 return p;
67 }
68 } /* iset_add */
69
70 /*************
71 *
72 * iset_remove() -- assume ordered, remove first
73 *
74 *************/
75
iset_remove(int i,struct ilist * p)76 struct ilist *iset_remove(int i, struct ilist *p)
77 {
78 if (p == NULL) {
79 return p;
80 }
81 else if (p->i == i) {
82 struct ilist *q = p;
83 p = p->next;
84 free_ilist(q);
85 return p;
86 }
87 else if (p->i > i) {
88 return p;
89 }
90 else {
91 p->next = iset_remove(i, p->next);
92 return p;
93 }
94 } /* iset_remove */
95
96 /*************
97 *
98 * ilist_member()
99 *
100 *************/
101
ilist_member(int i,struct ilist * p)102 int ilist_member(int i, struct ilist *p)
103 {
104 if (p == NULL)
105 return 0;
106 else if (p->i == i)
107 return 1;
108 else
109 return ilist_member(i, p->next);
110 } /* ilist_member */
111
112 /*************
113 *
114 * iset_subset()
115 *
116 *************/
117
iset_subset(struct ilist * a,struct ilist * b)118 int iset_subset(struct ilist *a, struct ilist *b)
119 {
120 if (a == NULL)
121 return 1;
122 else
123 return (ilist_member(a->i, b) && iset_subset(a->next, b));
124 } /* iset_subset */
125
126 /*************
127 *
128 * iset_subtract()
129 *
130 *************/
131
iset_subtract(struct ilist * a,struct ilist * b)132 struct ilist *iset_subtract(struct ilist *a, struct ilist *b)
133 {
134 if (b == NULL)
135 return copy_ilist(a);
136 else {
137 a = iset_subtract(a, b->next);
138 return iset_remove(b->i, a);
139 }
140 } /* iset_subtract */
141
142 /*************
143 *
144 * iset_sort() -- insertion sort -- remove duplicates
145 *
146 *************/
147
iset_sort(struct ilist * a)148 struct ilist *iset_sort(struct ilist *a)
149 {
150 if (a == NULL)
151 return NULL;
152 else {
153 int i = a->i;
154 struct ilist *b = iset_sort(a->next);
155 free_ilist(a);
156 return iset_add(i, b);
157 }
158 } /* iset_sort */
159
160 /*************
161 *
162 * idempot_ip()
163 *
164 *************/
165
idempot_ip(struct ilist * a)166 struct ilist *idempot_ip(struct ilist *a)
167 {
168 if (a == NULL)
169 return NULL;
170 else if (ilist_member(a->i, a->next)) {
171 struct ilist *b = a->next;
172 free_ilist(a);
173 return idempot_ip(b);
174 }
175 else {
176 a->next = idempot_ip(a->next);
177 return a;
178 }
179 } /* idempot_ip */
180
181 /*************
182 *
183 * reverse_ip()
184 *
185 *************/
186
reverse_ip(struct ilist * ip1,struct ilist * ip2)187 struct ilist *reverse_ip(struct ilist *ip1, struct ilist *ip2)
188 {
189 if (ip1 == NULL)
190 return ip2;
191 else {
192 struct ilist *ip3 = ip1->next;
193 ip1->next = ip2;
194 return reverse_ip(ip3, ip1);
195 }
196 } /* reverse_ip */
197
198 /*************
199 *
200 * ilist_append() -- This uses up the two inputs.
201 *
202 *************/
203
ilist_append(struct ilist * a,struct ilist * b)204 struct ilist *ilist_append(struct ilist *a, struct ilist *b)
205 {
206 if (a == NULL)
207 return b;
208 else {
209 a->next = ilist_append(a->next, b);
210 return a;
211 }
212 } /* ilist_append */
213
214 /*************
215 *
216 * copy_ilist()
217 *
218 * Copy and return a list of pointers to integers.
219 *
220 *************/
221
copy_ilist(struct ilist * p)222 struct ilist *copy_ilist(struct ilist *p)
223 {
224 if (p == NULL)
225 return NULL;
226 else {
227 struct ilist *q = get_ilist();
228 q->i = p->i;
229 q->next = copy_ilist(p->next);
230 return q;
231 }
232 } /* copy_ilist */
233
234 /*************
235 *
236 * ilist_length()
237 *
238 *************/
239
ilist_length(struct ilist * a)240 int ilist_length(struct ilist *a)
241 {
242 if (a == NULL)
243 return 0;
244 else
245 return 1 + ilist_length(a->next);
246 } /* ilist_length */
247
248 /*************
249 *
250 * copy_ilist_segment() -- copy the first n members
251 *
252 *************/
253
copy_ilist_segment(struct ilist * p,int n)254 struct ilist *copy_ilist_segment(struct ilist *p, int n)
255 {
256 if (n == 0 || p == NULL)
257 return NULL;
258 else {
259 struct ilist *q = get_ilist();
260 q->i = p->i;
261 q->next = copy_ilist_segment(p->next, n-1);
262 return q;
263 }
264 } /* copy_ilist_segment */
265
266 /*************
267 *
268 * print_ilist(fp, ip)
269 *
270 *************/
271
print_ilist(FILE * fp,struct ilist * ip)272 void print_ilist(FILE *fp,
273 struct ilist *ip)
274 {
275 struct ilist *p;
276 fprintf(fp, "(");
277 for (p = ip; p; p = p->next)
278 fprintf(fp, "%d%s", p->i, (p->next ? " " : ""));
279 fprintf(fp, ")");
280 } /* print_ilist */
281
282 /*************
283 *
284 * p_ilist(ip)
285 *
286 *************/
287
p_ilist(struct ilist * ip)288 void p_ilist(struct ilist *ip)
289 {
290 print_ilist(stdout, ip);
291 printf("\n");
292 } /* p_ilist */
293
294 /* ============================================================ glist */
295
296 /*************
297 *
298 * glist_length()
299 *
300 *************/
301
glist_length(struct glist * a)302 int glist_length(struct glist *a)
303 {
304 if (a == NULL)
305 return 0;
306 else
307 return 1 + glist_length(a->next);
308 } /* glist_length */
309
310 /*************
311 *
312 * copy_glist() -- don't copy objects (how could we??)
313 *
314 *************/
315
copy_glist(struct glist * p)316 struct glist *copy_glist(struct glist *p)
317 {
318 if (p == NULL)
319 return NULL;
320 else {
321 struct glist *q = get_glist();
322 q->v = p->v;
323 q->next = copy_glist(p->next);
324 return q;
325 }
326 } /* copy_glist */
327
328 /*************
329 *
330 * glist_append() -- this uses up both arguments
331 *
332 *************/
333
glist_append(struct glist * a,struct glist * b)334 struct glist *glist_append(struct glist *a, struct glist *b)
335 {
336 if (a == NULL)
337 return b;
338 else {
339 a->next = glist_append(a->next, b);
340 return a;
341 }
342 } /* glist_append */
343
344 /*************
345 *
346 * glist_prepend() -- put a pointer onto the front.
347 *
348 *************/
349
glist_prepend(void * p,struct glist * a)350 struct glist *glist_prepend(void *p, struct glist *a)
351 {
352 struct glist *b = get_glist();
353 b->v = p;
354 b->next = a;
355 return b;
356 } /* glist_prepend */
357
358 /*************
359 *
360 * glist_tack_on()
361 *
362 *************/
363
glist_tack_on(struct glist * a,void * v)364 struct glist *glist_tack_on(struct glist *a, void *v)
365 {
366 if (a == NULL) {
367 struct glist *b = get_glist();
368 b->v = v;
369 return b;
370 }
371 else {
372 a->next = glist_tack_on(a->next, v);
373 return a;
374 }
375 } /* glist_tack_on */
376
377 /*************
378 *
379 * free_glist_list()
380 *
381 *************/
382
free_glist_list(struct glist * p)383 void free_glist_list(struct glist *p)
384 {
385 if (p != NULL) {
386 free_glist_list(p->next);
387 free_glist(p);
388 }
389 } /* free_glist_list */
390
391 /* ============================================================ g2list */
392
393 /*************
394 *
395 * g2list_length()
396 *
397 *************/
398
g2list_length(struct g2list * a)399 int g2list_length(struct g2list *a)
400 {
401 if (a == NULL)
402 return 0;
403 else
404 return 1 + g2list_length(a->next);
405 } /* g2list_length */
406
407 /* ===================================================== glist and ilist */
408
409 /*************
410 *
411 * member_is_subset()
412 *
413 *************/
414
member_is_subset(struct glist * a,struct ilist * s)415 int member_is_subset(struct glist *a, struct ilist *s)
416 {
417 if (a == NULL)
418 return 0;
419 else if (iset_subset(a->v, s))
420 return 1;
421 else
422 return member_is_subset(a->next, s);
423 } /* member_is_subset */
424
425 /*************
426 *
427 * copy_glist_of_ilists()
428 *
429 *************/
430
copy_glist_of_ilists(struct glist * a)431 struct glist *copy_glist_of_ilists(struct glist *a)
432 {
433 if (a == NULL)
434 return NULL;
435 else {
436 struct glist *b = get_glist();
437 b->v = copy_ilist(a->v);
438 b->next = copy_glist_of_ilists(a->next);
439 return b;
440 }
441 } /* copy_glist_of_ilists */
442
443 /*************
444 *
445 * free_glist_of_ilists()
446 *
447 *************/
448
free_glist_of_ilists(struct glist * p)449 void free_glist_of_ilists(struct glist *p)
450 {
451 if (p != NULL) {
452 free_glist_of_ilists(p->next);
453 free_ilist_list(p->v);
454 free_glist(p);
455 }
456 } /* free_glist_of_ilists */
457
458