From 73716275a699f7501e8a2933b85862172a84519d Mon Sep 17 00:00:00 2001 From: martinahansen Date: Wed, 10 Sep 2008 06:48:48 +0000 Subject: [PATCH] linked list sort added git-svn-id: http://biopieces.googlecode.com/svn/trunk@252 74ccb610-7750-0410-82ae-013aeee3265d --- code_c/Maasha/src/inc/list.h | 20 ++++++ code_c/Maasha/src/lib/list.c | 101 ++++++++++++++++++++++++++ code_c/Maasha/src/test/test_list.c | 110 +++++++++++++++++++++++++++++ 3 files changed, 231 insertions(+) diff --git a/code_c/Maasha/src/inc/list.h b/code_c/Maasha/src/inc/list.h index 297be01..5558575 100644 --- a/code_c/Maasha/src/inc/list.h +++ b/code_c/Maasha/src/inc/list.h @@ -70,6 +70,9 @@ void list_sl_print( list_sl *list_pt ); /* Debug funtion to print a singly linked list node. */ void node_sl_print( node_sl *node_pt ); +/* Sort a singly linked list according to the compare function. */ +void list_sl_sort( list_sl **list_ppt, int ( *compare )( const void *a, const void *b ) ); + /* Free memory for all nodes in and including the singly linked list. */ void list_sl_destroy( list_sl **list_ppt ); @@ -108,6 +111,23 @@ void node_dl_print( node_dl *node_pt ); void list_dl_destroy( list_dl **list_ppt ); +/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> GENERIC LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/ + + +/* Returns the number of nodes in a linked list. */ +size_t list_count( void *list_pt ); + + +/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ASSORTED SORTING FUNCTIOS <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/ + + +/* Sort in ascending order according to char node values. */ +int cmp_list_sl_char_asc( const void *a, const void *b ); + +/* Sort in descending order according to char node values. */ +int cmp_list_sl_char_desc( const void *a, const void *b ); + + /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/ diff --git a/code_c/Maasha/src/lib/list.c b/code_c/Maasha/src/lib/list.c index c42d538..93b91c8 100644 --- a/code_c/Maasha/src/lib/list.c +++ b/code_c/Maasha/src/lib/list.c @@ -123,6 +123,55 @@ void node_sl_print( node_sl *node_pt ) } +void list_sl_sort( list_sl **list_ppt, int ( *compare )( const void *a, const void *b ) ) +{ + /* Martin A. Hansen, September 2008 */ + + /* Sort a singly linked list according to the compare function. */ + + list_sl *list = *list_ppt; + node_sl **node_array = NULL; /* array of pointers to nodes */ + node_sl *node = NULL; + node_sl *old_node = NULL; + size_t count = 0; + size_t i = 0; + + count = list_count( list ); + + if ( count > 1 ) + { + node_array = mem_get( count * sizeof( *node_array ) ); + + for ( node = list->first, i = 0; node != NULL; node = node->next, i++ ) { + node_array[ i ] = node; + } + + qsort( node_array, count, sizeof( node_array[ 0 ] ), compare ); + + list->first = NULL; + + node = node_array[ 0 ]; + + list_sl_add_beg( &list, &node ); + + old_node = node; + + for ( i = 1; i < count; i++ ) + { + node = node_array[ i ]; + + list_sl_add_after( &old_node, &node ); + + old_node = node; + } + + *list_ppt = list; + + mem_free( &node_array ); + } +} + + void list_sl_destroy( list_sl **list_ppt ) { /* Martin A. Hansen, August 2008 */ @@ -346,4 +395,56 @@ void list_dl_destroy( list_dl **list_ppt ) } +/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> GENERIC LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/ + + +size_t list_count( void *list_pt ) +{ + /* Martin A. Hansen, September 2008 */ + + /* Returns the number of nodes in a linked list. */ + + list_sl *list = ( list_sl * ) list_pt; + node_sl *node = NULL; + size_t count = 0; + + for ( node = list->first; node != NULL; node = node->next ) { + count++; + } + + return count; +} + + +/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ASSORTED SORTING FUNCTIOS <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/ + + +int cmp_list_sl_char_asc( const void *a, const void *b ) +{ + /* Martin A. Hansen, September 2008 */ + + /* Compare function for use with list_sl_sort(). */ + /* Sort in ascending order according to char node values. */ + + node_sl *a_node = *( ( node_sl ** ) a ); + node_sl *b_node = *( ( node_sl ** ) b ); + + return strcmp( ( char * ) a_node->val, ( char * ) b_node->val ); +} + + +int cmp_list_sl_char_desc( const void *a, const void *b ) +{ + /* Martin A. Hansen, September 2008 */ + + /* Compare function for use with list_sl_sort(). */ + /* Sort in descending order according to char node values. */ + + node_sl *a_node = *( ( node_sl ** ) a ); + node_sl *b_node = *( ( node_sl ** ) b ); + + return strcmp( ( char * ) b_node->val, ( char * ) a_node->val ); +} + + /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/ diff --git a/code_c/Maasha/src/test/test_list.c b/code_c/Maasha/src/test/test_list.c index 19f33d1..d4e5551 100644 --- a/code_c/Maasha/src/test/test_list.c +++ b/code_c/Maasha/src/test/test_list.c @@ -10,6 +10,7 @@ static void test_list_sl_add_after(); static void test_list_sl_remove_beg(); static void test_list_sl_remove_after(); static void test_list_sl_print(); +static void test_list_sl_sort(); static void test_list_sl_destroy(); static void test_list_dl_new(); @@ -22,6 +23,8 @@ static void test_list_dl_remove(); static void test_list_dl_print(); static void test_list_dl_destroy(); +static void test_list_count(); + int main() { @@ -34,6 +37,7 @@ int main() test_list_sl_remove_beg(); test_list_sl_remove_after(); test_list_sl_print(); + test_list_sl_sort(); test_list_sl_destroy(); test_list_dl_new(); @@ -46,6 +50,8 @@ int main() test_list_dl_print(); test_list_dl_destroy(); + test_list_count(); + fprintf( stderr, "Done\n\n" ); return EXIT_SUCCESS; @@ -280,6 +286,52 @@ void test_list_sl_print() } +void test_list_sl_sort() +{ + fprintf( stderr, " Testing list_sl_sort ... " ); + + /* Sorting a char list */ + + char *array[3] = { "test1", "test2", "test3" }; + list_sl *list = NULL; + node_sl *node = NULL; + int i = 0; + + list = list_sl_new(); + + for ( i = 0; i < 3; i++ ) + { + node = node_sl_new(); + + node->val = array[ i ]; + + list_sl_add_beg( &list, &node ); + } + + list_sl_sort( &list, cmp_list_sl_char_asc ); + list_sl_sort( &list, cmp_list_sl_char_desc ); + +// /* Sorting a int list */ +// +// int int_array[ 5 ] = { 345, 23, 23, 1, 400 }; +// list_sl *int_list = NULL; +// node_sl *int_node = NULL; +// +// int_list = list_sl_new(); +// +// for ( i = 0; i < 5; i++ ) +// { +// printf( "int: %d\n", int_array[ i ] ); +// +// int_node = node_sl_new(); +// +// node->val = int_array[ i ]; +// } + + fprintf( stderr, "OK\n" ); +} + + void test_list_sl_destroy() { fprintf( stderr, " Testing list_sl_destroy ... " ); @@ -549,6 +601,64 @@ void test_list_dl_destroy() } +/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> GENERIC LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */ + + +void test_list_count() +{ + fprintf( stderr, " Testing list_count ... " ); + + /* Singly linked list. */ + + char *array[3] = { "test1", "test2", "test3" }; + list_sl *sllist = NULL; + node_sl *node = NULL; + node_sl *new_node = NULL; + int i = 0; + + sllist = list_sl_new(); + new_node = node_sl_new(); + + new_node->val = array[ 0 ]; + + list_sl_add_beg( &sllist, &new_node ); + + node = new_node; + + for ( i = 1; i < 3; i++ ) + { + new_node = node_sl_new(); + + new_node->val = array[ i ]; + + list_sl_add_after( &node, &new_node ); + + node = new_node; + } + + assert( list_count( sllist ) == 3 ); + + /* Doubly linked list. */ + + list_dl *dllist = list_dl_new(); + node_dl *node1 = node_dl_new(); + node_dl *node2 = node_dl_new(); + node_dl *node3 = node_dl_new(); + + node1->val = "TEST1"; + node2->val = "TEST2"; + node3->val = "TEST3"; + + list_dl_add_beg( &dllist, &node1 ); + list_dl_add_beg( &dllist, &node2 ); + list_dl_add_beg( &dllist, &node3 ); + + assert( list_count( dllist ) == 3 ); + + fprintf( stderr, "OK\n" ); +} + + /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */ -- 2.39.5