1 /* IP.c */
2
3 #include "../Utilities.h"
4
5 #define MYDEBUG 0
6
7 /*--------------------------------------------------------------------*/
8 /*
9 ---------------------------------
10 purpose -- to print out a IP list
11
12 created -- 95sep22, cca
13 ---------------------------------
14 */
15 void
IP_fprintf(FILE * fp,IP * ip)16 IP_fprintf (
17 FILE *fp,
18 IP *ip
19 ) {
20 if ( fp != NULL && ip != NULL ) {
21 int i = 0 ;
22 while ( ip != NULL ) {
23 if ( i % 16 == 0 ) fprintf(fp, "\n ") ;
24 fprintf(fp, " %4d", ip->val) ;
25 ip = ip->next ;
26 i++ ;
27 }
28 }
29 return ; }
30
31 /*--------------------------------------------------------------------*/
32 /*
33 ------------------------------------------------------------------
34 purpose -- to write out an integer list with eighty column lines
35
36 input --
37
38 fp -- file pointer, must be formatted and write access
39 ip -- head of list
40 column -- present column
41
42 return value -- present column
43
44 created -- 95sep22, cca
45 ------------------------------------------------------------------
46 */
47 int
IP_fp80(FILE * fp,IP * ip,int column)48 IP_fp80 (
49 FILE *fp,
50 IP *ip,
51 int column
52 ) {
53 if ( fp != NULL && ip != NULL ) {
54 int inum, nchar, pow ;
55 while ( ip != NULL ) {
56 inum = ip->val ;
57 if ( inum < 0 ) {
58 inum = -inum ;
59 nchar = 3 ;
60 } else {
61 nchar = 2 ;
62 }
63 for ( pow = 10 ; inum >= pow ; pow *= 10 ) {
64 nchar++ ;
65 }
66 if ( (column += nchar) >= 80 ) {
67 fprintf(fp, "\n") ;
68 column = nchar ;
69 }
70 fprintf(fp, " %d", ip->val) ;
71 ip = ip->next ;
72 }
73 }
74 return(column) ; }
75
76 /*--------------------------------------------------------------------*/
77 /*
78 ---------------------------------------------------------
79 initializer.
80 create and return an array of n IP structures.
81 the structures are linked in one of three ways.
82 flag = 0 (IP_NULL) --> ip->next = NULL
83 flag = 1 (IP_FORWARD) --> ip->next = successor in list
84 flag = 2 (IP_BACKWARD) --> ip->next = predecessor in list
85
86 created -- 95sep22, cca
87 ---------------------------------------------------------
88 */
89 IP *
IP_init(int n,int flag)90 IP_init (
91 int n,
92 int flag
93 ) {
94 IP *base = NULL ;
95 if ( n > 0 ) {
96 if ( flag != IP_NULL
97 && flag != IP_FORWARD
98 && flag != IP_BACKWARD ) {
99 fprintf(stderr, "\n fatal error in IPinit, invalid data"
100 "\n n = %d, flag = %d"
101 "\n flag must be 0 (IP_NULL), 1 (IP_FORWARD) or 2(IP_BACKWARD)\n",
102 n, flag) ;
103 exit(-1) ;
104 } else {
105 int i ;
106 IP *head, *ip, *tail ;
107 ALLOCATE(base, struct _IP, n) ;
108 switch ( flag ) {
109 case IP_FORWARD :
110 head = NULL ;
111 for ( i = n - 1, ip = base + i ; i >= 0 ; i--, ip-- ) {
112 ip->next = head ;
113 ip->val = 0 ;
114 head = ip ;
115 }
116 break ;
117 case IP_BACKWARD :
118 head = tail = base + n - 1 ;
119 head->val = 0 ;
120 for ( i = n - 2, ip = head + i ; i >= 0 ; i--, ip-- ) {
121 tail->next = ip ;
122 ip->val = 0 ;
123 }
124 tail->next = NULL ;
125 break ;
126 case IP_NULL :
127 for ( i = 0, ip = base ; i < n ; i++, ip++ ) {
128 ip->val = 0 ;
129 ip->next = NULL ;
130 }
131 break ;
132 }
133 }
134 }
135 return(base) ; }
136
137 /*--------------------------------------------------------------------*/
138 /*
139 -----------------------------------------------
140 free the storage for an array of IP structures,
141 must have been allocated by IP_init
142
143 created -- 95sep22, cca
144 -----------------------------------------------
145 */
146 void
IP_free(IP * ip)147 IP_free (
148 IP *ip
149 ) {
150 if ( ip != NULL ) {
151 FREE(ip) ;
152 }
153 return ; }
154
155 /*--------------------------------------------------------------------*/
156 /*
157 ----------------------------------
158 merge two lists in ascending order
159
160 created -- 95sep22, cca
161 ----------------------------------
162 */
163 IP *
IP_mergeUp(IP * ip1,IP * ip2)164 IP_mergeUp (
165 IP *ip1,
166 IP *ip2
167 ) {
168 IP *head, *tail ;
169 /*
170 -------------------
171 check for NULL list
172 -------------------
173 */
174 if ( ip1 == NULL ) {
175 head = ip2 ;
176 } else if ( ip2 == NULL ) {
177 head = ip1 ;
178 } else {
179 /*
180 ------------------------------------------
181 neither list is NULL, assign first element
182 ------------------------------------------
183 */
184 if ( ip2->val < ip1->val ) {
185 head = tail = ip2 ;
186 ip2 = ip2->next ;
187 } else {
188 head = tail = ip1 ;
189 ip1 = ip1->next ;
190 }
191 /*
192 --------------------------------------
193 merge the lists until one is exhausted
194 --------------------------------------
195 */
196 while ( ip1 != NULL && ip2 != NULL ) {
197 if ( ip2->val < ip1->val ) {
198 tail->next = ip2 ;
199 tail = ip2 ;
200 ip2 = ip2->next ;
201 } else {
202 tail->next = ip1 ;
203 tail = ip1 ;
204 ip1 = ip1->next ;
205 }
206 }
207 /*
208 ----------------------------------
209 add the remaining list to the tail
210 ----------------------------------
211 */
212 if ( ip1 == NULL ) {
213 tail->next = ip2 ;
214 } else {
215 tail->next = ip1 ;
216 }
217 }
218
219 return(head) ; }
220
221 /*--------------------------------------------------------------------*/
222 /*
223 ---------------------------------------------
224 purpose -- to sort a singly linked list in
225 ascending order using a radix sort
226
227 created -- 95sep22, cca
228 ---------------------------------------------
229 */
230 IP *
IP_radixSortUp(IP * ip)231 IP_radixSortUp (
232 IP *ip
233 ) {
234 int b1, b2, d, dneg, dpos, i, j, negmin, posmax ;
235 IP *head, *next, *tail ;
236 IP *poshead, *neghead, *zerohead ;
237 IP *postail, *negtail, *zerotail ;
238 #define BASE 10
239 IP *heads[BASE], *tails[BASE] ;
240 /*
241 --------------------------------------------------------
242 split the list into negative, zero and positive sublists
243 --------------------------------------------------------
244 */
245 poshead = postail = neghead = negtail = zerohead = NULL ;
246 zerotail = NULL ;
247 posmax = negmin = 0 ;
248 while ( ip != NULL ) {
249 next = ip->next ;
250 if ( ip->val > 0 ) {
251 ip->next = poshead, poshead = ip ;
252 if ( posmax < ip->val ) {
253 posmax = ip->val ;
254 }
255 } else if ( ip->val < 0 ) {
256 ip->next = neghead, neghead = ip ;
257 if ( negmin > ip->val ) {
258 negmin = ip->val ;
259 }
260 } else {
261 if ( zerohead == NULL ) {
262 zerotail = ip ;
263 }
264 ip->next = zerohead, zerohead = ip ;
265 }
266 ip = next ;
267 }
268 #if MYDEBUG > 0
269 fprintf(stdout, "\n positive list :") ;
270 IP_fp80(stdout, poshead, 16) ;
271 fprintf(stdout, "\n zero list :") ;
272 IP_fp80(stdout, zerohead, 16) ;
273 fprintf(stdout, "\n negative list :") ;
274 IP_fp80(stdout, neghead, 16) ;
275 fflush(stdout) ;
276 #endif
277 /*
278 ---------------
279 find the limits
280 ---------------
281 */
282 dpos = 0 ;
283 while ( posmax > 0 ) {
284 dpos++ ;
285 posmax /= 10 ;
286 }
287 negmin = - negmin ;
288 dneg = 0 ;
289 while ( negmin > 0 ) {
290 dneg++ ;
291 negmin /= 10 ;
292 }
293 if ( dpos > dneg ) {
294 d = dpos ;
295 } else {
296 d = dneg ;
297 }
298 #if MYDEBUG > 0
299 fprintf(stdout, "\n dneg %d, dpos %d, d %d", dneg, dpos, d) ;
300 fflush(stdout) ;
301 #endif
302 /*
303 ----------------------
304 sort the positive list
305 ----------------------
306 */
307 #if MYDEBUG > 0
308 fprintf(stdout, "\n sorting the positive list") ;
309 #endif
310 for ( i = 0 ; i < BASE ; i++ ) {
311 heads[i] = tails[i] = NULL ;
312 }
313 b1 = 1 ;
314 for ( i = 0 ; i < dpos ; i++ ) {
315 b2 = BASE * b1 ;
316 ip = poshead ; poshead = NULL ;
317 #if MYDEBUG > 0
318 fprintf(stdout, "\n b1 %d, b2 %d", b1, b2) ;
319 #endif
320 while ( ip != NULL ) {
321 next = ip->next ;
322 j = (ip->val % b2) / b1 ;
323 #if MYDEBUG > 0
324 fprintf(stdout, "\n ip->val %d, j %d", ip->val, j) ;
325 #endif
326 if ( heads[j] == NULL ) {
327 heads[j] = ip ;
328 } else {
329 tails[j]->next = ip ;
330 }
331 tails[j] = ip ;
332 ip = next ;
333 }
334 for ( j = 0 ; j < BASE ; j++ ) {
335 if ( heads[j] != NULL ) {
336 if ( poshead == NULL ) {
337 poshead = heads[j] ;
338 } else {
339 postail->next = heads[j] ;
340 }
341 postail = tails[j] ;
342 heads[j] = tails[j] = NULL ;
343 }
344 }
345 postail->next = NULL ;
346 b1 = b2 ;
347 }
348 #if MYDEBUG > 0
349 fprintf(stdout, "\n positive list") ;
350 IP_fprintf(stdout, poshead) ;
351 #endif
352 /*
353 ----------------------
354 sort the negative list
355 ----------------------
356 */
357 #if MYDEBUG > 0
358 fprintf(stdout, "\n sorting the negative list") ;
359 #endif
360 b1 = 1 ;
361 for ( i = 0 ; i < dneg ; i++ ) {
362 b2 = BASE * b1 ;
363 #if MYDEBUG > 0
364 fprintf(stdout, "\n b1 %d, b2 %d", b1, b2) ;
365 #endif
366 ip = neghead ; neghead = NULL ;
367 while ( ip != NULL ) {
368 next = ip->next ;
369 j = ((-ip->val) % b2) / b1 ;
370 #if MYDEBUG > 0
371 fprintf(stdout, "\n ip->val %d, j %d", ip->val, j) ;
372 #endif
373 if ( heads[j] == NULL ) {
374 heads[j] = ip ;
375 } else {
376 tails[j]->next = ip ;
377 }
378 tails[j] = ip ;
379 ip = next ;
380 }
381 for ( j = 0 ; j < BASE ; j++ ) {
382 if ( heads[j] != NULL ) {
383 if ( neghead == NULL ) {
384 neghead = heads[j] ;
385 } else {
386 negtail->next = heads[j] ;
387 }
388 negtail = tails[j] ;
389 heads[j] = tails[j] = NULL ;
390 }
391 }
392 negtail->next = NULL ;
393 b1 = b2 ;
394 }
395 #if MYDEBUG > 0
396 fprintf(stdout, "\n negative list") ;
397 IP_fprintf(stdout, neghead) ;
398 #endif
399 /*
400 ---------------------------
401 concatenate the three lists
402 ---------------------------
403 */
404 head = tail = ip = neghead ;
405 while ( ip != NULL ) {
406 next = ip->next ;
407 ip->next = head ;
408 head = ip ;
409 ip = next ;
410 }
411 if ( tail != NULL ) {
412 tail->next = NULL ;
413 }
414 #if MYDEBUG > 0
415 fprintf(stdout, "\n 1. head = %p, tail = %p", head, tail) ;
416 #endif
417 if ( zerohead != NULL ) {
418 if ( tail != NULL ) {
419 tail->next = zerohead ;
420 } else {
421 head = zerohead ;
422 }
423 tail = zerotail ;
424 }
425 if ( tail != NULL ) {
426 tail->next = NULL ;
427 }
428 #if MYDEBUG > 0
429 fprintf(stdout, "\n 2. head = %p, tail = %p", head, tail) ;
430 #endif
431 if ( poshead != NULL ) {
432 if ( tail != NULL ) {
433 tail->next = poshead ;
434 } else {
435 head = poshead ;
436 }
437 tail = postail ;
438 }
439 if ( tail != NULL ) {
440 tail->next = NULL ;
441 }
442 #if MYDEBUG > 0
443 fprintf(stdout, "\n 3. head = %p, tail = %p", head, tail) ;
444 IP_fprintf(stdout, head) ;
445 #endif
446
447 return(head) ; }
448 /*--------------------------------------------------------------------*/
449 /*
450 ----------------------------------------------
451 purpose -- to sort a singly linked list in
452 descending order using a radix sort
453
454 created -- 95sep22, cca
455 ----------------------------------------------
456 */
457 IP *
IP_radixSortDown(IP * ip)458 IP_radixSortDown (
459 IP *ip
460 ) {
461 IP *ip1 = NULL ;
462 if ( ip != NULL ) {
463 IP *ip0 ;
464
465 for ( ip0 = ip ; ip0 != NULL ; ip0 = ip0->next ) {
466 ip0->val = -ip0->val ;
467 }
468 ip1 = IP_radixSortUp(ip) ;
469 for ( ip0 = ip1 ; ip0 != NULL ; ip0 = ip0->next ) {
470 ip0->val = -ip0->val ;
471 }
472 }
473 return(ip1) ; }
474
475 /*--------------------------------------------------------------------*/
476 /*
477 -----------------------------------------------
478 sort a list in ascending order using merge sort
479
480 created -- 95sep22, cca
481 -----------------------------------------------
482 */
483 IP *
IP_mergeSortUp(IP * ip0)484 IP_mergeSortUp (
485 IP *ip0
486 ) {
487 int i, m, m1 ;
488 IP *ip, *ip1, *ip2, *prev ;
489 /*
490 ----------------------------------------
491 count the number of elements in the list
492 ----------------------------------------
493 */
494 #if MYDEBUG > 0
495 fprintf(stdout, "\n inside IP_mergeSortUp :") ;
496 IP_fp80(stdout, ip0, 25) ;
497 fflush(stdout) ;
498 #endif
499 for ( ip = ip0, m = 0 ; ip != NULL ; ip = ip->next ) {
500 m++ ;
501 }
502 if ( m <= 1 ) {
503 return(ip0) ;
504 } else {
505 m1 = m / 2 ;
506 #if MYDEBUG > 0
507 fprintf(stdout, "\n m = %d, m1 = %d, m2 = %d", m, m1, m-m1) ;
508 fflush(stdout) ;
509 #endif
510 for ( i = 1, ip = ip0, prev = NULL ; i < m1 ; i++ ) {
511 prev = ip ;
512 ip = ip->next ;
513 }
514 ip2 = ip->next ;
515 ip->next = NULL ;
516 ip1 = ip0 ;
517 #if MYDEBUG > 0
518 fprintf(stdout, "\n calling IP_mergeSortUp :") ;
519 IP_fp80(stdout, ip1, 13) ;
520 fflush(stdout) ;
521 #endif
522 ip1 = IP_mergeSortUp(ip1) ;
523 #if MYDEBUG > 0
524 fprintf(stdout, "\n return from IP_mergeSortUp :") ;
525 IP_fp80(stdout, ip1, 13) ;
526 fprintf(stdout, "\n calling IPmergeSortUp :") ;
527 IP_fp80(stdout, ip2, 13) ;
528 #endif
529 ip2 = IP_mergeSortUp(ip2) ;
530 #if MYDEBUG > 0
531 fprintf(stdout, "\n return from IP_mergeSortUp :") ;
532 IP_fp80(stdout, ip2, 13) ;
533 fprintf(stdout, "\n calling IP_mergeUp :") ;
534 fprintf(stdout, "\n first list") ;
535 IP_fp80(stdout, ip1, 13) ;
536 fprintf(stdout, "\n second list") ;
537 IP_fp80(stdout, ip2, 13) ;
538 #endif
539 ip = IP_mergeUp(ip1, ip2) ;
540 #if MYDEBUG > 0
541 fprintf(stdout, "\n return from IP_mergeUp, sorted list : ") ;
542 IP_fp80(stdout, ip, 40) ;
543 fflush(stdout) ;
544 #endif
545 return(ip) ;
546 }
547 }
548 /*--------------------------------------------------------------------*/
549