linked list sort added

git-svn-id: http://biopieces.googlecode.com/svn/trunk@252 74ccb610-7750-0410-82ae-013aeee3265d

diff --git a/code_c/Maasha/src/inc/list.h b/code_c/Maasha/src/inc/list.h
index 297be014a3282d7d1f6df06cebb8e727c6fb7ed5..55585754754fa1c220f41863b2c4fbf2af756116 100644 (file)
--- 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 c42d5381648ac88f914ab9545ad792ac3d56879c..93b91c81c6539f5dde42b22446b31e15c7184f65 100644 (file)
--- 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 19f33d1c199f22c932b1efbc84a3d33daa08dee9..d4e55510164ee6fcba3e58e32f2a031ce1a76b0e 100644 (file)
--- 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" );
+}
+
+
 /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */