INC = -I $(INC_DIR)
LIB = -lm $(LIB_DIR)*.o
-all: libs utest bipartite_scan fasta_count repeat-O-matic tetra_count
+all: libs utest bipartite_scan fasta_count repeat-O-matic
libs:
cd $(LIB_DIR) && ${MAKE} all
repeat-O-matic: repeat-O-matic.c
$(CC) $(Cflags) $(INC) $(LIB) repeat-O-matic.c -o repeat-O-matic
-tetra_count: tetra_count.c
- $(CC) $(Cflags) $(INC) $(LIB) tetra_count.c -o tetra_count
-
clean:
cd $(LIB_DIR) && ${MAKE} clean
cd $(TEST_DIR) && ${MAKE} clean
rm bipartite_scan
rm fasta_count
rm repeat-O-matic
- rm tetra_count
#include "common.h"
#include "mem.h"
+#include "filesys.h"
+#include "seq.h"
+#include "fasta.h"
#include "list.h"
-#define BLOCK_SIZE_BITS 8 /* one block holds 8 bits */
-#define BLOCK_SIZE_NT 4 /* one block holds 4 nucleotides */
-#define BITS_IN_NT 2 /* two bits holds 1 nucleotide */
+#define BLOCK_SIZE_NT 4 /* one block holds 4 nucleotides. */
+#define BITS_IN_NT 2 /* two bits holds 1 nucleotide. */
+#define BITS_IN_BYTE 8 /* number of bits in one byte. */
+#define BLOCK_SPACE_MAX 256 /* maximum space between two blocks. */
+// #define COUNT_ARRAY_SIZE ( 1 << 30 ) /* size of the unsigned int count array. */
+#define COUNT_ARRAY_SIZE ( 1 << 5 ) /* size of the unsigned int count array. */
-#define add_A( c ) /* add 00 to the rightmost two bits of bin (i.e. do nothing). */
-#define add_T( c ) ( c |= 3 ) /* add 11 on the rightmost two bits of c. */
-#define add_C( c ) ( c |= 1 ) /* add 01 on the rightmost two bits of c. */
-#define add_G( c ) ( c |= 2 ) /* add 10 on the rightmost two bits of c. */
+#define add_A( c ) /* add 00 to the rightmost two bits of bin (i.e. do nothing). */
+#define add_T( c ) ( c |= 3 ) /* add 11 on the rightmost two bits of c. */
+#define add_C( c ) ( c |= 1 ) /* add 01 on the rightmost two bits of c. */
+#define add_G( c ) ( c |= 2 ) /* add 10 on the rightmost two bits of c. */
-typedef unsigned char block;
+struct _bitblock
+{
+ uchar bin;
+ bool hasN;
+};
+
+typedef struct _bitblock bitblock;
-char *block2dna[256] = {
+char *bin2dna[256] = {
"AAAA", "AAAC", "AAAG", "AAAT", "AACA", "AACC", "AACG", "AACT",
"AAGA", "AAGC", "AAGG", "AAGT", "AATA", "AATC", "AATG", "AATT",
"ACAA", "ACAC", "ACAG", "ACAT", "ACCA", "ACCC", "ACCG", "ACCT",
"TTGA", "TTGC", "TTGG", "TTGT", "TTTA", "TTTC", "TTTG", "TTTT"
};
-bool block_fill( char *seq, size_t offset, block *new_block );
-void block_print( list_sl *list );
-void scan_seq( char *seq, size_t seq_len );
+void run_scan( int argc, char *argv[] );
+void print_usage();
+void scan_file( char *file, seq_entry *entry, uint *count_array );
+void scan_seq( char *seq, size_t seq_len, uint *count_array );
+void scan_list( list_sl *list, uint *count_array );
+bitblock *bitblock_new();
+void bitblock_print( bitblock *out );
+void bitblock_list_print( list_sl *list );
+uint blocks2motif( uchar bin1, uchar bin2, short dist );
+void count_array_print( uint *count_array );
+void motif_print( uint motif, uint count );
static void run_tests();
-static void test_block_fill();
+static void test_bitblock_new();
+static void test_bitblock_print();
+static void test_bitblock_list_print();
static void test_scan_seq();
+static void test_blocks2motif();
-int main()
+int main( int argc, char *argv[] )
{
+ if ( argc == 1 ) {
+ print_usage();
+ }
+
run_tests();
+ run_scan( argc, argv );
return EXIT_SUCCESS;
}
-bool block_fill( char *seq, size_t offset, block *new_block_pt )
+void print_usage()
{
- /* Martin A. Hansen, September 2008. */
+ fprintf( stderr,
+ "Usage: bipartite_scam <FASTA file(s)> > result.csv\n"
+ );
+
+ exit( EXIT_SUCCESS );
+}
+
+
+void run_scan( int argc, char *argv[] )
+{
+ /* Martin A. Hansen, September 2008 */
+
+ /* Scan a stack of files. */
+
+ char *file = NULL;
+ int i = 0;
+ seq_entry *entry = NULL;
+ uint *count_array = NULL;
+
+ count_array = mem_get_zero( COUNT_ARRAY_SIZE );
+
+ entry = seq_new( MAX_SEQ_NAME, MAX_SEQ );
+
+ for ( i = 1; i < argc; i++ )
+ {
+ file = argv[ i ];
+
+ fprintf( stderr, "Scanning file: %s\n", file );
+
+ scan_file( file, entry, count_array );
+
+ fprintf( stderr, "done.\n" );
+ }
+
+ fprintf( stderr, "Printing motifs: ... " );
+
+ count_array_print( count_array );
+
+ fprintf( stderr, "done.\n" );
+
+ seq_destroy( entry );
+
+ mem_free( &count_array );
+}
- /* Fills a block with sequence (converted to bits) from */
- /* a given offset. If the sequence contains non-DNA residues */
- /* the function returns FALSE. */
+
+void scan_file( char *file, seq_entry *entry, uint *count_array )
+{
+ /* Martin A. Hansen, September 2008 */
- block new_block = *new_block_pt;
- int i = 0;
+ /* Scan all entries of a file in both */
+ /* sense and anti-sense directions .*/
- for ( i = 0; i < BLOCK_SIZE_NT; i++ )
+ FILE *fp = read_open( file );
+
+ while ( fasta_get_entry( fp, &entry ) == TRUE )
{
- new_block <<= BITS_IN_NT;
+ fprintf( stderr, " + Scanning: %s ... ", entry->seq_name );
+
+ scan_seq( entry->seq, entry->seq_len, count_array );
- switch( seq[ offset + i ] )
- {
- case 'A': case 'a': add_A( new_block ); break;
- case 'T': case 't': add_T( new_block ); break;
- case 'C': case 'c': add_C( new_block ); break;
- case 'G': case 'g': add_G( new_block ); break;
- default: return FALSE;
- }
+ fprintf( stderr, "done.\n" );
+
+ revcomp_dna( entry->seq );
+
+ fprintf( stderr, " - Scanning: %s ... ", entry->seq_name );
+
+ scan_seq( entry->seq, entry->seq_len, count_array );
+
+ fprintf( stderr, "done.\n" );
}
- *new_block_pt = new_block;
+ close_stream( fp );
+}
+
+
+bitblock *bitblock_new()
+{
+ /* Martin A. Hansen, September 2008 */
+
+ /* Initializes a new block. */
+
+ bitblock *new_block = NULL;
+
+ new_block = mem_get( sizeof( bitblock ) );
- return TRUE;
+ new_block->bin = 0;
+ new_block->hasN = FALSE;
+
+ return new_block;
}
-void scan_seq( char *seq, size_t seq_len )
+void bitblock_print( bitblock *out )
{
- /* Martin A. Hansen, September 2008. */
+ /* Martin A. Hansen, September 2008 */
+
+ /* Debug function to print a given block. */
+
+ printf( "bin: %d dna: %s hasN: %d\n", out->bin, bin2dna[ ( int ) out->bin ], out->hasN );
+}
- block b = 0;
- short b_count = 0;
- size_t i = 0;
- list_sl *list = NULL;
- node_sl *node_new = NULL;
- node_sl *node_old = NULL;
- bool first_node = TRUE;
- list_sl_new( &list );
+void bitblock_list_print( list_sl *list )
+{
+ /* Martin A. Hansen, September 2008 */
+
+ /* Debug function to print all blocks in a list. */
- node_new = mem_get( sizeof( node_sl ) );
- node_old = mem_get( sizeof( node_sl ) );
+ node_sl *node = NULL;
- while ( i < seq_len - BLOCK_SIZE_NT + 1 )
+ for ( node = list->first; node != NULL; node = node->next ) {
+ bitblock_print( ( bitblock * ) node->val );
+ }
+}
+
+
+void scan_seq( char *seq, size_t seq_len, uint *count_array )
+{
+ /* Martin A. Hansen, September 2008 */
+
+ bitblock *block = NULL;
+ short b_count = 0;
+ short n_count = 0;
+ size_t i = 0;
+ uchar bin = 0;
+ bool first_node = TRUE;
+ node_sl *new_node = NULL;
+ node_sl *old_node = NULL;
+ list_sl *list = list_sl_new();
+
+ for ( i = 0; seq[ i ]; i++ )
{
- b <<= BITS_IN_NT;
+ bin <<= BITS_IN_NT;
switch( seq[ i ] )
{
- case 'A': case 'a': add_A( b ); b_count++; break;
- case 'T': case 't': add_T( b ); b_count++; break;
- case 'C': case 'c': add_C( b ); b_count++; break;
- case 'G': case 'g': add_G( b ); b_count++; break;
- default: b = 0; b_count = 0; break;
+ case 'A': case 'a': add_A( bin ); break;
+ case 'T': case 't': add_T( bin ); break;
+ case 'C': case 'c': add_C( bin ); break;
+ case 'G': case 'g': add_G( bin ); break;
+ default: n_count = BLOCK_SIZE_NT; break;
}
- if ( b_count >= BLOCK_SIZE_NT )
+ if ( i > BLOCK_SIZE_NT - 2 )
{
- node_new->val = "FISK";
+ b_count++;
+
+ block = bitblock_new();
+ block->bin = bin;
- if ( first_node )
+ if ( n_count > 0 )
{
- list_sl_add_beg( &list, &node_new );
+ block->hasN = TRUE;
+ n_count--;
}
- else
- {
- list_sl_add_after( &node_old, &node_new );
+
+ new_node = node_sl_new();
+ new_node->val = block;
+
+ if ( first_node ) {
+ list_sl_add_beg( &list, &new_node );
+ } else {
+ list_sl_add_after( &old_node, &new_node );
}
- node_old = node_new;
+ old_node = new_node;
first_node = FALSE;
+
+ if ( b_count > BLOCK_SPACE_MAX + BLOCK_SIZE_NT )
+ {
+ // bitblock_list_print( list );
+
+ scan_list( list, count_array );
+
+ list_sl_remove_beg( &list );
+ }
}
+ }
+
+ list_sl_destroy( &list );
+}
+
- i++;
+void scan_list( list_sl *list, uint *count_array )
+{
+ /* Martin A. Hansen, September 2008 */
+
+ node_sl *first_node = NULL;
+ node_sl *next_node = NULL;
+ bitblock *block1 = NULL;
+ bitblock *block2 = NULL;
+ int i = 0;
+ short dist = 0;
+ uint motif_bin = 0;
+
+// bitblock_list_print( list );
+
+ first_node = list->first;
+
+ block1 = ( bitblock * ) first_node->val;
+
+ if ( ! block1->hasN )
+ {
+ next_node = first_node->next;
+
+ for ( i = 0; i < BLOCK_SIZE_NT - 1; i++ ) {
+ next_node = next_node->next;
+ }
+
+ for ( next_node = next_node; next_node != NULL; next_node = next_node->next )
+ {
+ block2 = ( bitblock * ) next_node->val;
+
+// printf( "block1: %s block2: %s dist: %d\n", bin2dna[ block1->bin ], bin2dna[ block2->bin ], dist );
+
+ if ( ! block2->hasN )
+ {
+ motif_bin = blocks2motif( block1->bin, block2->bin, dist );
+
+ // motif_print( motif_bin );
+
+ count_array[ motif_bin ]++;
+ }
+
+ dist++;
+ }
}
+}
- block_print( list );
- list_sl_destroy( &list );
+uint blocks2motif( uchar bin1, uchar bin2, short dist )
+{
+ /* Martin A. Hansen, September 2008 */
+
+ uint motif = 0;
+
+ motif |= bin1;
+
+ motif <<= sizeof( uchar ) * BITS_IN_BYTE;
+
+ motif |= bin2;
+
+ motif <<= sizeof( short ) * BITS_IN_BYTE;
+
+ motif |= dist;
+
+ return motif;
}
-void block_print( list_sl *list )
+void count_array_print( uint *count_array )
{
- node_sl *node = list->first;
+ /* Martin A. Hansen, Seqptember 2008. */
+
+ /* Print all motifs in count_array as */
+ /* tabular output. */
- while ( node != NULL )
+ uint i = 0;
+ uint motif = 0;
+ uint count = 0;
+
+ for ( i = 0; i < COUNT_ARRAY_SIZE; i++ )
{
- printf( "BLOCK: %s\n", ( char * ) node->val );
-
- node = node->next;
+ motif = i;
+ count = count_array[ i ];
+
+ motif_print( motif, count );
}
}
+void motif_print( uint motif, uint count )
+{
+ /* Martin A. Hansen, September 2008 */
+
+ uchar bin1 = 0;
+ uchar bin2 = 0;
+ short dist = 0;
+
+ dist = ( short ) motif;
+
+ motif >>= sizeof( short ) * BITS_IN_BYTE;
+
+ bin2 = ( uchar ) motif;
+
+ motif >>= sizeof( uchar ) * BITS_IN_BYTE;
+
+ bin1 = ( uchar ) motif;
+
+ printf( "%s\t%s\t%d\t%d\n", bin2dna[ bin1 ], bin2dna[ bin2 ], dist, count );
+}
+
+
/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> UNIT TESTS <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */
{
printf( "Running tests\n" );
- test_block_fill();
+ test_bitblock_new();
+ test_bitblock_print();
+ test_bitblock_list_print();
test_scan_seq();
+ test_blocks2motif();
printf( "All tests OK\n" );
}
-void test_block_fill()
+void test_bitblock_new()
{
- printf( " Running test_block_fill ... " );
+ printf( " Running test_bitblock_new ... " );
- char *seq = "AAAATCGGCTA";
- size_t seq_len = strlen( seq );
- size_t offset = 0;
- block new_block = 0;
+ bitblock *new_block = bitblock_new();
- for ( offset = 0; offset < seq_len - BLOCK_SIZE_NT + 1; offset++ )
- {
- assert( ( block_fill( seq, offset, &new_block ) == TRUE ) );
+ assert( new_block->bin == 0 );
+ assert( new_block->hasN == FALSE );
-// printf( "BLOCK: %s\n", block2dna[ new_block ] );
- }
+ printf( "done.\n");
+}
+
+
+void test_bitblock_print()
+{
+ printf( " Running test_bitblock_print ... " );
+
+ bitblock *new_block = bitblock_new();
+
+ new_block->bin = 7;
+ new_block->hasN = TRUE;
+
+// bitblock_print( new_block );
printf( "done.\n");
}
+void test_bitblock_list_print()
+{
+ printf( " Running test_bitblock_list_print ... " );
+
+ list_sl *list = list_sl_new();
+ node_sl *node1 = node_sl_new();
+ node_sl *node2 = node_sl_new();
+ node_sl *node3 = node_sl_new();
+ bitblock *block1 = bitblock_new();
+ bitblock *block2 = bitblock_new();
+ bitblock *block3 = bitblock_new();
+
+ block1->bin = 0;
+ block1->hasN = TRUE;
+ block2->bin = 1;
+ block2->hasN = TRUE;
+ block3->bin = 2;
+ block3->hasN = TRUE;
+
+ node1->val = block1;
+ node2->val = block2;
+ node3->val = block3;
+
+ list_sl_add_beg( &list, &node1 );
+ list_sl_add_beg( &list, &node2 );
+ list_sl_add_beg( &list, &node3 );
+
+ // bitblock_list_print( list );
+
+ printf( "done.\n" );
+}
+
+
void test_scan_seq()
{
printf( " Running test_scan_seq ... " );
- char *seq = "AAAATCGGCTA";
- size_t seq_len = strlen( seq );
+ //char *seq = "AAAANTCGGCTNGGGG";
+ char *seq = "AAAATCGGCTGGGG";
+ size_t seq_len = strlen( seq );
+ uint *count_array = mem_get_zero( sizeof( uint ) * ( 1 << 5 ) );
+
+ scan_seq( seq, seq_len, count_array );
+
+ printf( "done.\n");
+}
+
+
+static void test_blocks2motif()
+{
+ printf( " Running test_blocks2motif ... " );
+
+ uchar bin1 = 4;
+ uchar bin2 = 3;
+ short dist = 256;
+ uint motif = 0;
+
+ motif = blocks2motif( bin1, bin2, dist );
- scan_seq( seq, seq_len );
+// printf( "motif: %d\n", motif );
printf( "done.\n");
}
#include <assert.h>
#include <errno.h>
+typedef unsigned char uchar;
typedef char bool;
#define TRUE 1
/* Initialize a new singly linked list. */
-void list_sl_new( list_sl **list_ppt );
+list_sl *list_sl_new();
+
+/* Initialize a new singly linked list node. */
+node_sl *node_sl_new();
/* Add a new node to the beginning of a singly linked list. */
-void list_sl_add_beg( list_sl **list_ppt, node_sl **node_ppt );
+void list_sl_add_beg( list_sl **list_ppt, node_sl **node_ppt );
/* Add a new node after a given node of a singly linked list. */
-void list_sl_add_after( node_sl **node_ppt, node_sl **new_node_ppt );
+void list_sl_add_after( node_sl **node_ppt, node_sl **new_node_ppt );
/* Remove the first node of a singly linked list. */
-void list_sl_remove_beg( list_sl **list_ppt );
+void list_sl_remove_beg( list_sl **list_ppt );
/* Remove the node next to this one in a singly linked list. */
-void list_sl_remove_after( node_sl **node_ppt );
+void list_sl_remove_after( node_sl **node_ppt );
/* Debug function to print all elements from a singly linked list. */
-void list_sl_print( list_sl *list_pt );
+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 );
/* Free memory for all nodes in and including the singly linked list. */
-void list_sl_destroy( list_sl **list_ppt );
+void list_sl_destroy( list_sl **list_ppt );
/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> DOUBLY LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
/* Initialize a new doubly linked list. */
-void list_dl_new( list_dl **list_ppt );
+list_dl *list_dl_new();
+
+/* Initialize a new doubly linked list node. */
+node_dl *node_dl_new();
/* Add a new node to the beginning of a doubly linked list. */
-void list_dl_add_beg( list_dl **list_ppt, node_dl **node_ppt );
+void list_dl_add_beg( list_dl **list_ppt, node_dl **node_ppt );
/* Add a new node to the end of a doubly linked list. */
-void list_dl_add_end( list_dl **list_ppt, node_dl **node_ppt );
+void list_dl_add_end( list_dl **list_ppt, node_dl **node_ppt );
/* Add a new node before a given node of a doubly linked list. */
-void list_dl_add_before( list_dl **list_ppt, node_dl **node_ppt, node_dl **new_node_ppt );
+void list_dl_add_before( list_dl **list_ppt, node_dl **node_ppt, node_dl **new_node_ppt );
/* Add a new node after a given node of a doubly linked list. */
-void list_dl_add_after( list_dl **list_ppt, node_dl **node_ppt, node_dl **new_node_ppt );
+void list_dl_add_after( list_dl **list_ppt, node_dl **node_ppt, node_dl **new_node_ppt );
/* Remove a node from a doubly linked list. */
-void list_dl_remove( list_dl **list_ppt, node_dl **node_ppt );
+void list_dl_remove( list_dl **list_ppt, node_dl **node_ppt );
/* Debug function to print all elements from a doubly linked list. */
-void list_dl_print( list_dl *list_pt );
+void list_dl_print( list_dl *list_pt );
+
+/* Debug funtion to print a doubly linked list node. */
+void node_dl_print( node_dl *node_pt );
/* Free memory for all nodes in and including the doubly linked list. */
-void list_dl_destroy( list_dl **list_ppt );
+void list_dl_destroy( list_dl **list_ppt );
/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
typedef struct _seq_entry seq_entry;
/* Initialize a new sequence entry. */
-void seq_new( seq_entry **entry_ppt, size_t max_seq_name, size_t max_seq );
+seq_entry *seq_new( size_t max_seq_name, size_t max_seq );
/* Destroy a sequence entry. */
-void seq_destroy( seq_entry *entry );
+void seq_destroy( seq_entry *entry );
/* Uppercase sequence. */
-void seq_uppercase( char *seq );
+void seq_uppercase( char *seq );
/* Lowercase sequence. */
-void lowercase_seq( char *seq );
+void lowercase_seq( char *seq );
/* Reverse compliments DNA sequence. */
-void revcomp_dna( char *seq );
+void revcomp_dna( char *seq );
/* Reverse compliments RNA sequence. */
-void revcomp_rna( char *seq );
+void revcomp_rna( char *seq );
/* Reverse compliment nucleotide sequnce after guessing the sequence type. */
-void revcomp_nuc( char *seq );
+void revcomp_nuc( char *seq );
/* Complement DNA sequence. (NB it is not reversed!). */
-void complement_dna( char *seq );
+void complement_dna( char *seq );
/* Complement RNA sequence. (NB it is not reversed!). */
-void complement_rna( char *seq );
+void complement_rna( char *seq );
/* Complement nucleotide sequence after guessing the sequence type. */
-void complement_nuc( char *seq );
+void complement_nuc( char *seq );
/* Reverse sequence. */
-void reverse( char *seq );
+void reverse( char *seq );
/* Convert all non-nucleotide letters to Ns. */
-void seq2nuc_simple( char *seq );
+void seq2nuc_simple( char *seq );
/* Convert DNA into RNA by change t and T to u and U, respectively. */
-void dna2rna( char *seq );
+void dna2rna( char *seq );
/* Convert RNA into DNA by change u and U to t and T, respectively. */
-void rna2dna( char *seq );
+void rna2dna( char *seq );
/* Check if a sequence is DNA by inspecting the first 100 residues. */
-bool is_dna( char *seq );
+bool is_dna( char *seq );
/* Check if a sequence is RNA by inspecting the first 100 residues. */
-bool is_rna( char *seq );
+bool is_rna( char *seq );
/* Check if a sequence is protein by inspecting the first 100 residues. */
-bool is_protein( char *seq );
+bool is_protein( char *seq );
/* Guess if a sequence is DNA, RNA, or protein by inspecting the first 100 residues. */
-char *seq_guess_type( char *seq );
+char *seq_guess_type( char *seq );
/* Check if a sequence contain N or n. */
-bool contain_N( char *seq );
+bool contain_N( char *seq );
/* Pack a nucleotide oligo (max length 15) into a binary/integer (good for hash keys). */
-int oligo2bin( char *oligo );
+int oligo2bin( char *oligo );
/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> SINGLY LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
-void list_sl_new( list_sl **list_ppt )
+list_sl *list_sl_new()
{
/* Martin A. Hansen, August 2008 */
/* Initialize a new singly linked list. */
- list_sl *new = NULL;
+ list_sl *new_list = NULL;
- new = mem_get( sizeof( list_sl ) );
+ new_list = mem_get( sizeof( list_sl ) );
- new->first = NULL;
+ new_list->first = NULL;
- *list_ppt = new;
+ return new_list;
+}
+
+
+node_sl *node_sl_new()
+{
+ /* Martin A. Hansen, September 2008 */
+
+ /* Initialize a new singly linked list node. */
+
+ node_sl *new_node = NULL;
+
+ new_node = mem_get( sizeof( node_sl ) );
+
+ new_node->next = NULL;
+ new_node->val = NULL;
+
+ return new_node;
}
/* Debug function to print all elements from a singly linked list. */
- node_sl *node = list_pt->first;
- int i = 0;
+ node_sl *node = NULL;
- while ( node != NULL )
- {
- printf( "Node: %d val: %s\n", i, ( char * ) node->val );
+ for ( node = list_pt->first; node != NULL; node = node->next ) {
+ node_sl_print( node );
+ }
+}
- node = node->next;
- i++;
- }
+void node_sl_print( node_sl *node_pt )
+{
+ /* Martin A. Hansen, September 2008 */
+
+ /* Debug funtion to print a singly linked list node. */
+
+ printf( "node_sl->val: %s\n", ( char * ) node_pt->val );
}
/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> DOUBLY LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<*/
-void list_dl_new( list_dl **list_ppt )
+list_dl *list_dl_new()
{
/* Martin A. Hansen, August 2008 */
/* Initialize a new doubly linked list. */
- list_dl *new = NULL;
+ list_dl *new_list = NULL;
- new = mem_get( sizeof( list_dl ) );
+ new_list = mem_get( sizeof( list_dl ) );
- new->first = NULL;
- new->last = NULL;
+ new_list->first = NULL;
+ new_list->last = NULL;
- *list_ppt = new;
+ return new_list;
+}
+
+
+node_dl *node_dl_new()
+{
+ /* Martin A. Hansen, September 2008 */
+
+ /* Initialize a new doubly linked list node. */
+
+ node_dl *new_node = NULL;
+
+ new_node = mem_get( sizeof( node_dl ) );
+
+ new_node->next = NULL;
+ new_node->prev = NULL;
+ new_node->val = NULL;
+
+ return new_node;
}
/* Debug function to print all elements from a doubly linked list. */
- node_dl *node = list_pt->first;
- int i = 0;
+ node_dl *node = NULL;
- while ( node != NULL )
- {
- printf( "Node: %d val: %s\n", i, ( char * ) node->val );
+ for ( node = list_pt->first; node != NULL; node = node->next ) {
+ node_dl_print( node );
+ }
+}
- node = node->next;
- i++;
- }
+void node_dl_print( node_dl *node_pt )
+{
+ /* Martin A. Hansen, September 2008 */
+
+ /* Debug funtion to print a doubly linked list node. */
+
+ printf( "node_dl->val: %s\n", ( char * ) node_pt->val );
}
#include "seq.h"
-void seq_new( seq_entry **entry_ppt, size_t max_seq_name, size_t max_seq )
+seq_entry *seq_new( size_t max_seq_name, size_t max_seq )
{
/* Martin A. Hansen, August 2008 */
/* Initialize a new sequence entry. */
- seq_entry *entry = *entry_ppt;
+ seq_entry *entry = NULL;
entry = mem_get( sizeof( seq_entry ) );
entry->seq_name = mem_get( max_seq_name );
entry->seq = mem_get( max_seq );
entry->seq_len = 0;
- *entry_ppt = entry;
+
+ return entry;
}
fp = read_open( path );
- seq_new( &entry, MAX_SEQ_NAME, MAX_SEQ );
+ entry = seq_new( MAX_SEQ_NAME, MAX_SEQ );
while ( ( fasta_get_entry( fp, &entry ) ) != 0 )
{
seq_entry *entry;
FILE *fp;
- seq_new( &entry, MAX_SEQ_NAME, MAX_SEQ );
+ entry = seq_new( MAX_SEQ_NAME, MAX_SEQ );
fp = read_open( path );
fp = read_open( TEST_FILE1 );
- seq_new( &entry, max_seq_name, max_seq );
+ entry = seq_new( max_seq_name, max_seq );
while ( ( fasta_get_entry( fp, &entry ) != FALSE ) ) {
// printf( "seq_name: %s seq_len: %zu\n", entry->seq_name, entry->seq_len );
fp = read_open( TEST_FILE1 );
- seq_new( &entry, max_seq_name, max_seq );
+ entry = seq_new( max_seq_name, max_seq );
while ( ( fasta_get_entry( fp, &entry ) != FALSE ) ) {
// fasta_put_entry( entry );
#include "mem.h"
#include "list.h"
+
static void test_list_sl_new();
+static void test_node_sl_new();
static void test_list_sl_add_beg();
static void test_list_sl_add_after();
static void test_list_sl_remove_beg();
static void test_list_sl_destroy();
static void test_list_dl_new();
+static void test_node_dl_new();
static void test_list_dl_add_beg();
static void test_list_dl_add_end();
static void test_list_dl_add_before();
static void test_list_dl_print();
static void test_list_dl_destroy();
+
int main()
{
fprintf( stderr, "Running all tests for list.c\n" );
test_list_sl_new();
+ test_node_sl_new();
test_list_sl_add_beg();
test_list_sl_add_after();
test_list_sl_remove_beg();
test_list_sl_destroy();
test_list_dl_new();
+ test_node_dl_new();
test_list_dl_add_beg();
test_list_dl_add_end();
test_list_dl_add_before();
}
+/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> SINGLY LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */
+
+
void test_list_sl_new()
{
fprintf( stderr, " Testing list_sl_new ... " );
list_sl *list = NULL;
- list_sl_new( &list );
+ list = list_sl_new();
+ assert( list != NULL );
assert( list->first == NULL );
fprintf( stderr, "OK\n" );
}
-void test_list_sl_add_beg()
+void test_node_sl_new()
{
- fprintf( stderr, " Testing list_sl_add_beg ... " );
-
- list_sl *list = NULL;
- node_sl *node1 = NULL;
- node_sl *node2 = NULL;
- node_sl *node3 = NULL;
+ fprintf( stderr, " Testing node_sl_new ... " );
- list_sl_new( &list );
+ node_sl *node = NULL;
- node1 = mem_get( sizeof( node_sl ) );
- node2 = mem_get( sizeof( node_sl ) );
- node3 = mem_get( sizeof( node_sl ) );
+ node = node_sl_new();
- node1->val = "TEST1";
- node2->val = "TEST2";
- node3->val = "TEST3";
+ assert( node != NULL );
+ assert( node->next == NULL );
+ assert( node->val == NULL );
- node1->next = NULL;
- node2->next = NULL;
- node3->next = NULL;
+ fprintf( stderr, "OK\n" );
+}
- assert( list->first == NULL );
- list_sl_add_beg( &list, &node1 );
- assert( list->first == node1 );
- assert( strcmp( list->first->val, "TEST1" ) == 0 );
+void test_list_sl_add_beg()
+{
+ fprintf( stderr, " Testing list_sl_add_beg ... " );
- list_sl_add_beg( &list, &node2 );
- assert( list->first == node2 );
- assert( strcmp( list->first->val, "TEST2" ) == 0 );
+ char *array[3] = { "test1", "test2", "test3" };
+ list_sl *list = NULL;
+ node_sl *node = NULL;
+ int i = 0;
- list_sl_add_beg( &list, &node3 );
- assert( list->first == node3 );
- assert( strcmp( list->first->val, "TEST3" ) == 0 );
+ list = list_sl_new();
- node2->val = "FOP";
+ for ( i = 0; i < 3; i++ )
+ {
+ node = node_sl_new();
- list_sl_print( list );
+ node->val = array[ i ];
- node1->val = "TEST4";
- node1->next = NULL;
+ list_sl_add_beg( &list, &node );
+ }
- list_sl_add_beg( &list, &node1 );
- assert( list->first == node1 );
- assert( strcmp( list->first->val, "TEST4" ) == 0 );
+ i = 2;
- node1->next = NULL;
+ for ( node = list->first; node != NULL; node = node->next )
+ {
+ assert( strcmp( array[ i ], ( char * ) node->val ) == 0 );
- list_sl_print( list );
+ i--;
+ }
fprintf( stderr, "OK\n" );
}
{
fprintf( stderr, " Testing list_sl_add_after ... " );
- list_sl *list = NULL;
- node_sl *node1 = NULL;
- node_sl *node2 = NULL;
+ char *array[3] = { "test1", "test2", "test3" };
+ list_sl *list = NULL;
+ node_sl *node = NULL;
+ node_sl *new_node = NULL;
+ int i = 0;
- list_sl_new( &list );
+ list = list_sl_new();
+ new_node = node_sl_new();
- node1 = mem_get( sizeof( node_sl ) );
- node2 = mem_get( sizeof( node_sl ) );
+ new_node->val = array[ 0 ];
- node1->val = "TEST1";
- node2->val = "TEST2";
+ list_sl_add_beg( &list, &new_node );
- assert( list->first == NULL );
+ node = new_node;
- list_sl_add_beg( &list, &node1 );
- assert( list->first == node1 );
- assert( strcmp( list->first->val, "TEST1" ) == 0 );
+ for ( i = 1; i < 3; i++ )
+ {
+ new_node = node_sl_new();
- list_sl_add_after( &node1, &node2 );
- assert( list->first == node1 );
- assert( strcmp( list->first->val, "TEST1" ) == 0 );
+ new_node->val = array[ i ];
+
+ list_sl_add_after( &node, &new_node );
+
+ node = new_node;
+ }
+
+ i = 0;
+
+ for ( node = list->first; node != NULL; node = node->next )
+ {
+ assert( strcmp( array[ i ], ( char * ) node->val ) == 0 );
+
+ i++;
+ }
fprintf( stderr, "OK\n" );
}
{
fprintf( stderr, " Testing list_sl_remove_beg ... " );
- list_sl *list = NULL;
- node_sl *node1 = NULL;
+ char *array[3] = { "test1", "test2", "test3" };
+ list_sl *list = NULL;
+ node_sl *node = NULL;
+ node_sl *new_node = NULL;
+ int i = 0;
- list_sl_new( &list );
+ list = list_sl_new();
+ new_node = node_sl_new();
- node1 = mem_get( sizeof( node_sl ) );
+ new_node->val = array[ 0 ];
- node1->val = "TEST1";
+ list_sl_add_beg( &list, &new_node );
- assert( list->first == NULL );
+ node = new_node;
- list_sl_add_beg( &list, &node1 );
- assert( list->first == node1 );
- assert( strcmp( list->first->val, "TEST1" ) == 0 );
+ for ( i = 1; i < 3; i++ )
+ {
+ new_node = node_sl_new();
- list_sl_remove_beg( &list );
- assert( list->first == NULL );
+ new_node->val = array[ i ];
+
+ list_sl_add_after( &node, &new_node );
+
+ node = new_node;
+ }
+
+ i = 0;
+
+ node = list->first;
+
+ while ( node != NULL )
+ {
+ assert( strcmp( ( char * ) node->val, array[ i ] ) == 0 );
+
+ list_sl_remove_beg( &list );
+
+ node = list->first;
+
+ i++;
+ }
fprintf( stderr, "OK\n" );
}
{
fprintf( stderr, " Testing list_sl_remove_after ... " );
- list_sl *list = NULL;
- node_sl *node1 = NULL;
- node_sl *node2 = NULL;
+ char *array[3] = { "test1", "test2", "test3" };
+ list_sl *list = NULL;
+ node_sl *node = NULL;
+ node_sl *new_node = NULL;
+ int i = 0;
- list_sl_new( &list );
+ list = list_sl_new();
+ new_node = node_sl_new();
- node1 = mem_get( sizeof( node_sl ) );
- node2 = mem_get( sizeof( node_sl ) );
+ new_node->val = array[ 0 ];
- node1->val = "TEST1";
- node2->val = "TEST2";
+ list_sl_add_beg( &list, &new_node );
- assert( list->first == NULL );
+ node = new_node;
- list_sl_add_beg( &list, &node1 );
- assert( list->first == node1 );
- assert( strcmp( list->first->val, "TEST1" ) == 0 );
+ for ( i = 1; i < 3; i++ )
+ {
+ new_node = node_sl_new();
- list_sl_add_after( &node1, &node2 );
- assert( list->first == node1 );
- assert( strcmp( list->first->val, "TEST1" ) == 0 );
+ new_node->val = array[ i ];
- list_sl_remove_after( &node1 );
- assert( list->first->next == NULL );
+ list_sl_add_after( &node, &new_node );
+
+ node = new_node;
+ }
+
+ assert( strcmp( ( char * ) list->first->next->val, "test2" ) == 0 );
+
+ list_sl_remove_after( &list->first );
+
+ assert( strcmp( ( char * ) list->first->next->val, "test3" ) == 0 );
fprintf( stderr, "OK\n" );
}
node_sl *node2 = NULL;
node_sl *node3 = NULL;
- list_sl_new( &list );
+ list = list_sl_new();
- node1 = mem_get( sizeof( node_sl ) );
- node2 = mem_get( sizeof( node_sl ) );
- node3 = mem_get( sizeof( node_sl ) );
+ node1 = node_sl_new();
+ node2 = node_sl_new();
+ node3 = node_sl_new();
node1->val = "TEST1";
node2->val = "TEST2";
{
fprintf( stderr, " Testing list_sl_destroy ... " );
- list_sl *list = NULL;
- node_sl *node1 = NULL;
- node_sl *node2 = NULL;
- node_sl *node3 = NULL;
+ char *array[3] = { "test1", "test2", "test3" };
+ list_sl *list = NULL;
+ node_sl *node = NULL;
+ int i = 0;
- list_sl_new( &list );
+ list = list_sl_new();
- node1 = mem_get( sizeof( node_sl ) );
- node2 = mem_get( sizeof( node_sl ) );
- node3 = mem_get( sizeof( node_sl ) );
+ for ( i = 0; i < 3; i++ )
+ {
+ node = node_sl_new();
- node1->val = "TEST1";
- node2->val = "TEST2";
- node3->val = "TEST3";
+ node->val = array[ i ];
- list_sl_add_beg( &list, &node1 );
- list_sl_add_beg( &list, &node2 );
- list_sl_add_beg( &list, &node3 );
+ list_sl_add_beg( &list, &node );
+ }
list_sl_destroy( &list );
}
+/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> DOUBLY LINKED LIST <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */
+
+
void test_list_dl_new()
{
fprintf( stderr, " Testing list_dl_new ... " );
list_dl *list = NULL;
- list_dl_new( &list );
+ list = list_dl_new();
assert( list->first == NULL );
assert( list->last == NULL );
}
-void test_list_dl_add_beg()
+void test_node_dl_new()
{
- fprintf( stderr, " Testing list_dl_add_beg ... " );
+ fprintf( stderr, " Testing node_dl_new ... " );
+
+ node_dl *node = NULL;
+
+ node = node_dl_new();
+
+ assert( node->next == NULL );
+ assert( node->prev == NULL );
+ assert( node->val == NULL );
- list_dl *list = NULL;
- node_dl *node1 = NULL;
- node_dl *node2 = NULL;
- node_dl *node3 = NULL;
+ fprintf( stderr, "OK\n" );
+}
- list_dl_new( &list );
- node1 = mem_get( sizeof( node_dl ) );
- node2 = mem_get( sizeof( node_dl ) );
- node3 = mem_get( sizeof( node_dl ) );
+void test_list_dl_add_beg()
+{
+ fprintf( stderr, " Testing list_dl_add_beg ... " );
+
+ list_dl *list = 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";
{
fprintf( stderr, " Testing list_dl_add_end ... " );
- list_dl *list = NULL;
- node_dl *node1 = NULL;
- node_dl *node2 = NULL;
- node_dl *node3 = NULL;
-
- list_dl_new( &list );
-
- node1 = mem_get( sizeof( node_dl ) );
- node2 = mem_get( sizeof( node_dl ) );
- node3 = mem_get( sizeof( node_dl ) );
+ list_dl *list = 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";
{
fprintf( stderr, " Testing list_dl_add_before ... " );
- list_dl *list = NULL;
- node_dl *node1 = NULL;
- node_dl *node2 = NULL;
- node_dl *node3 = NULL;
-
- list_dl_new( &list );
-
- node1 = mem_get( sizeof( node_dl ) );
- node2 = mem_get( sizeof( node_dl ) );
- node3 = mem_get( sizeof( node_dl ) );
+ list_dl *list = 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";
{
fprintf( stderr, " Testing list_dl_add_after ... " );
- list_dl *list = NULL;
- node_dl *node1 = NULL;
- node_dl *node2 = NULL;
- node_dl *node3 = NULL;
-
- list_dl_new( &list );
-
- node1 = mem_get( sizeof( node_dl ) );
- node2 = mem_get( sizeof( node_dl ) );
- node3 = mem_get( sizeof( node_dl ) );
+ list_dl *list = 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";
{
fprintf( stderr, " Testing list_dl_remove ... " );
- list_dl *list = NULL;
- node_dl *node1 = NULL;
- node_dl *node2 = NULL;
- node_dl *node3 = NULL;
-
- list_dl_new( &list );
-
- node1 = mem_get( sizeof( node_dl ) );
- node2 = mem_get( sizeof( node_dl ) );
- node3 = mem_get( sizeof( node_dl ) );
+ list_dl *list = 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";
list_dl_add_beg( &list, &node1 );
- assert( strcmp( list->first->val, "TEST1" ) == 0 );
-
list_dl_add_after( &list, &node1, &node2 );
-
- assert( strcmp( list->last->val, "TEST2" ) == 0 );
-
- list_dl_add_after( &list, &node1, &node3 );
-
- assert( strcmp( list->last->val, "TEST2" ) == 0 );
-
list_dl_add_after( &list, &node2, &node3 );
- assert( strcmp( list->last->val, "TEST3" ) == 0 );
-
list_dl_remove( &list, &node3 );
-
assert( strcmp( list->last->val, "TEST2" ) == 0 );
list_dl_remove( &list, &node2 );
-
- assert( strcmp( list->first->val, "TEST1" ) == 0 );
+ assert( strcmp( list->last->val, "TEST1" ) == 0 );
list_dl_remove( &list, &node1 );
+ assert( list->first == NULL );
+ assert( list->last == NULL );
+
fprintf( stderr, "OK\n" );
}
{
fprintf( stderr, " Testing list_dl_print ... " );
- list_dl *list = NULL;
- node_dl *node1 = NULL;
- node_dl *node2 = NULL;
- node_dl *node3 = NULL;
-
- list_dl_new( &list );
-
- node1 = mem_get( sizeof( node_dl ) );
- node2 = mem_get( sizeof( node_dl ) );
- node3 = mem_get( sizeof( node_dl ) );
+ list_dl *list = 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";
list_dl_add_beg( &list, &node2 );
list_dl_add_beg( &list, &node3 );
-// list_dl_print( list );
+ // list_dl_print( list );
fprintf( stderr, "OK\n" );
}
{
fprintf( stderr, " Testing list_dl_destroy ... " );
- list_dl *list = NULL;
- node_dl *node1 = NULL;
- node_dl *node2 = NULL;
- node_dl *node3 = NULL;
-
- list_dl_new( &list );
-
- node1 = mem_get( sizeof( node_dl ) );
- node2 = mem_get( sizeof( node_dl ) );
- node3 = mem_get( sizeof( node_dl ) );
+ list_dl *list = 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";
list_dl_add_beg( &list, &node2 );
list_dl_add_beg( &list, &node3 );
+// list_dl_print( list );
+
list_dl_destroy( &list );
assert( list == NULL );
-// list_dl_print( list );
-
fprintf( stderr, "OK\n" );
}
+
+/* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< */
+
+
{
fprintf( stderr, " Testing seq_new ... " );
- seq_entry *entry;
+ seq_entry *entry = NULL;
size_t max_seq_name = MAX_SEQ_NAME;
size_t max_seq = MAX_SEQ;
- seq_new( &entry, max_seq_name, max_seq );
+ entry = seq_new( max_seq_name, max_seq );
assert( entry->seq_name != NULL );
assert( entry->seq != NULL );
{
fprintf( stderr, " Testing seq_destroy ... " );
- seq_entry *entry;
+ seq_entry *entry = NULL;
size_t max_seq_name = MAX_SEQ_NAME;
size_t max_seq = MAX_SEQ;
- seq_new( &entry, max_seq_name, max_seq );
+ entry = seq_new( max_seq_name, max_seq );
assert( entry->seq_name != NULL );
assert( entry->seq != NULL );