/* IP.c */
#include "../Utilities.h"
#define MYDEBUG 0
/*--------------------------------------------------------------------*/
/*
---------------------------------
purpose -- to print out a IP list
created -- 95sep22, cca
---------------------------------
*/
void
IP_fprintf (
FILE *fp,
IP *ip
) {
if ( fp != NULL && ip != NULL ) {
int i = 0 ;
while ( ip != NULL ) {
if ( i % 16 == 0 ) fprintf(fp, "\n ") ;
fprintf(fp, " %4d", ip->val) ;
ip = ip->next ;
i++ ;
}
}
return ; }
/*--------------------------------------------------------------------*/
/*
------------------------------------------------------------------
purpose -- to write out an integer list with eighty column lines
input --
fp -- file pointer, must be formatted and write access
ip -- head of list
column -- present column
return value -- present column
created -- 95sep22, cca
------------------------------------------------------------------
*/
int
IP_fp80 (
FILE *fp,
IP *ip,
int column
) {
if ( fp != NULL && ip != NULL ) {
int inum, nchar, pow ;
while ( ip != NULL ) {
inum = ip->val ;
if ( inum < 0 ) {
inum = -inum ;
nchar = 3 ;
} else {
nchar = 2 ;
}
for ( pow = 10 ; inum >= pow ; pow *= 10 ) {
nchar++ ;
}
if ( (column += nchar) >= 80 ) {
fprintf(fp, "\n") ;
column = nchar ;
}
fprintf(fp, " %d", ip->val) ;
ip = ip->next ;
}
}
return(column) ; }
/*--------------------------------------------------------------------*/
/*
---------------------------------------------------------
initializer.
create and return an array of n IP structures.
the structures are linked in one of three ways.
flag = 0 (IP_NULL) --> ip->next = NULL
flag = 1 (IP_FORWARD) --> ip->next = successor in list
flag = 2 (IP_BACKWARD) --> ip->next = predecessor in list
created -- 95sep22, cca
---------------------------------------------------------
*/
IP *
IP_init (
int n,
int flag
) {
IP *base = NULL ;
if ( n > 0 ) {
if ( flag != IP_NULL
&& flag != IP_FORWARD
&& flag != IP_BACKWARD ) {
fprintf(stderr, "\n fatal error in IPinit, invalid data"
"\n n = %d, flag = %d"
"\n flag must be 0 (IP_NULL), 1 (IP_FORWARD) or 2(IP_BACKWARD)\n",
n, flag) ;
exit(-1) ;
} else {
int i ;
IP *head, *ip, *tail ;
ALLOCATE(base, struct _IP, n) ;
switch ( flag ) {
case IP_FORWARD :
head = NULL ;
for ( i = n - 1, ip = base + i ; i >= 0 ; i--, ip-- ) {
ip->next = head ;
ip->val = 0 ;
head = ip ;
}
break ;
case IP_BACKWARD :
head = tail = base + n - 1 ;
head->val = 0 ;
for ( i = n - 2, ip = head + i ; i >= 0 ; i--, ip-- ) {
tail->next = ip ;
ip->val = 0 ;
}
tail->next = NULL ;
break ;
case IP_NULL :
for ( i = 0, ip = base ; i < n ; i++, ip++ ) {
ip->val = 0 ;
ip->next = NULL ;
}
break ;
}
}
}
return(base) ; }
/*--------------------------------------------------------------------*/
/*
-----------------------------------------------
free the storage for an array of IP structures,
must have been allocated by IP_init
created -- 95sep22, cca
-----------------------------------------------
*/
void
IP_free (
IP *ip
) {
if ( ip != NULL ) {
FREE(ip) ;
}
return ; }
/*--------------------------------------------------------------------*/
/*
----------------------------------
merge two lists in ascending order
created -- 95sep22, cca
----------------------------------
*/
IP *
IP_mergeUp (
IP *ip1,
IP *ip2
) {
IP *head, *tail ;
/*
-------------------
check for NULL list
-------------------
*/
if ( ip1 == NULL ) {
head = ip2 ;
} else if ( ip2 == NULL ) {
head = ip1 ;
} else {
/*
------------------------------------------
neither list is NULL, assign first element
------------------------------------------
*/
if ( ip2->val < ip1->val ) {
head = tail = ip2 ;
ip2 = ip2->next ;
} else {
head = tail = ip1 ;
ip1 = ip1->next ;
}
/*
--------------------------------------
merge the lists until one is exhausted
--------------------------------------
*/
while ( ip1 != NULL && ip2 != NULL ) {
if ( ip2->val < ip1->val ) {
tail->next = ip2 ;
tail = ip2 ;
ip2 = ip2->next ;
} else {
tail->next = ip1 ;
tail = ip1 ;
ip1 = ip1->next ;
}
}
/*
----------------------------------
add the remaining list to the tail
----------------------------------
*/
if ( ip1 == NULL ) {
tail->next = ip2 ;
} else {
tail->next = ip1 ;
}
}
return(head) ; }
/*--------------------------------------------------------------------*/
/*
---------------------------------------------
purpose -- to sort a singly linked list in
ascending order using a radix sort
created -- 95sep22, cca
---------------------------------------------
*/
IP *
IP_radixSortUp (
IP *ip
) {
int b1, b2, d, dneg, dpos, i, j, negmin, posmax ;
IP *head, *next, *tail ;
IP *poshead, *neghead, *zerohead ;
IP *postail, *negtail, *zerotail ;
#define BASE 10
IP *heads[BASE], *tails[BASE] ;
/*
--------------------------------------------------------
split the list into negative, zero and positive sublists
--------------------------------------------------------
*/
poshead = postail = neghead = negtail = zerohead = NULL ;
zerotail = NULL ;
posmax = negmin = 0 ;
while ( ip != NULL ) {
next = ip->next ;
if ( ip->val > 0 ) {
ip->next = poshead, poshead = ip ;
if ( posmax < ip->val ) {
posmax = ip->val ;
}
} else if ( ip->val < 0 ) {
ip->next = neghead, neghead = ip ;
if ( negmin > ip->val ) {
negmin = ip->val ;
}
} else {
if ( zerohead == NULL ) {
zerotail = ip ;
}
ip->next = zerohead, zerohead = ip ;
}
ip = next ;
}
#if MYDEBUG > 0
fprintf(stdout, "\n positive list :") ;
IP_fp80(stdout, poshead, 16) ;
fprintf(stdout, "\n zero list :") ;
IP_fp80(stdout, zerohead, 16) ;
fprintf(stdout, "\n negative list :") ;
IP_fp80(stdout, neghead, 16) ;
fflush(stdout) ;
#endif
/*
---------------
find the limits
---------------
*/
dpos = 0 ;
while ( posmax > 0 ) {
dpos++ ;
posmax /= 10 ;
}
negmin = - negmin ;
dneg = 0 ;
while ( negmin > 0 ) {
dneg++ ;
negmin /= 10 ;
}
if ( dpos > dneg ) {
d = dpos ;
} else {
d = dneg ;
}
#if MYDEBUG > 0
fprintf(stdout, "\n dneg %d, dpos %d, d %d", dneg, dpos, d) ;
fflush(stdout) ;
#endif
/*
----------------------
sort the positive list
----------------------
*/
#if MYDEBUG > 0
fprintf(stdout, "\n sorting the positive list") ;
#endif
for ( i = 0 ; i < BASE ; i++ ) {
heads[i] = tails[i] = NULL ;
}
b1 = 1 ;
for ( i = 0 ; i < dpos ; i++ ) {
b2 = BASE * b1 ;
ip = poshead ; poshead = NULL ;
#if MYDEBUG > 0
fprintf(stdout, "\n b1 %d, b2 %d", b1, b2) ;
#endif
while ( ip != NULL ) {
next = ip->next ;
j = (ip->val % b2) / b1 ;
#if MYDEBUG > 0
fprintf(stdout, "\n ip->val %d, j %d", ip->val, j) ;
#endif
if ( heads[j] == NULL ) {
heads[j] = ip ;
} else {
tails[j]->next = ip ;
}
tails[j] = ip ;
ip = next ;
}
for ( j = 0 ; j < BASE ; j++ ) {
if ( heads[j] != NULL ) {
if ( poshead == NULL ) {
poshead = heads[j] ;
} else {
postail->next = heads[j] ;
}
postail = tails[j] ;
heads[j] = tails[j] = NULL ;
}
}
postail->next = NULL ;
b1 = b2 ;
}
#if MYDEBUG > 0
fprintf(stdout, "\n positive list") ;
IP_fprintf(stdout, poshead) ;
#endif
/*
----------------------
sort the negative list
----------------------
*/
#if MYDEBUG > 0
fprintf(stdout, "\n sorting the negative list") ;
#endif
b1 = 1 ;
for ( i = 0 ; i < dneg ; i++ ) {
b2 = BASE * b1 ;
#if MYDEBUG > 0
fprintf(stdout, "\n b1 %d, b2 %d", b1, b2) ;
#endif
ip = neghead ; neghead = NULL ;
while ( ip != NULL ) {
next = ip->next ;
j = ((-ip->val) % b2) / b1 ;
#if MYDEBUG > 0
fprintf(stdout, "\n ip->val %d, j %d", ip->val, j) ;
#endif
if ( heads[j] == NULL ) {
heads[j] = ip ;
} else {
tails[j]->next = ip ;
}
tails[j] = ip ;
ip = next ;
}
for ( j = 0 ; j < BASE ; j++ ) {
if ( heads[j] != NULL ) {
if ( neghead == NULL ) {
neghead = heads[j] ;
} else {
negtail->next = heads[j] ;
}
negtail = tails[j] ;
heads[j] = tails[j] = NULL ;
}
}
negtail->next = NULL ;
b1 = b2 ;
}
#if MYDEBUG > 0
fprintf(stdout, "\n negative list") ;
IP_fprintf(stdout, neghead) ;
#endif
/*
---------------------------
concatenate the three lists
---------------------------
*/
head = tail = ip = neghead ;
while ( ip != NULL ) {
next = ip->next ;
ip->next = head ;
head = ip ;
ip = next ;
}
if ( tail != NULL ) {
tail->next = NULL ;
}
#if MYDEBUG > 0
fprintf(stdout, "\n 1. head = %p, tail = %p", head, tail) ;
#endif
if ( zerohead != NULL ) {
if ( tail != NULL ) {
tail->next = zerohead ;
} else {
head = zerohead ;
}
tail = zerotail ;
}
if ( tail != NULL ) {
tail->next = NULL ;
}
#if MYDEBUG > 0
fprintf(stdout, "\n 2. head = %p, tail = %p", head, tail) ;
#endif
if ( poshead != NULL ) {
if ( tail != NULL ) {
tail->next = poshead ;
} else {
head = poshead ;
}
tail = postail ;
}
if ( tail != NULL ) {
tail->next = NULL ;
}
#if MYDEBUG > 0
fprintf(stdout, "\n 3. head = %p, tail = %p", head, tail) ;
IP_fprintf(stdout, head) ;
#endif
return(head) ; }
/*--------------------------------------------------------------------*/
/*
----------------------------------------------
purpose -- to sort a singly linked list in
descending order using a radix sort
created -- 95sep22, cca
----------------------------------------------
*/
IP *
IP_radixSortDown (
IP *ip
) {
IP *ip1 = NULL ;
if ( ip != NULL ) {
IP *ip0 ;
for ( ip0 = ip ; ip0 != NULL ; ip0 = ip0->next ) {
ip0->val = -ip0->val ;
}
ip1 = IP_radixSortUp(ip) ;
for ( ip0 = ip1 ; ip0 != NULL ; ip0 = ip0->next ) {
ip0->val = -ip0->val ;
}
}
return(ip1) ; }
/*--------------------------------------------------------------------*/
/*
-----------------------------------------------
sort a list in ascending order using merge sort
created -- 95sep22, cca
-----------------------------------------------
*/
IP *
IP_mergeSortUp (
IP *ip0
) {
int i, m, m1 ;
IP *ip, *ip1, *ip2, *prev ;
/*
----------------------------------------
count the number of elements in the list
----------------------------------------
*/
#if MYDEBUG > 0
fprintf(stdout, "\n inside IP_mergeSortUp :") ;
IP_fp80(stdout, ip0, 25) ;
fflush(stdout) ;
#endif
for ( ip = ip0, m = 0 ; ip != NULL ; ip = ip->next ) {
m++ ;
}
if ( m <= 1 ) {
return(ip0) ;
} else {
m1 = m / 2 ;
#if MYDEBUG > 0
fprintf(stdout, "\n m = %d, m1 = %d, m2 = %d", m, m1, m-m1) ;
fflush(stdout) ;
#endif
for ( i = 1, ip = ip0, prev = NULL ; i < m1 ; i++ ) {
prev = ip ;
ip = ip->next ;
}
ip2 = ip->next ;
ip->next = NULL ;
ip1 = ip0 ;
#if MYDEBUG > 0
fprintf(stdout, "\n calling IP_mergeSortUp :") ;
IP_fp80(stdout, ip1, 13) ;
fflush(stdout) ;
#endif
ip1 = IP_mergeSortUp(ip1) ;
#if MYDEBUG > 0
fprintf(stdout, "\n return from IP_mergeSortUp :") ;
IP_fp80(stdout, ip1, 13) ;
fprintf(stdout, "\n calling IPmergeSortUp :") ;
IP_fp80(stdout, ip2, 13) ;
#endif
ip2 = IP_mergeSortUp(ip2) ;
#if MYDEBUG > 0
fprintf(stdout, "\n return from IP_mergeSortUp :") ;
IP_fp80(stdout, ip2, 13) ;
fprintf(stdout, "\n calling IP_mergeUp :") ;
fprintf(stdout, "\n first list") ;
IP_fp80(stdout, ip1, 13) ;
fprintf(stdout, "\n second list") ;
IP_fp80(stdout, ip2, 13) ;
#endif
ip = IP_mergeUp(ip1, ip2) ;
#if MYDEBUG > 0
fprintf(stdout, "\n return from IP_mergeUp, sorted list : ") ;
IP_fp80(stdout, ip, 40) ;
fflush(stdout) ;
#endif
return(ip) ;
}
}
/*--------------------------------------------------------------------*/
syntax highlighted by Code2HTML, v. 0.9.1