← Back to branch summary

~ubuntu-branches/ubuntu/maverick/ncbi-tools6/maverick

« back to all changes in this revision

Viewing changes to util/creaders/alnread.c

  • Committer: Bazaar Package Importer
  • Author(s): Aaron M. Ucko
  • Date: 2005-03-27 12:00:15 UTC
  • mfrom: (2.1.2 hoary)
  • Revision ID: james.westby@ubuntu.com-20050327120015-embhesp32nj73p9r
Tags: 6.1.20041020-3
http://bugs.debian.org/295110
* Fix FTBFS under GCC 4.0 caused by inconsistent use of "static" on
  functions.  (Closes: #295110.)
* Add a watch file, now that we can.  (Upstream's layout needs version=3.)

Show diffs side-by-side

added added

removed removed

Lines of Context:
util/creaders/alnread.c
 
1
/*
 
2
 * $Id: alnread.c,v 1.12 2004/09/17 12:21:48 bollin Exp $
 
3
 *
 
4
 * ===========================================================================
 
5
 *
 
6
 *                            PUBLIC DOMAIN NOTICE
 
7
 *               National Center for Biotechnology Information
 
8
 *
 
9
 *  This software/database is a "United States Government Work" under the
 
10
 *  terms of the United States Copyright Act.  It was written as part of
 
11
 *  the author's official duties as a United States Government employee and
 
12
 *  thus cannot be copyrighted.  This software/database is freely available
 
13
 *  to the public for use. The National Library of Medicine and the U.S.
 
14
 *  Government have not placed any restriction on its use or reproduction.
 
15
 *
 
16
 *  Although all reasonable efforts have been taken to ensure the accuracy
 
17
 *  and reliability of the software and data, the NLM and the U.S.
 
18
 *  Government do not and cannot warrant the performance or results that
 
19
 *  may be obtained by using this software or data. The NLM and the U.S.
 
20
 *  Government disclaim all warranties, express or implied, including
 
21
 *  warranties of performance, merchantability or fitness for any particular
 
22
 *  purpose.
 
23
 *
 
24
 *  Please cite the author in any work or product based on this material.
 
25
 *
 
26
 * ===========================================================================
 
27
 *
 
28
 * Authors:  Colleen Bollin
 
29
 *
 
30
 */
 
31
 
 
32
#include <util/creaders/alnread.h>
 
33
#include <stdio.h>
 
34
#include <stdlib.h>
 
35
#include <string.h>
 
36
#include <ctype.h>
 
37
 
 
38
static const int kMaxPrintedIntLen = 10;
 
39
#define MAX_PRINTED_INT_LEN_PLUS_ONE 11
 
40
 
 
41
typedef enum {
 
42
    eTrue = -1,
 
43
    eFalse = 0
 
44
} EBool;
 
45
 
 
46
/* structures used internally */
 
47
typedef struct SLineInfo {
 
48
    char *             data;
 
49
    int                line_num;
 
50
    int                line_offset;
 
51
    EBool              delete_me;
 
52
    struct SLineInfo * next;
 
53
} SLineInfo, * TLineInfoPtr;
 
54
 
 
55
typedef struct SLineInfoReader {
 
56
    TLineInfoPtr first_line;
 
57
    TLineInfoPtr curr_line;
 
58
    char *       curr_line_pos;
 
59
    int          data_pos;
 
60
} SLineInfoReader, * TLineInfoReaderPtr;
 
61
 
 
62
typedef struct SIntLink {
 
63
    int               ival;
 
64
    struct SIntLink * next;
 
65
} SIntLink, * TIntLinkPtr;
 
66
 
 
67
typedef struct SStringCount {
 
68
    char *                string;
 
69
    int                   num_appearances;
 
70
    TIntLinkPtr           line_numbers;
 
71
    struct SStringCount * next;
 
72
} SStringCount, * TStringCountPtr;
 
73
 
 
74
typedef struct SSizeInfo {
 
75
    int                size_value;
 
76
    int                num_appearances;
 
77
    struct SSizeInfo * next;
 
78
} SSizeInfo, * TSizeInfoPtr;
 
79
 
 
80
typedef struct SLengthList {
 
81
    TSizeInfoPtr         lengthrepeats;
 
82
    int                  num_appearances;
 
83
    struct SLengthList * next;
 
84
} SLengthListData, * SLengthListPtr;
 
85
 
 
86
typedef struct SCommentLoc {
 
87
  char *               start;
 
88
  char *               end;
 
89
  struct SCommentLoc * next;
 
90
} SCommentLoc, * TCommentLocPtr;
 
91
 
 
92
typedef struct SBracketedCommentList 
 
93
{
 
94
        TLineInfoPtr                   comment_lines;
 
95
        struct SBracketedCommentList * next;
 
96
} SBracketedCommentList, * TBracketedCommentListPtr;
 
97
 
 
98
typedef struct SAlignRawSeq {
 
99
    char *                id;
 
100
    TLineInfoPtr          sequence_data;
 
101
    TIntLinkPtr           id_lines;
 
102
    struct SAlignRawSeq * next;
 
103
} SAlignRawSeq, * TAlignRawSeqPtr;
 
104
 
 
105
typedef struct SAlignFileRaw {
 
106
    TLineInfoPtr         line_list;
 
107
    TLineInfoPtr         organisms;
 
108
    TAlignRawSeqPtr      sequences;
 
109
    int                  num_organisms;
 
110
    TLineInfoPtr         deflines;
 
111
    int                  num_deflines;
 
112
    EBool                marked_ids;
 
113
    int                  block_size;
 
114
    TIntLinkPtr          offset_list;
 
115
    FReportErrorFunction report_error;
 
116
    void *               report_error_userdata;
 
117
    char *               alphabet;
 
118
    int                  expected_num_sequence;
 
119
    int                  expected_sequence_len;
 
120
    int                  num_segments;
 
121
} SAlignRawFileData, * SAlignRawFilePtr;
 
122
 
 
123
/* These functions are used for storing and transmitting information
 
124
 * about errors encountered while reading the alignment data.
 
125
 */
 
126
 
 
127
/* This function allocates memory for a new error structure and populates
 
128
 * the structure with default values.
 
129
 * The new structure will be added to the end of the linked list of error
 
130
 * structures pointed to by list.
 
131
 */
 
132
extern TErrorInfoPtr ErrorInfoNew (TErrorInfoPtr list)
 
133
{
 
134
    TErrorInfoPtr eip, last;
 
135
 
 
136
    eip = (TErrorInfoPtr) malloc ( sizeof (SErrorInfo));
 
137
    if (eip == NULL) {
 
138
        return NULL;
 
139
    }
 
140
    eip->category = eAlnErr_Unknown;
 
141
    eip->line_num = -1;
 
142
    eip->id       = NULL;
 
143
    eip->message  = NULL;
 
144
    eip->next     = NULL;
 
145
    last = list;
 
146
    while (last != NULL && last->next != NULL) {
 
147
        last = last->next;
 
148
    }
 
149
    if (last != NULL) {
 
150
        last->next = eip;
 
151
    }
 
152
    return eip;
 
153
}
 
154
 
 
155
 
 
156
/* This function recursively frees the memory associated with a list of
 
157
 * error structures as well as the member variables of the error structures.
 
158
 */
 
159
extern void ErrorInfoFree (TErrorInfoPtr eip)
 
160
{
 
161
    if (eip == NULL) {
 
162
        return;
 
163
    }
 
164
    ErrorInfoFree (eip->next);
 
165
    free (eip->id);
 
166
    free (eip->message);
 
167
    free (eip);
 
168
}
 
169
 
 
170
/* This function creates and sends an error message regarding a NEXUS comment
 
171
 * character.
 
172
 */
 
173
static void 
 
174
s_ReportCharCommentError 
 
175
(char * expected,
 
176
 char    seen,
 
177
 char * val_name,
 
178
 FReportErrorFunction errfunc,
 
179
 void *             errdata)
 
180
{
 
181
    TErrorInfoPtr eip;
 
182
    const char * errformat = "Specified %s character does not match NEXUS"
 
183
                             " comment in file (specified %s, comment %c)";
 
184
 
 
185
    if (errfunc == NULL  ||  val_name == NULL || expected == NULL) {
 
186
        return;
 
187
    }
 
188
 
 
189
    eip = ErrorInfoNew (NULL);
 
190
    if (eip != NULL) {
 
191
        eip->category = eAlnErr_BadFormat;
 
192
        eip->message = (char *) malloc (strlen (errformat) + strlen (val_name)
 
193
                                        + strlen (expected) + 2);
 
194
        if (eip->message != NULL) {
 
195
            sprintf (eip->message, errformat, val_name, expected, seen);
 
196
        }
 
197
        errfunc (eip, errdata);
 
198
    }
 
199
}
 
200
 
 
201
 
 
202
/* This function creates and sends an error message regarding a character
 
203
 * that is unexpected in sequence data.
 
204
 */
 
205
static void 
 
206
s_ReportBadCharError 
 
207
(char *  id,
 
208
 char    bad_char,
 
209
 int     num_bad,
 
210
 int     offset,
 
211
 int     line_number,
 
212
 char *  reason,
 
213
 FReportErrorFunction errfunc,
 
214
 void *             errdata)
 
215
{
 
216
    TErrorInfoPtr eip;
 
217
    const char *  err_format =
 
218
                          "%d bad characters (%c) found at position %d (%s).";
 
219
 
 
220
    if (errfunc == NULL  ||  num_bad == 0  ||  bad_char == 0
 
221
        ||  reason == NULL) {
 
222
        return;
 
223
    }
 
224
 
 
225
    eip = ErrorInfoNew (NULL);
 
226
    if (eip == NULL) {
 
227
        return;
 
228
    }
 
229
 
 
230
    eip->category = eAlnErr_BadData;
 
231
    if (id != NULL) eip->id = strdup (id);
 
232
    eip->line_num = line_number;
 
233
    eip->message = (char *) malloc (strlen (err_format) + 2 * kMaxPrintedIntLen
 
234
                                    + strlen (reason) + 3);
 
235
    if (eip->message != NULL)
 
236
    {
 
237
        sprintf (eip->message, err_format, num_bad, bad_char, offset, reason);
 
238
    }
 
239
    errfunc (eip, errdata);
 
240
}
 
241
 
 
242
 
 
243
/* This function creates and sends an error message regarding an ID that
 
244
 * was found in the wrong location.
 
245
 */
 
246
static void 
 
247
s_ReportInconsistentID 
 
248
(char *               id,
 
249
 int                  line_number,
 
250
 FReportErrorFunction report_error,
 
251
 void *              report_error_userdata)
 
252
{
 
253
    TErrorInfoPtr eip;
 
254
 
 
255
    if (report_error == NULL) {
 
256
        return;
 
257
    }
 
258
    eip = ErrorInfoNew (NULL);
 
259
    if (eip == NULL) {
 
260
        return;
 
261
    }
 
262
    eip->category = eAlnErr_BadFormat;
 
263
    eip->id = strdup (id);
 
264
    eip->line_num = line_number;
 
265
    eip->message = strdup ("Found unexpected ID");
 
266
    report_error (eip, report_error_userdata);
 
267
}
 
268
 
 
269
 
 
270
/* This function creates and sends an error message regarding a line
 
271
 * of sequence data that was expected to have a different length.
 
272
 */
 
273
static void 
 
274
s_ReportInconsistentBlockLine 
 
275
(char *               id,
 
276
 int                  line_number,
 
277
 FReportErrorFunction report_error,
 
278
 void *              report_error_userdata)
 
279
{
 
280
    TErrorInfoPtr eip;
 
281
 
 
282
    if (report_error == NULL) {
 
283
        return;
 
284
    }
 
285
    eip = ErrorInfoNew (NULL);
 
286
    if (eip == NULL) {
 
287
        return;
 
288
    }
 
289
    eip->category = eAlnErr_BadFormat;
 
290
    eip->id = strdup (id);
 
291
    eip->line_num = line_number;
 
292
    eip->message = strdup ("Inconsistent block line formatting");
 
293
    report_error (eip, report_error_userdata);
 
294
}
 
295
 
 
296
 
 
297
/* This function creates and sends an error message regarding mismatched
 
298
 * definition lines
 
299
 */
 
300
static void
 
301
s_ReportDefinitionLineMismatch
 
302
(FReportErrorFunction report_error,
 
303
 void *              report_error_userdata)
 
304
{
 
305
    TErrorInfoPtr eip;
 
306
 
 
307
    if (report_error == NULL) {
 
308
        return;
 
309
    }
 
310
    eip = ErrorInfoNew (NULL);
 
311
    if (eip == NULL) {
 
312
        return;
 
313
    }
 
314
 
 
315
    eip->category = eAlnErr_BadData;
 
316
    eip->message = strdup ("Mismatched definition lines");
 
317
    report_error (eip, report_error_userdata);
 
318
}
 
319
 
 
320
 
 
321
/* This function recursively creates and sends an error message 
 
322
 * regarding the number of times items in list appear.
 
323
 */
 
324
static void 
 
325
s_ReportDefinitionLines 
 
326
(TStringCountPtr      list,
 
327
 FReportErrorFunction report_error,
 
328
 void *              report_error_userdata)
 
329
{
 
330
    TErrorInfoPtr eip;
 
331
    const char *  err_null_format = "Null definition line occurs %d times";
 
332
    const char *  err_format = "Definition line %s occurs %d times";
 
333
 
 
334
    if (list == NULL  ||  report_error == NULL) {
 
335
        return;
 
336
    }
 
337
    eip = ErrorInfoNew (NULL);
 
338
    if (eip == NULL) {
 
339
        return;
 
340
    }
 
341
 
 
342
    eip->category = eAlnErr_BadData;
 
343
    if (list->string == NULL) {
 
344
        eip->message = malloc (strlen (err_null_format)
 
345
                               + kMaxPrintedIntLen + 1);
 
346
        if (eip->message != NULL) {
 
347
            sprintf (eip->message, err_null_format, list->num_appearances);
 
348
        }
 
349
    } else {
 
350
        eip->message = malloc (strlen (err_format)
 
351
                               + strlen (list->string)
 
352
                               + kMaxPrintedIntLen + 1);
 
353
        if (eip->message != NULL) {
 
354
            sprintf (eip->message, err_format, list->string,
 
355
                     list->num_appearances);
 
356
        }
 
357
    }
 
358
    report_error (eip, report_error_userdata);
 
359
  
 
360
    s_ReportDefinitionLines (list->next, report_error, report_error_userdata);
 
361
}
 
362
 
 
363
  
 
364
/* This function creates and sends an error message regarding a line of
 
365
 * sequence data that was expected to be a different length.
 
366
 */
 
367
static void 
 
368
s_ReportLineLengthError 
 
369
(char *               id,
 
370
 TLineInfoPtr         lip,
 
371
 int                  expected_length,
 
372
 FReportErrorFunction report_error,
 
373
 void *               report_error_userdata)
 
374
{
 
375
    TErrorInfoPtr eip;
 
376
    char *        msg;
 
377
    const char *  format = "Expected line length %d, actual length %d";
 
378
    int           len;
 
379
 
 
380
    if (lip == NULL  ||  report_error == NULL) {
 
381
        return;
 
382
    }
 
383
 
 
384
    eip = ErrorInfoNew (NULL);
 
385
    if (eip == NULL) {
 
386
        return;
 
387
    }
 
388
    eip->category = eAlnErr_BadFormat;
 
389
    eip->id = strdup (id);
 
390
    eip->line_num = lip->line_num;
 
391
    msg = (char *) malloc (strlen (format) + kMaxPrintedIntLen + 1);
 
392
    if (msg != NULL) {
 
393
        if (lip->data == NULL) {
 
394
            len = 0;
 
395
        } else {
 
396
            len = strlen (lip->data);
 
397
        }
 
398
        sprintf (msg, format, expected_length, len);
 
399
        eip->message = msg;
 
400
    }
 
401
    report_error (eip, report_error_userdata);
 
402
}
 
403
 
 
404
 
 
405
/* This function creates and sends an error message regarding a block of
 
406
 * sequence data that was expected to contain more lines.
 
407
 */
 
408
static void 
 
409
s_ReportBlockLengthError 
 
410
(char *               id,
 
411
 int                  line_num,
 
412
 int                  expected_num,
 
413
 int                  actual_num,
 
414
 FReportErrorFunction report_error,
 
415
 void *              report_error_userdata)
 
416
{
 
417
    TErrorInfoPtr eip;
 
418
    const char *  err_format = "Expected %d lines in block, found %d";
 
419
 
 
420
    if (report_error == NULL) {
 
421
        return;
 
422
    }
 
423
 
 
424
    eip = ErrorInfoNew (NULL);
 
425
    if (eip == NULL) {
 
426
        return;
 
427
    }
 
428
    eip->category = eAlnErr_BadFormat;
 
429
    eip->id = strdup (id);
 
430
    eip->line_num = line_num;
 
431
    eip->message = malloc (strlen (err_format) + 2 * kMaxPrintedIntLen + 1);
 
432
    if (eip->message != NULL) {
 
433
      sprintf (eip->message, err_format, expected_num, actual_num);
 
434
    }
 
435
    report_error (eip, report_error_userdata);
 
436
}
 
437
 
 
438
 
 
439
/* This function creates and sends an error message regarding missing
 
440
 * sequence data.
 
441
 */
 
442
static void
 
443
s_ReportMissingSequenceData
 
444
(char *               id,
 
445
 FReportErrorFunction report_error,
 
446
 void *              report_error_userdata)
 
447
{
 
448
    TErrorInfoPtr eip;
 
449
 
 
450
    if (report_error == NULL) {
 
451
        return;
 
452
    }
 
453
    eip = ErrorInfoNew (NULL);
 
454
    if (eip == NULL) {
 
455
        return;
 
456
    }
 
457
    eip->category = eAlnErr_Fatal;
 
458
    eip->id = strdup (id);
 
459
    eip->message = strdup ("No data found");
 
460
    report_error (eip, report_error_userdata);
 
461
}
 
462
 
 
463
 
 
464
/* This function creates and sends an error message indicating that the
 
465
 * most common length of the sequences in the file do not match a comment
 
466
 * found in the file.
 
467
 */
 
468
static void 
 
469
s_ReportBadSequenceLength 
 
470
(char *               id,
 
471
 int                  expected_length,
 
472
 int                  actual_length,
 
473
 FReportErrorFunction report_error,
 
474
 void *               report_error_userdata)
 
475
{
 
476
    TErrorInfoPtr eip;
 
477
    const char *  format_str = "Expected sequence length %d, actual length %d";
 
478
 
 
479
    if (report_error == NULL) {
 
480
        return;
 
481
    }
 
482
    eip = ErrorInfoNew (NULL);
 
483
    if (eip == NULL) {
 
484
        return;
 
485
    }
 
486
    eip->category = eAlnErr_BadFormat;
 
487
    eip->id = strdup (id);
 
488
    eip->message = malloc (strlen (format_str) + 50);
 
489
    if (eip->message != NULL) {
 
490
        sprintf (eip->message, format_str, expected_length, actual_length);
 
491
    }
 
492
    report_error (eip, report_error_userdata);
 
493
}
 
494
 
 
495
 
 
496
/* This function creates and sends an error message indicating that the
 
497
 * number of sequences read does not match a comment in the alignment file.
 
498
 */
 
499
static void
 
500
s_ReportIncorrectNumberOfSequences
 
501
(int                  num_expected,
 
502
 int                  num_found,
 
503
 FReportErrorFunction report_error,
 
504
 void *              report_error_userdata)
 
505
{
 
506
    TErrorInfoPtr eip;
 
507
    const char *  err_format = "Expected %d sequences, found %d";
 
508
 
 
509
    if (report_error == NULL) {
 
510
        return;
 
511
    }
 
512
    eip = ErrorInfoNew (NULL);
 
513
    if (eip == NULL) {
 
514
        return;
 
515
    }
 
516
    eip->category = eAlnErr_BadFormat;
 
517
    eip->message = (char *) malloc (strlen (err_format) +
 
518
                                    2 * kMaxPrintedIntLen + 1);
 
519
                                     
 
520
    if (eip->message != NULL)
 
521
    {
 
522
        sprintf (eip->message, err_format, num_expected, num_found);
 
523
    }
 
524
    report_error (eip, report_error_userdata);
 
525
}
 
526
 
 
527
 
 
528
static void
 
529
s_ReportIncorrectSequenceLength 
 
530
(int                 len_expected,
 
531
 int                 len_found,
 
532
 FReportErrorFunction report_error,
 
533
 void *             report_error_userdata)
 
534
{
 
535
    TErrorInfoPtr eip;
 
536
    const char *  err_format = "Expected sequences of length %d, found %d";
 
537
 
 
538
    if (report_error == NULL) {
 
539
        return;
 
540
    }
 
541
    eip = ErrorInfoNew (NULL);
 
542
    if (eip == NULL) {
 
543
        return;
 
544
    }
 
545
 
 
546
    eip->category = eAlnErr_BadFormat;
 
547
    eip->message = (char *)malloc (strlen (err_format)
 
548
                                   + 2 * kMaxPrintedIntLen + 1);
 
549
    if (eip->message != NULL)
 
550
    {
 
551
      sprintf (eip->message, err_format, len_expected, len_found);
 
552
    }
 
553
    report_error (eip, report_error_userdata);
 
554
}
 
555
 
 
556
 
 
557
/* This function creates and sends an error message regarding a non-unique
 
558
 * organism name.
 
559
 */
 
560
static void
 
561
s_ReportRepeatedOrganismName
 
562
(char *               id,
 
563
 int                  line_num,
 
564
 int                  second_line_num,
 
565
 char *               org_name,
 
566
 FReportErrorFunction report_error,
 
567
 void *              report_error_userdata)
 
568
{
 
569
    TErrorInfoPtr eip;
 
570
    const char *  err_format = "Organism name %s also appears at line %d";
 
571
 
 
572
    if (report_error == NULL || org_name == NULL) {
 
573
        return;
 
574
    }
 
575
    eip = ErrorInfoNew (NULL);
 
576
    if (eip == NULL) {
 
577
        return;
 
578
    }
 
579
    eip->category = eAlnErr_BadData;
 
580
    eip->line_num = line_num;
 
581
    if (id != NULL ) {
 
582
        eip->id = strdup (id);
 
583
    }
 
584
    eip->message = malloc (strlen (err_format) + strlen (org_name)
 
585
                           + kMaxPrintedIntLen + 1);
 
586
    if (eip->message != NULL) {
 
587
        sprintf (eip->message, err_format, org_name, second_line_num);
 
588
    }
 
589
    report_error (eip, report_error_userdata);
 
590
}
 
591
 
 
592
 
 
593
/* This function creates and sends an error message indicating that some or
 
594
 * all of the organism information for the sequences are missing.
 
595
 */
 
596
static void
 
597
s_ReportMissingOrganismInfo
 
598
(FReportErrorFunction report_error,
 
599
 void *             report_error_userdata)
 
600
{
 
601
    TErrorInfoPtr eip;
 
602
 
 
603
    if (report_error == NULL) {
 
604
        return;
 
605
    }
 
606
    eip = ErrorInfoNew (NULL);
 
607
    if (eip == NULL) {
 
608
        return;
 
609
    }
 
610
 
 
611
    eip->category = eAlnErr_BadData;
 
612
    eip->message = strdup ("Missing organism information");
 
613
    report_error (eip, report_error_userdata);
 
614
}
 
615
 
 
616
 
 
617
/* This function creates and sends an error message regarding an ID that is
 
618
 * used for more than one sequence.
 
619
 */
 
620
static void 
 
621
s_ReportRepeatedId 
 
622
(TStringCountPtr      scp,
 
623
 FReportErrorFunction report_error,
 
624
 void *              report_error_userdata)
 
625
{
 
626
    TErrorInfoPtr  eip;
 
627
    const char *   err_format = "ID %s appears in the following locations:";
 
628
    char *         cp;
 
629
    TIntLinkPtr    line_number;
 
630
 
 
631
    if (report_error == NULL  ||  scp == NULL  ||  scp->string == NULL) {
 
632
        return;
 
633
    }
 
634
 
 
635
    eip = ErrorInfoNew (NULL);
 
636
    if (eip == NULL) {
 
637
        return;
 
638
    }
 
639
 
 
640
    eip->category = eAlnErr_BadData;
 
641
    eip->id = strdup (scp->string);
 
642
    if (scp->line_numbers != NULL) {
 
643
        eip->line_num = scp->line_numbers->ival;
 
644
    }
 
645
    eip->message = (char *) malloc ( strlen (err_format)
 
646
                                    + strlen (scp->string)
 
647
                                    + scp->num_appearances * 15
 
648
                                    + 1);
 
649
    if (eip->message != NULL) {
 
650
        sprintf (eip->message, err_format, scp->string);
 
651
        cp = eip->message + strlen (eip->message);
 
652
        for (line_number = scp->line_numbers;
 
653
             line_number != NULL;
 
654
             line_number = line_number->next) {
 
655
            sprintf (cp, " %d", line_number->ival);
 
656
            cp += strlen (cp);
 
657
        }
 
658
    }
 
659
    report_error (eip, report_error_userdata);
 
660
}
 
661
 
 
662
 
 
663
/* This function creates and sends an error message indicating that the file
 
664
 * being read is an ASN.1 file.
 
665
 */
 
666
static void 
 
667
s_ReportASN1Error 
 
668
(FReportErrorFunction errfunc,
 
669
 void *             errdata)
 
670
{
 
671
    TErrorInfoPtr eip;
 
672
    const char * msg = "This is an ASN.1 file, "
 
673
        "which cannot be read by this function.";
 
674
 
 
675
    if (errfunc == NULL) {
 
676
        return;
 
677
    }
 
678
 
 
679
    eip = ErrorInfoNew (NULL);
 
680
    if (eip != NULL) {
 
681
        eip->category = eAlnErr_BadData;
 
682
        eip->message = (char *) malloc (strlen (msg) + 1);
 
683
        if (eip->message != NULL) {
 
684
            sprintf (eip->message, msg);
 
685
        }
 
686
        errfunc (eip, errdata);
 
687
    }
 
688
}
 
689
 
 
690
 
 
691
/* This function reports that some sequences are inside brackets (indicating a segmented set)
 
692
 * and that some sequences are outside the brackets.
 
693
 */
 
694
static void 
 
695
s_ReportSegmentedAlignmentError 
 
696
(TIntLinkPtr          offset_list,
 
697
 FReportErrorFunction errfunc,
 
698
 void *               errdata)
 
699
{
 
700
    TErrorInfoPtr eip;
 
701
    const char * msg = "This file contains sequences in brackets (indicating "
 
702
        "a segmented alignment) as well as sequences not in brackets at lines "
 
703
        "%s.  Please either add or remove brackets to correct this problem.";
 
704
    int num_lines = 0;
 
705
    int         msg_len = 0;
 
706
    TIntLinkPtr t;
 
707
    char *      line_text_list;
 
708
    char *      line_text_list_offset;
 
709
 
 
710
    if (errfunc == NULL || offset_list == NULL) {
 
711
        return;
 
712
    }
 
713
 
 
714
    for (t = offset_list; t != NULL; t = t->next)
 
715
    {
 
716
        num_lines ++;
 
717
    }
 
718
    msg_len = num_lines * (kMaxPrintedIntLen + 2);
 
719
    if (num_lines > 1) 
 
720
    {
 
721
        msg_len += 4;
 
722
    }
 
723
    line_text_list = (char *) malloc (msg_len);
 
724
    if (line_text_list == NULL) return;
 
725
    line_text_list_offset = line_text_list;
 
726
    for (t = offset_list; t != NULL; t = t->next)
 
727
    {
 
728
        if (t->next == NULL)
 
729
        {
 
730
            sprintf (line_text_list_offset, "%d", t->ival);
 
731
        }
 
732
        else if (num_lines == 2) 
 
733
        {
 
734
                sprintf (line_text_list_offset, "%d and ", t->ival);
 
735
        }
 
736
        else if (t->next->next == NULL)
 
737
        {
 
738
                sprintf (line_text_list_offset, "%d, and ", t->ival);
 
739
        }
 
740
        else
 
741
        {
 
742
                sprintf (line_text_list_offset, "%d, ", t->ival);
 
743
        }
 
744
        line_text_list_offset += strlen (line_text_list_offset);
 
745
    }
 
746
 
 
747
    msg_len += strlen (msg) + 1;
 
748
 
 
749
    eip = ErrorInfoNew (NULL);
 
750
    if (eip != NULL) {
 
751
        eip->category = eAlnErr_BadData;
 
752
        eip->message = (char *) malloc (msg_len);
 
753
        if (eip->message != NULL) {
 
754
            sprintf (eip->message, msg, line_text_list);
 
755
        }
 
756
        errfunc (eip, errdata);
 
757
    }
 
758
    free (line_text_list);
 
759
}
 
760
 
 
761
 
 
762
/* This function reports an error if a line looks like it might contain an organism comment
 
763
 * but is somehow improperly formatted
 
764
 */
 
765
static void s_ReportOrgCommentError 
 
766
(char *               linestring,
 
767
 FReportErrorFunction errfunc,
 
768
 void *               errdata)
 
769
{
 
770
    TErrorInfoPtr eip;
 
771
    const char * msg = "This line may contain an improperly formatted organism description.\n"
 
772
                       "Organism descriptions should be of the form [org=tax name] or [organism=tax name].\n";
 
773
    
 
774
    if (errfunc == NULL || linestring == NULL) {
 
775
        return;
 
776
    }
 
777
                       
 
778
    eip = ErrorInfoNew (NULL);
 
779
    if (eip != NULL) {
 
780
        eip->category = eAlnErr_BadData;
 
781
        eip->message = (char *) malloc (strlen (msg) + strlen (linestring) + 1);
 
782
        if (eip->message != NULL) {
 
783
            strcpy (eip->message, msg);
 
784
            strcat (eip->message, linestring);
 
785
        }
 
786
        errfunc (eip, errdata);
 
787
    }
 
788
}
 
789
 
 
790
 
 
791
/* This function reports that the number of segments in an alignment of
 
792
 * segmented sets is inconsistent.
 
793
 */
 
794
static void s_ReportBadNumSegError 
 
795
(int                  line_num,
 
796
 int                  num_seg,
 
797
 int                  num_seg_exp,
 
798
 FReportErrorFunction errfunc,
 
799
 void *               errdata)
 
800
{
 
801
    TErrorInfoPtr eip;
 
802
    const char * msg = "This segmented set contains a different number of segments (%d) than expected (%d).\n";
 
803
    
 
804
    if (errfunc == NULL) {
 
805
        return;
 
806
    }
 
807
                       
 
808
    eip = ErrorInfoNew (NULL);
 
809
    if (eip != NULL) {
 
810
        eip->line_num = line_num;
 
811
        eip->category = eAlnErr_BadData;
 
812
        eip->message = (char *) malloc (strlen (msg) + 2 * kMaxPrintedIntLen + 1);
 
813
        if (eip->message != NULL) {
 
814
            sprintf (eip->message, msg, num_seg, num_seg_exp);
 
815
        }
 
816
        errfunc (eip, errdata);
 
817
    }
 
818
}
 
819
 
 
820
 
 
821
/* This function allocates memory for a SSequenceInfo structure and
 
822
 * initializes the member variables.  It returns a pointer to the newly
 
823
 * allocated memory.
 
824
 */
 
825
extern TSequenceInfoPtr SequenceInfoNew (void)
 
826
{
 
827
    TSequenceInfoPtr sip;
 
828
 
 
829
    sip = (TSequenceInfoPtr) malloc (sizeof (SSequenceInfo));
 
830
    if (sip == NULL) {
 
831
        return NULL;
 
832
    }
 
833
    sip->missing       = strdup ("?");
 
834
    sip->beginning_gap = strdup (".");
 
835
    sip->middle_gap    = strdup ("-");
 
836
    sip->end_gap       = strdup (".");
 
837
    sip->match         = strdup (".");
 
838
    sip->alphabet      = NULL;
 
839
    return sip;
 
840
}
 
841
 
 
842
 
 
843
/* This function frees memory associated with the member variables of
 
844
 * the SSequenceInfo structure and with the structure itself.
 
845
 */
 
846
extern void SequenceInfoFree (TSequenceInfoPtr sip)
 
847
{
 
848
    if (sip == NULL) {
 
849
        return;
 
850
    }
 
851
    free (sip->alphabet);
 
852
    free (sip->missing);
 
853
    free (sip->beginning_gap);
 
854
    free (sip->middle_gap);
 
855
    free (sip->end_gap);
 
856
    free (sip->match);
 
857
    sip->alphabet = NULL;
 
858
    free (sip);
 
859
}
 
860
 
 
861
 
 
862
/* This function creates and sends an error message regarding an unused line.
 
863
 */
 
864
static void 
 
865
s_ReportUnusedLine
 
866
(int                  line_num_start,
 
867
 int                  line_num_stop,
 
868
 TLineInfoPtr         line_val,
 
869
 FReportErrorFunction errfunc,
 
870
 void *               errdata)
 
871
{
 
872
    TErrorInfoPtr eip;
 
873
    const char * errformat1 = "Line %d could not be assigned to an interleaved block";
 
874
    const char * errformat2 = "Lines %d through %d could not be assigned to an interleaved block";
 
875
    const char * errformat3 = "Contents of unused line: %s";
 
876
    int skip;
 
877
 
 
878
    if (errfunc == NULL  ||  line_val == NULL) {
 
879
        return;
 
880
    }
 
881
 
 
882
    eip = ErrorInfoNew (NULL);
 
883
    if (eip != NULL) {
 
884
        eip->category = eAlnErr_BadFormat;
 
885
        eip->line_num = line_num_start;
 
886
        if (line_num_start == line_num_stop) {
 
887
              eip->message = (char *) malloc (strlen (errformat1)
 
888
                                            + kMaxPrintedIntLen + 1);
 
889
            if (eip->message != NULL) {
 
890
                sprintf (eip->message, errformat1, line_num_start);
 
891
            }
 
892
        } else {
 
893
            eip->message = (char *) malloc (strlen (errformat2)
 
894
                                            + 2 * kMaxPrintedIntLen + 1);
 
895
            if (eip->message != NULL) {
 
896
                sprintf (eip->message, errformat2, line_num_start,
 
897
                         line_num_stop);
 
898
            }
 
899
        }
 
900
        errfunc (eip, errdata);
 
901
    }
 
902
    /* report contents of unused lines */
 
903
    for (skip = line_num_start;
 
904
         skip < line_num_stop + 1  &&  line_val != NULL;
 
905
         skip++) {
 
906
        if (line_val->data == NULL) {
 
907
            continue;
 
908
        }
 
909
        eip = ErrorInfoNew (NULL);
 
910
        if (eip != NULL) {
 
911
            eip->category = eAlnErr_BadFormat;
 
912
            eip->line_num = skip;
 
913
            eip->message = (char *) malloc (strlen (errformat3)
 
914
                                            + strlen (line_val->data) + 1);
 
915
            if (eip->message != NULL) {
 
916
                sprintf (eip->message, errformat3, line_val->data);
 
917
            }
 
918
            errfunc (eip, errdata);
 
919
        }
 
920
        line_val = line_val->next;
 
921
    }
 
922
}
 
923
 
 
924
 
 
925
/* The following functions are used to manage a linked list of integer
 
926
 * values.
 
927
 */
 
928
 
 
929
/* This function creates a new SIntLink structure with a value of ival.
 
930
 * The new structure will be placed at the end of list if list is not NULL.
 
931
 * The function will return a pointer to the new structure.
 
932
 */
 
933
static TIntLinkPtr 
 
934
s_IntLinkNew 
 
935
(int         ival, 
 
936
 TIntLinkPtr list)
 
937
{
 
938
    TIntLinkPtr ilp, last;
 
939
 
 
940
    ilp = (TIntLinkPtr) malloc (sizeof (SIntLink));
 
941
    if (ilp == NULL) {
 
942
        return NULL;
 
943
    }
 
944
    ilp->ival = ival;
 
945
    ilp->next = NULL;
 
946
    last = list;
 
947
    while (last != NULL && last->next != NULL) {
 
948
        last = last->next;
 
949
    }
 
950
    if (last != NULL) {
 
951
        last->next = ilp;
 
952
    }
 
953
    return ilp;
 
954
}
 
955
 
 
956
 
 
957
/* This function recursively frees memory associated with a linked list
 
958
 * of SIntLink structures.
 
959
 */
 
960
static void s_IntLinkFree (TIntLinkPtr ilp)
 
961
{
 
962
    if (ilp == NULL) {
 
963
        return;
 
964
    }
 
965
    s_IntLinkFree (ilp->next);
 
966
    free (ilp);
 
967
}
 
968
 
 
969
 
 
970
/* These functions are used to accumulate and retrieve information on 
 
971
 * how often a size of data (number of lines or number of characters) occurs.
 
972
 */
 
973
 
 
974
/* This function allocates space for a new SSizeInfo structure and 
 
975
 * initializes its member variables.  If list is not NULL, the new structure
 
976
 * is added to the end of the list.
 
977
 * The function returns a pointer to the newly allocated structure.
 
978
 */
 
979
static TSizeInfoPtr s_SizeInfoNew (TSizeInfoPtr list)
 
980
{
 
981
    TSizeInfoPtr sip, last;
 
982
 
 
983
    sip = (TSizeInfoPtr) malloc (sizeof (SSizeInfo));
 
984
    if (sip == NULL) {
 
985
        return NULL;
 
986
    }
 
987
 
 
988
    sip->size_value      = 0;
 
989
    sip->num_appearances = 0;
 
990
    sip->next            = NULL;
 
991
    last = list;
 
992
    while (last != NULL && last->next != NULL) {
 
993
        last = last->next;
 
994
    }
 
995
    if (last != NULL) {
 
996
        last->next = sip;
 
997
    }
 
998
    return sip;
 
999
}
 
1000
 
 
1001
 
 
1002
/* This function recursively frees the memory associated with a linked list
 
1003
 * of SSizeInfo structures.
 
1004
 */
 
1005
static void s_SizeInfoFree (TSizeInfoPtr list)
 
1006
{
 
1007
    if (list == NULL) {
 
1008
        return;
 
1009
    }
 
1010
    s_SizeInfoFree (list->next);
 
1011
    list->next = NULL;
 
1012
    free (list);
 
1013
}
 
1014
 
 
1015
 
 
1016
/* This function returns eTrue if the two SSizeInfo structures have
 
1017
 * the same size_value and number of appearances, eFalse otherwise.
 
1018
 */
 
1019
static EBool 
 
1020
s_SizeInfoIsEqual 
 
1021
(TSizeInfoPtr s1,
 
1022
 TSizeInfoPtr s2)
 
1023
{
 
1024
    if (s1 == NULL
 
1025
      ||  s2 == NULL
 
1026
      ||  s1->size_value != s2->size_value
 
1027
      ||  s1->num_appearances != s2->num_appearances) {
 
1028
        return eFalse;
 
1029
    }
 
1030
    return eTrue;
 
1031
}
 
1032
 
 
1033
 
 
1034
/* This function searches list for a SSizeInfo structure with the
 
1035
 * same size_value as size_value.  If it finds such a structure, it
 
1036
 * adds the value of num_appearances to the num_appearances for that
 
1037
 * structure, otherwise the function creates a new structure at the end
 
1038
 * of the list with the specified values of size_value and num_appearances.
 
1039
 * The function returns a pointer to the list of SSizeInfo structures.
 
1040
 */
 
1041
static TSizeInfoPtr s_AddSizeInfoAppearances 
 
1042
(TSizeInfoPtr list,
 
1043
 int  size_value,
 
1044
 int  num_appearances)
 
1045
{
 
1046
    TSizeInfoPtr p, last;
 
1047
 
 
1048
    last = NULL;
 
1049
    for (p = list;  p != NULL  &&  p->size_value != size_value;  p = p->next) {
 
1050
        last = p;
 
1051
    }
 
1052
    if (p == NULL) {
 
1053
        p = (TSizeInfoPtr) malloc (sizeof (SSizeInfo));
 
1054
        if (p == NULL) {
 
1055
            return NULL;
 
1056
        }
 
1057
        p->size_value = size_value;
 
1058
        p->num_appearances = num_appearances;
 
1059
        p->next = 0;
 
1060
        if (last == NULL) {
 
1061
            list = p;
 
1062
        } else {
 
1063
            last->next = p;
 
1064
        }
 
1065
    } else {
 
1066
        p->num_appearances += num_appearances;
 
1067
    }
 
1068
    return list;
 
1069
}
 
1070
 
 
1071
 
 
1072
/* This function searches list for a SSizeInfo structure with the
 
1073
 * same size_value as size_value.  If it finds such a structure, it
 
1074
 * adds one to the num_appearances for that structure, otherwise the 
 
1075
 * function creates a new structure at the end of the list with the 
 
1076
 * specified values of size_value and num_appearances.
 
1077
 * The function returns a pointer to the list of SSizeInfo structures.
 
1078
 */
 
1079
static TSizeInfoPtr 
 
1080
s_AddSizeInfo
 
1081
(TSizeInfoPtr list,
 
1082
 int  size_value)
 
1083
{
 
1084
    return s_AddSizeInfoAppearances (list, size_value, 1);
 
1085
}
 
1086
 
 
1087
 
 
1088
/* This function searches list for the SSizeInfo structure with the
 
1089
 * highest value for num_appearances.  If more than one structure exists
 
1090
 * with the highest value for num_appearances, the function chooses the
 
1091
 * value with the highest value for size_value.  The function returns a
 
1092
 * pointer to the structure selected based on the above criteria.
 
1093
 */
 
1094
static TSizeInfoPtr s_GetMostPopularSizeInfo (TSizeInfoPtr list)
 
1095
{
 
1096
    TSizeInfoPtr p, best;
 
1097
 
 
1098
    if (list == NULL) {
 
1099
        return NULL;
 
1100
    }
 
1101
 
 
1102
    best = list;
 
1103
    for (p = list->next;  p != NULL;  p = p->next) {
 
1104
      if (p->num_appearances > best->num_appearances
 
1105
          ||  (p->num_appearances == best->num_appearances
 
1106
            &&  p->size_value > best->size_value)) {
 
1107
          best = p;
 
1108
      }
 
1109
    }
 
1110
    return best;
 
1111
}
 
1112
 
 
1113
 
 
1114
/* This function uses s_GetMostPopularSizeInfo function to find the structure
 
1115
 * in list that has the highest value for num_appearances and size_value.
 
1116
 * If such a structure is found and has a num_appearances value greater than
 
1117
 * one, the size_value for that structure will be returned, otherwise the
 
1118
 * function returns 0.
 
1119
 */
 
1120
static int  s_GetMostPopularSize (TSizeInfoPtr list)
 
1121
{
 
1122
    TSizeInfoPtr best;
 
1123
 
 
1124
    best = s_GetMostPopularSizeInfo (list);
 
1125
    if (best == NULL) {
 
1126
        return 0;
 
1127
    }
 
1128
    if (best->num_appearances > 1) {
 
1129
        return best->size_value; 
 
1130
    } else {
 
1131
        return 0;
 
1132
    }
 
1133
}
 
1134
 
 
1135
 
 
1136
/* The following functions are used to keep track of patterns of line or
 
1137
 * token lengths, which will be used to identify errors in formatting.
 
1138
 */
 
1139
static SLengthListPtr s_LengthListNew (SLengthListPtr list)
 
1140
{
 
1141
    SLengthListPtr llp, last;
 
1142
 
 
1143
    llp = (SLengthListPtr) malloc (sizeof (SLengthListData));
 
1144
    if (llp == NULL) {
 
1145
        return NULL;
 
1146
    }
 
1147
 
 
1148
    llp->lengthrepeats   = NULL;
 
1149
    llp->num_appearances = 0;
 
1150
    llp->next            = NULL;
 
1151
 
 
1152
    last = list;
 
1153
    while (last != NULL && last->next != NULL) {
 
1154
        last = last->next;
 
1155
    }
 
1156
    if (last != NULL) {
 
1157
        last->next = llp;
 
1158
    }
 
1159
    return llp;
 
1160
}
 
1161
 
 
1162
 
 
1163
/* This function recursively frees memory for a list of SLengthListData
 
1164
 * structures and its member variables.
 
1165
 */
 
1166
static void s_LengthListFree (SLengthListPtr llp)
 
1167
{
 
1168
    if (llp == NULL) {
 
1169
        return;
 
1170
    }
 
1171
    s_LengthListFree (llp->next);
 
1172
    s_SizeInfoFree (llp->lengthrepeats);
 
1173
    free (llp);
 
1174
}
 
1175
 
 
1176
 
 
1177
/* This function examines the last SSizeInfo structure in the 
 
1178
 * lengthrepeats member variable of llp.  If the last structure 
 
1179
 * in the list has the same size_value value as the function argument 
 
1180
 * size_value, the value of num_appearances for that SizeInforData structure
 
1181
 * will be incremented.  Otherwise a new SSizeInfo structure will be
 
1182
 * appended to the end of the lengthrepeats list with the specified
 
1183
 * size_value and a num_appearances value of 1.
 
1184
 */
 
1185
static void 
 
1186
s_AddLengthRepeat
 
1187
(SLengthListPtr llp,
 
1188
 int  size_value)
 
1189
{
 
1190
    TSizeInfoPtr p, last;
 
1191
 
 
1192
    if (llp == NULL) {
 
1193
        return;
 
1194
    }
 
1195
 
 
1196
    last = NULL;
 
1197
    for (p = llp->lengthrepeats;  p != NULL;  p = p->next) {
 
1198
        last = p;
 
1199
    }
 
1200
    if (last == NULL  ||  last->size_value != size_value) {
 
1201
        p = (TSizeInfoPtr) malloc (sizeof (SSizeInfo));
 
1202
        if (p == NULL) {
 
1203
            return;
 
1204
        }
 
1205
        p->size_value = size_value;
 
1206
        p->num_appearances = 1;
 
1207
        p->next = 0;
 
1208
        if (last == NULL) {
 
1209
            llp->lengthrepeats = p;
 
1210
        } else {
 
1211
            last->next = p;
 
1212
        }
 
1213
    } else {
 
1214
        last->num_appearances ++;
 
1215
    }
 
1216
}
 
1217
 
 
1218
 
 
1219
/* This function examines whether two SLengthListData structures "match" - 
 
1220
 * the structures match if each SSizeInfo structure in llp1->lengthrepeats
 
1221
 * has the same size_value and num_appearances values as the SSizeInfo
 
1222
 * structure in the corresponding list position in llp2->lenghrepeats.
 
1223
 * If the two structures match, the function returns eTrue, otherwise the
 
1224
 * function returns eFalse.
 
1225
 */
 
1226
static EBool 
 
1227
s_DoLengthPatternsMatch 
 
1228
(SLengthListPtr llp1,
 
1229
 SLengthListPtr llp2)
 
1230
{
 
1231
    TSizeInfoPtr sip1, sip2;
 
1232
 
 
1233
    if (llp1 == NULL  ||  llp2 == NULL
 
1234
        ||  llp1->lengthrepeats == NULL
 
1235
        ||  llp2->lengthrepeats == NULL) {
 
1236
        return eFalse;
 
1237
    }
 
1238
    for (sip1 = llp1->lengthrepeats, sip2 = llp2->lengthrepeats;
 
1239
         sip1 != NULL  &&  sip2 != NULL;
 
1240
         sip1 = sip1->next, sip2 = sip2->next) {
 
1241
        if ( ! s_SizeInfoIsEqual (sip1, sip2)
 
1242
          ||  (sip1->next == NULL  &&  sip2->next != NULL)
 
1243
          ||  (sip1->next != NULL  &&  sip2->next == NULL)) {
 
1244
            return eFalse;
 
1245
        }
 
1246
    }
 
1247
    return eTrue;
 
1248
}
 
1249
 
 
1250
 
 
1251
/* This function examines a list of SLengthListData structures to see if
 
1252
 * one of them matches llp.  If so, the value of num_appearances in that
 
1253
 * list is incremented by one and llp is freed, otherwise llp is added
 
1254
 * to the end of the list.
 
1255
 * The function returns a pointer to the list of LenghtListData structures.
 
1256
 */
 
1257
static SLengthListPtr
 
1258
s_AddLengthList
 
1259
(SLengthListPtr list,
 
1260
 SLengthListPtr llp)
 
1261
{
 
1262
    SLengthListPtr prev_llp;
 
1263
 
 
1264
    if (list == NULL) {
 
1265
        list = llp;
 
1266
    } else {
 
1267
        prev_llp = list;
 
1268
        while ( prev_llp->next  &&  ! s_DoLengthPatternsMatch (prev_llp, llp)) {
 
1269
            prev_llp = prev_llp->next;
 
1270
        }
 
1271
        if (s_DoLengthPatternsMatch (prev_llp, llp)) {
 
1272
            prev_llp->num_appearances ++;
 
1273
            s_LengthListFree (llp);
 
1274
        } else {
 
1275
            prev_llp->next = llp;
 
1276
        }
 
1277
    }
 
1278
    return list;
 
1279
}
 
1280
 
 
1281
 
 
1282
/* This function examines the last SLengthListData structure in list to
 
1283
 * see if it matches llp.  If so, the function increments the value of
 
1284
 * num_appearances for the last SLengthListData structure in list and
 
1285
 * frees llp, otherwise the function appends llp to the end of list.
 
1286
 * The function returns a pointer to the list of SLengthListData structures.
 
1287
 */
 
1288
static SLengthListPtr
 
1289
s_AddPatternRepeat
 
1290
(SLengthListPtr list,
 
1291
 SLengthListPtr llp)
 
1292
{
 
1293
    SLengthListPtr prev_llp;
 
1294
 
 
1295
    if (list == NULL) {
 
1296
        list = llp;
 
1297
    } else {
 
1298
        prev_llp = list;
 
1299
        while ( prev_llp->next != NULL ) {
 
1300
             prev_llp = prev_llp->next;
 
1301
        }
 
1302
        if (s_DoLengthPatternsMatch (prev_llp, llp)) {
 
1303
            prev_llp->num_appearances ++;
 
1304
            s_LengthListFree (llp);
 
1305
        } else {
 
1306
            prev_llp->next = llp;
 
1307
        }
 
1308
    }
 
1309
    return list;
 
1310
}
 
1311
 
 
1312
 
 
1313
/* This set of functions is used for storing and analyzing individual lines
 
1314
 * or tokens from an alignment file.
 
1315
 */
 
1316
 
 
1317
/* This function allocates memory for a new SLineInfo structure and
 
1318
 * initializes the structure with a saved copy of string and the specified
 
1319
 * values of line_num and line_offset.
 
1320
 * The function returns a pointer to the new SLineInfo structure.
 
1321
 */
 
1322
static TLineInfoPtr
 
1323
s_LineInfoNew
 
1324
(char * string,
 
1325
 int    line_num,
 
1326
 int    line_offset)
 
1327
{
 
1328
    TLineInfoPtr lip;
 
1329
 
 
1330
    lip = (TLineInfoPtr) malloc (sizeof (SLineInfo));
 
1331
    if (lip == NULL) {
 
1332
        return NULL;
 
1333
    }
 
1334
    lip->data = strdup (string);
 
1335
    lip->line_num = line_num;
 
1336
    lip->line_offset = line_offset;
 
1337
    lip->delete_me = eFalse;
 
1338
    lip->next = NULL;
 
1339
    return lip;
 
1340
}
 
1341
 
 
1342
 
 
1343
/* This function recursively frees the memory associated with the structures
 
1344
 * and members of the structures in a linked list of SLineInfo structures.
 
1345
 */
 
1346
static void s_LineInfoFree (TLineInfoPtr lip)
 
1347
{
 
1348
    if (lip == NULL) {
 
1349
        return;
 
1350
    }
 
1351
    s_LineInfoFree (lip->next);
 
1352
    lip->next = NULL;
 
1353
    free (lip->data);
 
1354
    free (lip);
 
1355
}
 
1356
 
 
1357
 
 
1358
/* This function deletes from a linked list of SLineInfo structures
 
1359
 * those structures for which the delete_me flag has been set.  The function
 
1360
 * returns a pointer to the beginning of the new list.
 
1361
 */
 
1362
static TLineInfoPtr s_DeleteLineInfos (TLineInfoPtr list)
 
1363
{
 
1364
    TLineInfoPtr prev = NULL;
 
1365
    TLineInfoPtr lip, nextlip;
 
1366
 
 
1367
    lip = list;
 
1368
    while (lip != NULL) {
 
1369
        nextlip = lip->next;
 
1370
        if (lip->delete_me) {
 
1371
            if (prev != NULL) {
 
1372
                prev->next = lip->next;
 
1373
            } else {
 
1374
                list = lip->next;
 
1375
            }
 
1376
            lip->next = NULL;
 
1377
            s_LineInfoFree (lip);
 
1378
        } else {
 
1379
            prev = lip;
 
1380
        }
 
1381
        lip = nextlip;
 
1382
    }
 
1383
    return list;
 
1384
}
 
1385
     
 
1386
 
 
1387
/* This function creates a new SLineInfo structure, populates it with
 
1388
 * a copy of string and the specified line_num and line_offset values,
 
1389
 * and appends it to the end of "list" if list is not NULL.
 
1390
 * The function will return a pointer to the newly created structure
 
1391
 * if list is NULL, otherwise the function will return list.
 
1392
 */
 
1393
static TLineInfoPtr 
 
1394
s_AddLineInfo
 
1395
(TLineInfoPtr list,
 
1396
 char * string,
 
1397
 int    line_num,
 
1398
 int    line_offset)
 
1399
{
 
1400
    TLineInfoPtr lip, p;
 
1401
 
 
1402
    if (string == NULL) {
 
1403
        return list;
 
1404
    }
 
1405
    lip = s_LineInfoNew (string, line_num, line_offset);
 
1406
    if (lip == NULL) {
 
1407
        return NULL;
 
1408
    }
 
1409
    if (list == NULL) {
 
1410
        list = lip;
 
1411
    } else {
 
1412
        p = list;
 
1413
        while (p != NULL  &&  p->next != NULL) {
 
1414
            p = p->next;
 
1415
        }
 
1416
        p->next = lip;
 
1417
    }
 
1418
    return list;
 
1419
}
 
1420
 
 
1421
/* This function creates a new bracketed comment */
 
1422
static TBracketedCommentListPtr s_BracketedCommentListNew 
 
1423
(TBracketedCommentListPtr list,
 
1424
 char * string,
 
1425
 int    line_num,
 
1426
 int    line_offset)
 
1427
{
 
1428
    TBracketedCommentListPtr comment;
 
1429
        
 
1430
    comment = (TBracketedCommentListPtr) malloc (sizeof (SBracketedCommentList));
 
1431
    if (comment == NULL) {
 
1432
        return NULL;
 
1433
    }
 
1434
    comment->comment_lines = s_LineInfoNew (string, line_num, line_offset);
 
1435
    comment->next = NULL;
 
1436
    
 
1437
    if (list != NULL) {
 
1438
        while (list->next != NULL) {
 
1439
                list = list->next;
 
1440
        }
 
1441
        list->next = comment;
 
1442
    }
 
1443
    
 
1444
    return comment;
 
1445
}
 
1446
 
 
1447
/* This function frees a bracketed comment list. */
 
1448
static void s_BracketedCommentListFree (TBracketedCommentListPtr list)
 
1449
{
 
1450
    if (list == NULL) {
 
1451
            return;
 
1452
    }
 
1453
    s_BracketedCommentListFree (list->next);
 
1454
    list->next = NULL;
 
1455
    s_LineInfoFree (list->comment_lines);
 
1456
}
 
1457
 
 
1458
/* This function adds a line to a bracketed comment. */
 
1459
static void s_BracketedCommentListAddLine 
 
1460
(TBracketedCommentListPtr comment,
 
1461
 char                   * string,
 
1462
 int                      line_num,
 
1463
 int                      line_offset)
 
1464
{
 
1465
        if (comment == NULL) {
 
1466
                return;
 
1467
        }
 
1468
 
 
1469
    comment->comment_lines = s_AddLineInfo (comment->comment_lines, string, line_num, line_offset);
 
1470
}
 
1471
 
 
1472
/* This function counts the sequences found in a bracketed comment. */
 
1473
static int s_CountSequencesInBracketedComment (TBracketedCommentListPtr comment)
 
1474
{
 
1475
    TLineInfoPtr lip;
 
1476
    int          num_segments = 0;
 
1477
    EBool        skipped_line_since_last_defline = eTrue;
 
1478
    
 
1479
        if (comment == NULL || comment->comment_lines == NULL) {
 
1480
                return 0;
 
1481
        }
 
1482
        
 
1483
        lip = comment->comment_lines;
 
1484
        /* First line must be left bracket on a line by itself */
 
1485
        if (lip->data[0] != '[' || strspn (lip->data + 1, " \t\r\n") != strlen (lip->data + 1))
 
1486
        {
 
1487
                return 0;
 
1488
        }
 
1489
        lip = lip->next;
 
1490
        while (lip != NULL && lip->next != NULL)
 
1491
        {
 
1492
                if (lip->data[0] == '>')
 
1493
                {
 
1494
                        if (!skipped_line_since_last_defline) 
 
1495
                        {
 
1496
                                return 0;
 
1497
                        }
 
1498
                        else
 
1499
                        {
 
1500
                                num_segments ++;
 
1501
                                skipped_line_since_last_defline = eFalse;
 
1502
                        }
 
1503
                }
 
1504
                else 
 
1505
                {
 
1506
                        skipped_line_since_last_defline = eTrue;
 
1507
                }
 
1508
                lip = lip->next;
 
1509
        }
 
1510
        /* Last line must be right bracket on a line by itself */
 
1511
        /* First line must be left bracket on a line by itself */
 
1512
        if (lip->data[0] != ']' || strspn (lip->data + 1, " \t\r\n") != strlen (lip->data + 1))
 
1513
        {
 
1514
                return 0;
 
1515
        }
 
1516
        
 
1517
        return num_segments;
 
1518
}
 
1519
 
 
1520
/* This function counts the number of sequences that appear in
 
1521
 * bracketed comments.  If the number of sequences is inconsistent,
 
1522
 * the function will issue error messages and return a 1, otherwise
 
1523
 * the function will return the number of sequences that appear in
 
1524
 * each bracketed comment.
 
1525
 */
 
1526
static int s_GetNumSegmentsInAlignment 
 
1527
(TBracketedCommentListPtr comment_list,
 
1528
 FReportErrorFunction     errfunc,
 
1529
 void *                   errdata)
 
1530
{
 
1531
    TBracketedCommentListPtr comment;
 
1532
    TSizeInfoPtr             segcount_list = NULL;
 
1533
    int                      num_segments = 1;
 
1534
    int                      num_segments_this_bracket;
 
1535
    int                      num_segments_expected;
 
1536
    TSizeInfoPtr             best;
 
1537
    
 
1538
        if (comment_list == NULL)
 
1539
        {
 
1540
                return num_segments;
 
1541
        }
 
1542
        
 
1543
        for (comment = comment_list; comment != NULL; comment = comment->next)
 
1544
        {
 
1545
            num_segments_this_bracket = s_CountSequencesInBracketedComment (comment);
 
1546
        segcount_list = s_AddSizeInfoAppearances (segcount_list,
 
1547
                                                  num_segments_this_bracket,
 
1548
                                                  1);
 
1549
        if (comment != comment_list && segcount_list->next != NULL)
 
1550
        {
 
1551
            best = s_GetMostPopularSizeInfo (segcount_list);
 
1552
            num_segments_expected = best->size_value;
 
1553
 
 
1554
                if (num_segments_expected != num_segments_this_bracket)
 
1555
                {
 
1556
                        s_ReportBadNumSegError (comment->comment_lines->line_num,
 
1557
                                                num_segments_this_bracket, num_segments_expected,
 
1558
                                                errfunc, errdata);
 
1559
                }
 
1560
        }
 
1561
        }
 
1562
        if (segcount_list != NULL && segcount_list->next == NULL && segcount_list->size_value > 0)
 
1563
        {
 
1564
                num_segments = segcount_list->size_value;
 
1565
        }
 
1566
        s_SizeInfoFree (segcount_list);
 
1567
        return num_segments;
 
1568
}
 
1569
 
 
1570
/* This function gets a list of the offsets of the 
 
1571
 * sequences in bracketed comments.
 
1572
 */
 
1573
static TIntLinkPtr GetSegmentOffsetList (TBracketedCommentListPtr comment_list)
 
1574
{
 
1575
        TIntLinkPtr              new_offset, offset_list = NULL;
 
1576
        TBracketedCommentListPtr comment;
 
1577
        TLineInfoPtr             lip;
 
1578
 
 
1579
    if (comment_list == NULL) 
 
1580
    {
 
1581
        return NULL;
 
1582
    }
 
1583
    
 
1584
    for (comment = comment_list; comment != NULL; comment = comment->next)
 
1585
    {
 
1586
        if (s_CountSequencesInBracketedComment (comment) == 0) 
 
1587
        {
 
1588
                continue;
 
1589
        }
 
1590
        for (lip = comment->comment_lines; lip != NULL; lip = lip->next)
 
1591
        {
 
1592
                if (lip->data != NULL && lip->data[0] == '>') 
 
1593
                {
 
1594
                new_offset = s_IntLinkNew (lip->line_num + 1, offset_list);
 
1595
                if (offset_list == NULL) offset_list = new_offset;
 
1596
                }
 
1597
        }
 
1598
    }
 
1599
    return offset_list;
 
1600
}
 
1601
 
 
1602
static char * s_TokenizeString (char * str, char *delimiter, char **last)
 
1603
{
 
1604
    int skip;
 
1605
    int length;
 
1606
 
 
1607
    if (str == NULL) {
 
1608
        str = *last;
 
1609
    }
 
1610
    if (delimiter == NULL) {
 
1611
        *last = NULL;
 
1612
        return NULL;
 
1613
    }
 
1614
 
 
1615
    if (str == NULL || *str == 0) {
 
1616
        return NULL;
 
1617
    }
 
1618
    skip = strspn (str, delimiter);
 
1619
    str += skip;
 
1620
    length = strcspn (str, delimiter);
 
1621
    *last = str + length;
 
1622
    if (**last != 0) {
 
1623
        **last = 0;
 
1624
        (*last) ++;
 
1625
    }
 
1626
    return str;
 
1627
}
 
1628
  
 
1629
 
 
1630
/* This function creates a new list of SLineInfo structures by tokenizing
 
1631
 * each data element from line_list into multiple tokens at whitespace.
 
1632
 * The function returns a pointer to the new list.  The original list is
 
1633
 * unchanged.
 
1634
 */
 
1635
static TLineInfoPtr s_BuildTokenList (TLineInfoPtr line_list)
 
1636
{
 
1637
    TLineInfoPtr first_token, lip;
 
1638
    char *       tmp;
 
1639
    char *       piece;
 
1640
    char *       last;
 
1641
    int          line_pos;
 
1642
 
 
1643
    first_token = NULL;
 
1644
 
 
1645
    for (lip = line_list;  lip != NULL;  lip = lip->next) {
 
1646
        if (lip->data != NULL  &&  (tmp = strdup (lip->data)) != NULL) {
 
1647
            piece = s_TokenizeString (tmp, " \t\r", &last);
 
1648
            while (piece != NULL) {
 
1649
                line_pos = piece - tmp;
 
1650
                line_pos += lip->line_offset;
 
1651
                first_token = s_AddLineInfo (first_token, piece, 
 
1652
                                             lip->line_num,
 
1653
                                             line_pos);
 
1654
                piece = s_TokenizeString (NULL, " \t\r", &last);
 
1655
            }
 
1656
            free (tmp);
 
1657
        }
 
1658
    }
 
1659
    return first_token;
 
1660
}
 
1661
 
 
1662
 
 
1663
/* This function takes a list of SLineInfo structures, allocates memory
 
1664
 * to hold their contents contiguously, and stores their contents, minus
 
1665
 * the whitespace, in the newly allocated memory.
 
1666
 * The function returns a pointer to this newly allocated memory.
 
1667
 */
 
1668
static char * s_LineInfoMergeAndStripSpaces (TLineInfoPtr list)
 
1669
{
 
1670
    TLineInfoPtr lip;
 
1671
    int          len;
 
1672
    char *       result;
 
1673
    char *       cp_to;
 
1674
    char *       cp_from;
 
1675
 
 
1676
    if (list == NULL) {
 
1677
        return NULL;
 
1678
    }
 
1679
    len = 0;
 
1680
    for (lip = list;  lip != NULL;  lip = lip->next) {
 
1681
        if (lip->data != NULL) {
 
1682
            len += strlen (lip->data);
 
1683
        }
 
1684
    }
 
1685
    result = (char *) malloc (len + 1);
 
1686
    if (result == NULL) {
 
1687
        return result;
 
1688
    }
 
1689
    cp_to = result;
 
1690
    for (lip = list;  lip != NULL;  lip = lip->next) {
 
1691
        if (lip->data != NULL) {
 
1692
            cp_from = lip->data;
 
1693
            while (*cp_from != 0) {
 
1694
                if (! isspace ((int )*cp_from)) {
 
1695
                    *cp_to = *cp_from;
 
1696
                    cp_to ++;
 
1697
                }
 
1698
                cp_from ++;
 
1699
            }
 
1700
        }
 
1701
    }
 
1702
    *cp_to = 0;
 
1703
    return result;
 
1704
}
 
1705
 
 
1706
 
 
1707
/* The following functions are used to manage the SLineInfoReader
 
1708
 * structure.  The intention is to allow the user to access the data
 
1709
 * from a linked list of SLineInfo structures using a given position
 
1710
 * in the data based on the number of sequence data characters rather than 
 
1711
 * any particular line number or position in the line.  This is useful
 
1712
 * for matching up a data position in a record with a match character with
 
1713
 * the same data position in the first or master record.  This is also useful
 
1714
 * for determining how to interpret special characters that may have
 
1715
 * context-sensitive meanings.  For example, a ? could indicate a missing 
 
1716
 * character if it is inside a sequence but indicate a gap if it is outside
 
1717
 * a sequence.
 
1718
 */
 
1719
 
 
1720
/* This function is used to advance the current data position pointer
 
1721
 * for a SLineInfoReader structure past white space and blank lines
 
1722
 * in sequence data.
 
1723
 */
 
1724
static void s_LineInfoReaderAdvancePastSpace (TLineInfoReaderPtr lirp)
 
1725
{
 
1726
    if (lirp->curr_line_pos == NULL) {
 
1727
        return;
 
1728
    }
 
1729
    while ( isspace ((int ) *lirp->curr_line_pos)
 
1730
           ||  *lirp->curr_line_pos == 0) {
 
1731
        while ( isspace ((int )*lirp->curr_line_pos)) {
 
1732
            lirp->curr_line_pos ++;
 
1733
        }
 
1734
        if (*lirp->curr_line_pos == 0) {
 
1735
            lirp->curr_line = lirp->curr_line->next;
 
1736
            while (lirp->curr_line != NULL
 
1737
                   &&  lirp->curr_line->data == NULL) {
 
1738
                lirp->curr_line = lirp->curr_line->next;
 
1739
            }
 
1740
            if (lirp->curr_line == NULL) {
 
1741
                lirp->curr_line_pos = NULL;
 
1742
                return;
 
1743
            } else {
 
1744
                lirp->curr_line_pos = lirp->curr_line->data;
 
1745
            }
 
1746
        }
 
1747
    }
 
1748
}
 
1749
 
 
1750
 
 
1751
/* This function sets the current data position pointer to the first
 
1752
 * non-whitespace character in the sequence data.
 
1753
 */
 
1754
static void s_LineInfoReaderReset (TLineInfoReaderPtr lirp)
 
1755
{
 
1756
    if (lirp == NULL) {
 
1757
        return;
 
1758
    }
 
1759
    lirp->curr_line = lirp->first_line;
 
1760
 
 
1761
    while (lirp->curr_line != NULL  &&  lirp->curr_line->data == NULL) {
 
1762
        lirp->curr_line = lirp->curr_line->next;
 
1763
    }
 
1764
    if (lirp->curr_line == NULL) {
 
1765
        lirp->curr_line_pos = NULL;
 
1766
        lirp->data_pos = -1;
 
1767
    } else {
 
1768
        lirp->curr_line_pos = lirp->curr_line->data;
 
1769
        s_LineInfoReaderAdvancePastSpace (lirp);
 
1770
        if (lirp->curr_line_pos == NULL) {
 
1771
            lirp->data_pos = -1;
 
1772
        } else {
 
1773
            lirp->data_pos = 0;
 
1774
        }
 
1775
    }
 
1776
}
 
1777
 
 
1778
 
 
1779
/* This function creates a new SLineInfoReader structure and initializes
 
1780
 * its member variables.  The current data position pointer is set to the
 
1781
 * first non-whitespace character in the sequence data, and the data position
 
1782
 * counter is set to zero.  The function returns a pointer to the new
 
1783
 * LineInfoReader data structure.
 
1784
 */
 
1785
static TLineInfoReaderPtr s_LineInfoReaderNew (TLineInfoPtr line_list)
 
1786
{
 
1787
    TLineInfoReaderPtr lirp;
 
1788
 
 
1789
    if (line_list == NULL) {
 
1790
        return NULL;
 
1791
    }
 
1792
    lirp = (TLineInfoReaderPtr) malloc (sizeof (SLineInfoReader));
 
1793
    if (lirp == NULL) {
 
1794
        return NULL;
 
1795
    }
 
1796
 
 
1797
    lirp->first_line = line_list;
 
1798
    s_LineInfoReaderReset (lirp);
 
1799
    return lirp;
 
1800
}
 
1801
 
 
1802
 
 
1803
/* This function safely interprets the current line number of the
 
1804
 * SLineInfoReader structure.  If the structure is NULL or the
 
1805
 * current line is NULL (usually because the data position has been
 
1806
 * advanced to the end of the available sequence data), the function
 
1807
 * returns -1, since the current data position does not actually exist.
 
1808
 * Otherwise, the line number of the character at the current data position
 
1809
 * is returned.
 
1810
 */
 
1811
static int  s_LineInfoReaderGetCurrentLineNumber (TLineInfoReaderPtr lirp)
 
1812
{
 
1813
    if (lirp == NULL  ||  lirp->curr_line == NULL) {
 
1814
        return -1;
 
1815
    } else {
 
1816
        return lirp->curr_line->line_num;
 
1817
    }
 
1818
}
 
1819
 
 
1820
 
 
1821
/* This function safely interprets the position of the current data position
 
1822
 * of the SLineInfoReader structure.  If the structure is NULL or the
 
1823
 * current line is NULL or the current line position is NULL (usually because
 
1824
 * the data position has been advanced to the end of the available sequence
 
1825
 * data), the function returns -1, since the current data position does not 
 
1826
 * actually exist.
 
1827
 * Otherwise, the position within the line of the character at the current 
 
1828
 * data position is returned.
 
1829
 */
 
1830
static int  s_LineInfoReaderGetCurrentLineOffset (TLineInfoReaderPtr lirp)
 
1831
{
 
1832
    if (lirp == NULL  ||  lirp->curr_line == NULL 
 
1833
        ||  lirp->curr_line_pos == NULL) {
 
1834
        return -1;
 
1835
    } else {
 
1836
        return lirp->curr_line->line_offset + lirp->curr_line_pos 
 
1837
                     - lirp->curr_line->data;
 
1838
    }
 
1839
}
 
1840
 
 
1841
 
 
1842
/* This function frees the memory associated with the SLineInfoReader
 
1843
 * structure.  Notice that this function does NOT free the SLineInfo list.
 
1844
 * This is by design.
 
1845
 */
 
1846
static void s_LineInfoReaderFree (TLineInfoReaderPtr lirp)
 
1847
{
 
1848
    if (lirp == NULL) {
 
1849
        return;
 
1850
    }
 
1851
    free (lirp);
 
1852
    lirp = NULL;
 
1853
}
 
1854
 
 
1855
 
 
1856
/* This function retrieves the "pos"th sequence data character from the lines
 
1857
 * of sequence data.  If the data position requested is greater than the
 
1858
 * current position, the current data pointer will be advanced until the
 
1859
 * current position is the requested position or there is no more data.  If
 
1860
 * there is no more data, the function returns a 0.  If the data position
 
1861
 * requested is lower than the current position, the current position is reset
 
1862
 * to the beginning of the sequence and advanced from there.
 
1863
 * As a result, it is clearly more efficient to read the data in the forward
 
1864
 * direction, but it is still possible to access the data randomly.
 
1865
 */
 
1866
static char 
 
1867
s_FindNthDataChar
 
1868
(TLineInfoReaderPtr lirp,
 
1869
 int  pos)
 
1870
{
 
1871
    if (lirp == NULL  ||  lirp->first_line == NULL  ||  pos < 0
 
1872
        ||  lirp->data_pos == -1) {
 
1873
        return 0;
 
1874
    }
 
1875
 
 
1876
    if (lirp->data_pos == pos) {
 
1877
        if (lirp->curr_line_pos == NULL) {
 
1878
            return 0;
 
1879
        } else {
 
1880
            return *lirp->curr_line_pos;
 
1881
        }
 
1882
    }
 
1883
    if (lirp->data_pos > pos) {
 
1884
        s_LineInfoReaderReset (lirp);
 
1885
    }
 
1886
     
 
1887
    while (lirp->data_pos < pos  &&  lirp->curr_line != NULL) {
 
1888
        lirp->curr_line_pos ++;
 
1889
        /* skip over spaces, progress to next line if necessary */
 
1890
        s_LineInfoReaderAdvancePastSpace (lirp);
 
1891
        lirp->data_pos ++;
 
1892
    }
 
1893
    if (lirp->curr_line_pos != NULL) {
 
1894
        return *lirp->curr_line_pos;
 
1895
    } else {
 
1896
        return 0;
 
1897
    }
 
1898
}
 
1899
 
 
1900
 
 
1901
/* The following functions are used to manage the SStringCount structure.
 
1902
 * These functions are useful for determining whether a string is unique
 
1903
 * or whether only one string is used for a particular purpose.
 
1904
 * The structure also tracks the line numbers on which a particular string
 
1905
 * appeared.
 
1906
 */
 
1907
 
 
1908
/* This function allocates memory for a new SStringCount structure,
 
1909
 * initializes its member variables.  The function also places the 
 
1910
 * structure at the end of list if list is not NULL.
 
1911
 * The function returns a pointer to the newly allocated SStringCount
 
1912
 * structure.
 
1913
 */
 
1914
static TStringCountPtr s_StringCountNew (TStringCountPtr list)
 
1915
{
 
1916
    TStringCountPtr new_item, last;
 
1917
 
 
1918
    new_item = (TStringCountPtr) malloc (sizeof (SStringCount));
 
1919
    if (new_item == NULL) {
 
1920
        return NULL;
 
1921
    }
 
1922
    new_item->string          = NULL;
 
1923
    new_item->num_appearances = 0;
 
1924
    new_item->line_numbers    = NULL;
 
1925
    new_item->next            = NULL;
 
1926
 
 
1927
    last = list;
 
1928
    while (last != NULL && last->next != NULL) {
 
1929
        last = last->next;
 
1930
    }
 
1931
    if (last != NULL) {
 
1932
        last->next = new_item;
 
1933
    }
 
1934
    return new_item;
 
1935
}
 
1936
 
 
1937
 
 
1938
/* This function recursively frees data associated with the structures
 
1939
 * and structure member variables in a linked list of SStringCount
 
1940
 * structures.
 
1941
 */
 
1942
static void s_StringCountFree (TStringCountPtr list)
 
1943
{
 
1944
    if (list == NULL) {
 
1945
        return;
 
1946
    }
 
1947
    s_StringCountFree (list->next);
 
1948
    s_IntLinkFree (list->line_numbers);
 
1949
    free (list);
 
1950
}
 
1951
 
 
1952
 
 
1953
/* This function searches list to see if the string matches any of the
 
1954
 * existing entries.  If so, the num_appearances value for that entry is
 
1955
 * increased and the line_num is added to that entry's list of line numbers.
 
1956
 * Otherwise a new entry is created at the end of the list.
 
1957
 * The function returns list if list was not NULL, or a pointer to the
 
1958
 * newly created SStringCount structure otherwise.
 
1959
 */
 
1960
static TStringCountPtr s_AddStringCount (
 
1961
  char *          string,
 
1962
  int             line_num,
 
1963
  TStringCountPtr list
 
1964
)
 
1965
{
 
1966
    TStringCountPtr  add_to, last;
 
1967
    TIntLinkPtr      new_offset;
 
1968
 
 
1969
    if (string == NULL) {
 
1970
        for (add_to = list;
 
1971
             add_to != NULL  &&  add_to->string != NULL;
 
1972
             add_to = add_to->next) {
 
1973
            last = add_to;
 
1974
        }
 
1975
    } else {
 
1976
        for (add_to = list;
 
1977
             add_to != NULL
 
1978
               &&  (add_to->string == NULL
 
1979
                 ||  strcmp (string, add_to->string) != 0);
 
1980
             add_to = add_to->next) {
 
1981
            last = add_to;
 
1982
        }
 
1983
    }
 
1984
    
 
1985
    if (add_to == NULL) {
 
1986
        add_to = s_StringCountNew (list);
 
1987
        if (list == NULL) list = add_to;
 
1988
        if (add_to != NULL) {
 
1989
            add_to->string = string;
 
1990
        }
 
1991
    }
 
1992
    if (add_to != NULL) {
 
1993
        add_to->num_appearances ++;
 
1994
        new_offset = s_IntLinkNew (line_num, add_to->line_numbers);
 
1995
        if (add_to->line_numbers == NULL) {
 
1996
            add_to->line_numbers = new_offset;
 
1997
        }
 
1998
    }
 
1999
    return list;   
 
2000
}
 
2001
 
 
2002
/* The following functions are replacements for strncasecmp and strcasecmp */
 
2003
 
 
2004
/* This function returns -1 if str1 is less than str2 in the first cmp_count
 
2005
 * characters (using case-insensitive comparisons), 0 if they are equal,
 
2006
 * and 1 if str1 is greater than str2.
 
2007
 */
 
2008
static int s_StringNICmp (char * str1, char *str2, int cmp_count)
 
2009
{
 
2010
    char * cp1;
 
2011
    char * cp2;
 
2012
    int    char_count, diff;
 
2013
 
 
2014
    if (str1 == NULL && str2 == NULL) {
 
2015
        return 0;
 
2016
    }
 
2017
    if (str1 == NULL) {
 
2018
        return -1;
 
2019
    }
 
2020
    if (str2 == NULL) {
 
2021
        return 1;
 
2022
    }
 
2023
    cp1 = str1;
 
2024
    cp2 = str2;
 
2025
    char_count = 0;
 
2026
    while (*cp1 != 0  &&  *cp2 != 0  &&  char_count < cmp_count) {
 
2027
        diff = toupper ((int) *cp1) - toupper ((int) *cp2);
 
2028
        if (diff != 0) {
 
2029
            return diff;
 
2030
        }
 
2031
        char_count ++;
 
2032
        cp1++;
 
2033
        cp2++;
 
2034
    }
 
2035
    if (char_count == cmp_count) {
 
2036
        return 0;
 
2037
    } else if (*cp1 == 0  &&  *cp2 != 0) {
 
2038
        return -1;
 
2039
    } else if (*cp1 != 0  && *cp2 == 0) {
 
2040
        return 1;
 
2041
    } else {
 
2042
        return 0;
 
2043
    }
 
2044
}
 
2045
 
 
2046
 
 
2047
/* This function returns -1 if str1 is less than str2 using case-insensitive
 
2048
 * comparisons), 0 if they are equal, and 1 if str1 is greater than str2.
 
2049
 */
 
2050
static int s_StringICmp (char * str1, char *str2)
 
2051
{
 
2052
    char * cp1;
 
2053
    char * cp2;
 
2054
    int    diff;
 
2055
 
 
2056
    if (str1 == NULL && str2 == NULL) {
 
2057
        return 0;
 
2058
    }
 
2059
    if (str1 == NULL) {
 
2060
        return -1;
 
2061
    }
 
2062
    if (str2 == NULL) {
 
2063
        return 1;
 
2064
    }
 
2065
    cp1 = str1;
 
2066
    cp2 = str2;
 
2067
    while (*cp1 != 0  &&  *cp2 != 0) {
 
2068
        diff = toupper ((int) *cp1) - toupper ((int) *cp2);
 
2069
        if (diff != 0) {
 
2070
            return diff;
 
2071
        }
 
2072
        cp1++;
 
2073
        cp2++;
 
2074
    }
 
2075
    if (*cp1 == 0  &&  *cp2 != 0) {
 
2076
        return -1;
 
2077
    } else if (*cp1 != 0  && *cp2 == 0) {
 
2078
        return 1;
 
2079
    } else {
 
2080
        return 0;
 
2081
    }
 
2082
}
 
2083
 
 
2084
 
 
2085
/* The following functions are used to analyze specific kinds of lines
 
2086
 * found in alignment files for information regarding the number of
 
2087
 * expected sequences, the expected length of those sequences, and the
 
2088
 * characters used to indicate missing, gap, and match characters.
 
2089
 */
 
2090
 
 
2091
/* This function reads two numbers separated by whitespace from the
 
2092
 * beginning of the string and uses them to set the expected number of
 
2093
 * sequences and the expected number of characters per sequence.
 
2094
 */
 
2095
static void
 
2096
s_GetFASTAExpectedNumbers
 
2097
(char *           str,
 
2098
 SAlignRawFilePtr afrp)
 
2099
{
 
2100
    char *  cp;
 
2101
    char *  cpend;
 
2102
    char    replace;
 
2103
    int     first, second;
 
2104
 
 
2105
    if (str == NULL  ||  afrp == NULL) {
 
2106
        return;
 
2107
    }
 
2108
    cp = str;
 
2109
    while (! isdigit ((int )*cp)  &&  *cp != 0) {
 
2110
        cp++;
 
2111
    }
 
2112
 
 
2113
    cpend = cp;
 
2114
    while (isdigit ((int )*cpend)  &&  *cpend != 0) {
 
2115
        cpend++;
 
2116
    }
 
2117
    if (cp == cpend) {
 
2118
        return;
 
2119
    }
 
2120
    replace = *cpend;
 
2121
    *cpend = 0;
 
2122
    first = atol (cp);
 
2123
    *cpend = replace;
 
2124
 
 
2125
    cp = cpend;
 
2126
    while (! isdigit ((int )*cp)  &&  *cp != 0) {
 
2127
        cp++;
 
2128
    }
 
2129
 
 
2130
    cpend = cp;
 
2131
    while (isdigit ((int )*cpend)  &&  *cpend != 0) {
 
2132
        cpend++;
 
2133
    }
 
2134
    if (cp == cpend) {
 
2135
        return;
 
2136
    }
 
2137
    replace = *cpend;
 
2138
    *cpend = 0;
 
2139
    second = atol (cp);
 
2140
    *cpend = replace;
 
2141
 
 
2142
    if (first > 0  &&  second > 0) {
 
2143
        afrp->expected_num_sequence = first;
 
2144
        afrp->expected_sequence_len = second;
 
2145
    }
 
2146
  
 
2147
}
 
2148
 
 
2149
 
 
2150
/* This function examines the string str to see if it begins with two
 
2151
 * numbers separated by whitespace.  The function returns eTrue if so,
 
2152
 * otherwise it returns eFalse.
 
2153
 */
 
2154
static EBool s_IsTwoNumbersSeparatedBySpace (char * str)
 
2155
{
 
2156
    char * cp;
 
2157
    EBool  found_first_number = eFalse;
 
2158
    EBool  found_dividing_space = eFalse;
 
2159
    EBool  found_second_number = eFalse;
 
2160
    EBool  found_second_number_end = eFalse;
 
2161
 
 
2162
    if (str == NULL) {
 
2163
        return eFalse;
 
2164
    }
 
2165
    cp = str;
 
2166
    while (*cp != 0) {
 
2167
        if (! isdigit ((int )*cp)  &&  ! isspace ((int )*cp)) {
 
2168
            return eFalse;
 
2169
        }
 
2170
        if (! found_first_number) {
 
2171
            if (! isdigit ((int )*cp)) {
 
2172
                return eFalse;
 
2173
            }
 
2174
            found_first_number = eTrue;
 
2175
        } else if (! found_dividing_space) {
 
2176
            if ( isspace ((int ) *cp)) {
 
2177
                found_dividing_space = eTrue;
 
2178
            } else if ( ! isdigit ((int )*cp)) {
 
2179
                return eFalse;
 
2180
            }
 
2181
        } else if (! found_second_number) {
 
2182
            if ( isdigit ((int )*cp)) {
 
2183
                found_second_number = eTrue;
 
2184
            } else if (! isspace ((int ) *cp)) {
 
2185
                return eFalse;
 
2186
            }
 
2187
        } else if (! found_second_number_end) {
 
2188
            if ( isspace ((int ) *cp)) {
 
2189
                found_second_number_end = eTrue;
 
2190
            } else if (! isdigit ((int )*cp)) {
 
2191
                return eFalse;
 
2192
            }
 
2193
        } else if (! isspace ((int ) *cp)) {
 
2194
            return eFalse;
 
2195
        }
 
2196
        cp++;
 
2197
    }
 
2198
    if (found_second_number) {
 
2199
        return eTrue;
 
2200
    }
 
2201
    return eFalse;
 
2202
}
 
2203
 
 
2204
 
 
2205
/* This function finds a value name in a string, looks for an equals sign
 
2206
 * after the value name, and then looks for an integer value after the
 
2207
 * equals sign.  If the integer value is found, the function copies the
 
2208
 * integer value into the val location and returns eTrue, otherwise the
 
2209
 * function returns eFalse.
 
2210
 */
 
2211
static EBool 
 
2212
s_GetOneNexusSizeComment 
 
2213
(char * str,
 
2214
 char * valname, 
 
2215
 int  * val)
 
2216
{
 
2217
    char   buf[MAX_PRINTED_INT_LEN_PLUS_ONE];
 
2218
    char * cpstart;
 
2219
    char * cpend;
 
2220
    int    maxlen;
 
2221
 
 
2222
    if (str == NULL  ||  valname == NULL  ||  val == NULL) {
 
2223
        return eFalse;
 
2224
    }
 
2225
 
 
2226
    cpstart = strstr (str, valname);
 
2227
    if (cpstart == NULL) {
 
2228
        return eFalse;
 
2229
    }
 
2230
    cpstart += strlen (valname);
 
2231
    while (*cpstart != 0  &&  isspace ((int )*cpstart)) {
 
2232
        cpstart++;
 
2233
    }
 
2234
    if (*cpstart != '=') {
 
2235
        return eFalse;
 
2236
    }
 
2237
    cpstart ++;
 
2238
    while (*cpstart != 0  &&  isspace ((int )*cpstart)) {
 
2239
        cpstart++;
 
2240
    }
 
2241
 
 
2242
    if (! isdigit ((int )*cpstart)) {
 
2243
        return eFalse;
 
2244
    }
 
2245
    cpend = cpstart + 1;
 
2246
    while ( *cpend != 0  &&  isdigit ((int )*cpend)) {
 
2247
        cpend ++;
 
2248
    }
 
2249
    maxlen = cpend - cpstart;
 
2250
    if (maxlen > kMaxPrintedIntLen) maxlen = kMaxPrintedIntLen;
 
2251
 
 
2252
    strncpy (buf, cpstart, maxlen);
 
2253
    buf [maxlen] = 0;
 
2254
    *val = atoi (buf);
 
2255
    return eTrue;
 
2256
}
 
2257
 
 
2258
 
 
2259
/* This function looks for Nexus-style comments to indicate the number of
 
2260
 * sequences and the number of characters per sequence expected from this
 
2261
 * alignment file.  If the function finds these comments, it returns eTrue,
 
2262
 * otherwise it returns eFalse.
 
2263
 */
 
2264
static void 
 
2265
s_GetNexusSizeComments 
 
2266
(char *           str,
 
2267
 EBool *          found_ntax,
 
2268
 EBool *          found_nchar,
 
2269
 SAlignRawFilePtr afrp)
 
2270
{
 
2271
    int  num_sequences;
 
2272
    int  num_chars;
 
2273
  
 
2274
    if (str == NULL  ||  found_nchar == NULL  
 
2275
        ||  found_ntax == NULL  ||  afrp == NULL) {
 
2276
        return;
 
2277
    }
 
2278
    if (! *found_ntax  && 
 
2279
        (s_GetOneNexusSizeComment (str, "ntax", &num_sequences)
 
2280
        ||   s_GetOneNexusSizeComment (str, "NTAX", &num_sequences))) {
 
2281
        afrp->expected_num_sequence = num_sequences;
 
2282
        *found_ntax = eTrue;
 
2283
    }
 
2284
    if (! *found_nchar  &&
 
2285
        (s_GetOneNexusSizeComment (str, "nchar", &num_chars)
 
2286
        ||  s_GetOneNexusSizeComment (str, "NCHAR", &num_chars))) {
 
2287
        afrp->expected_sequence_len = num_chars;
 
2288
        *found_nchar = eTrue;
 
2289
    }
 
2290
}
 
2291
 
 
2292
 
 
2293
/* This function looks for characters in Nexus-style comments to 
 
2294
 * indicate values for specific kinds of characters (match, missing, gap...).
 
2295
 * If the string str contains val_name followed by an equals sign, the function
 
2296
 * will return the first non-whitespace character following the equals sign,
 
2297
 * otherwise the function will return a 0.
 
2298
 */
 
2299
static char GetNexusTypechar (char * str, char * val_name)
 
2300
{
 
2301
    char * cp;
 
2302
    char * cpend;
 
2303
 
 
2304
    if (str == NULL  ||  val_name == NULL) {
 
2305
        return 0;
 
2306
    }
 
2307
    cpend = strstr (str, ";");
 
2308
    if (cpend == NULL) {
 
2309
        return 0;
 
2310
    }
 
2311
    cp = strstr (str, val_name);
 
2312
    if (cp == NULL || cp > cpend) {
 
2313
        return 0;
 
2314
    }
 
2315
    cp += strlen (val_name);
 
2316
    while ( isspace ((int )*cp)) {
 
2317
        cp ++;
 
2318
    }
 
2319
    if (*cp != '=') {
 
2320
        return 0;
 
2321
    }
 
2322
    cp++;
 
2323
    while ( isspace ((int )*cp) || *cp == '\'') {
 
2324
        cp ++;
 
2325
    }
 
2326
    return *cp;
 
2327
}
 
2328
 
 
2329
 
 
2330
/* This function reads a Nexus-style comment line for the characters 
 
2331
 * specified for missing, match, and gap and compares the characters from
 
2332
 * the comment with the characters specified in sequence_info.  If any
 
2333
 * discrepancies are found, the function reports the errors and returns eFalse,
 
2334
 * otherwise the function returns eTrue.
 
2335
 */ 
 
2336
static EBool s_CheckNexusCharInfo 
 
2337
(char *               str,
 
2338
 TSequenceInfoPtr     sequence_info,
 
2339
 FReportErrorFunction errfunc,
 
2340
 void *              errdata)
 
2341
{
 
2342
    char * cp;
 
2343
    char   c;
 
2344
 
 
2345
    if (str == NULL  ||  sequence_info == NULL) {
 
2346
        return eFalse;
 
2347
    }
 
2348
 
 
2349
    cp = strstr (str, "format ");
 
2350
    if (cp == NULL) {
 
2351
        cp = strstr (str, "FORMAT ");
 
2352
    }
 
2353
    if (cp == NULL) {
 
2354
        return eFalse;
 
2355
    }
 
2356
 
 
2357
    if (errfunc == NULL) {
 
2358
        return eTrue;
 
2359
    }
 
2360
 
 
2361
    c = GetNexusTypechar (cp + 7, "missing");
 
2362
    if (c == 0) {
 
2363
        c = GetNexusTypechar (cp + 7, "MISSING");
 
2364
    }
 
2365
    if (c != 0  &&  sequence_info->missing != NULL
 
2366
        &&  strchr (sequence_info->missing, c) == NULL)
 
2367
    {
 
2368
        s_ReportCharCommentError (sequence_info->missing, c, "MISSING",
 
2369
                                errfunc, errdata);
 
2370
    }
 
2371
 
 
2372
    c = GetNexusTypechar (cp + 7, "gap");
 
2373
    if (c == 0) {
 
2374
        c = GetNexusTypechar (cp + 7, "GAP");
 
2375
    }
 
2376
    if (c != 0  &&  sequence_info->middle_gap != NULL
 
2377
        &&  strchr (sequence_info->middle_gap, c) == NULL)
 
2378
    {
 
2379
        s_ReportCharCommentError (sequence_info->middle_gap, c, "GAP",
 
2380
                                errfunc, errdata);
 
2381
    }
 
2382
 
 
2383
    c = GetNexusTypechar (cp + 7, "match");
 
2384
    if (c == 0) {
 
2385
        c = GetNexusTypechar (cp + 7, "MATCH");
 
2386
    }
 
2387
    if (c != 0  &&  sequence_info->match != NULL
 
2388
        &&  strchr (sequence_info->match, c) == NULL)
 
2389
    {
 
2390
        s_ReportCharCommentError (sequence_info->match, c, "MATCH",
 
2391
                                errfunc, errdata);
 
2392
    }
 
2393
    return eTrue;
 
2394
} 
 
2395
 
 
2396
 
 
2397
/* This function examines the string str to see if it consists entirely of
 
2398
 * asterisks, colons, periods, and whitespace.  If so, this line is assumed
 
2399
 * to be a Clustal-style consensus line and the function returns eTrue.
 
2400
 * otherwise the function returns false;
 
2401
 */
 
2402
static EBool s_IsConsensusLine (char * str)
 
2403
{
 
2404
    if (str == NULL 
 
2405
        ||  strspn (str, "*:. \t\r\n") < strlen (str)
 
2406
        ||  strchr (str, '*') == NULL) {
 
2407
        return eFalse;
 
2408
    } else {
 
2409
        return eTrue;
 
2410
    } 
 
2411
}
 
2412
 
 
2413
 
 
2414
/* This function identifies lines that begin with a NEXUS keyword and end
 
2415
 * with a semicolon - they will not contain sequence data.  The function
 
2416
 * returns eTrue if the line contains only a NEXUS comment, eFalse otherwise.
 
2417
 */
 
2418
static EBool s_SkippableNexusComment (char *str)
 
2419
{
 
2420
    char * last_semicolon;
 
2421
 
 
2422
    if (str == NULL) {
 
2423
        return eFalse;
 
2424
    }
 
2425
    last_semicolon = strrchr (str, ';');
 
2426
    if (last_semicolon == NULL
 
2427
        ||  strspn (last_semicolon + 1, " \t\r") != strlen (last_semicolon + 1)
 
2428
        ||  strchr (str, ';') != last_semicolon) {
 
2429
        return eFalse;
 
2430
    }
 
2431
    if (s_StringNICmp (str, "format ", 7) == 0
 
2432
        ||  s_StringNICmp (str, "dimensions ", 11) == 0
 
2433
        ||  s_StringNICmp (str, "dimensions ", 11) == 0
 
2434
        ||  s_StringNICmp (str, "options ", 8) == 0
 
2435
        ||  s_StringNICmp (str, "begin characters", 16) == 0
 
2436
        ||  s_StringNICmp (str, "begin data", 10) == 0) {
 
2437
        return eTrue;
 
2438
    } else {
 
2439
        return eFalse;
 
2440
    }
 
2441
}
 
2442
 
 
2443
 
 
2444
/* This function determines whether the contents of str are "skippable"
 
2445
 * in that they do not contain sequence data and therefore should not be
 
2446
 * considered part of any block patterns or sequence data.
 
2447
 */
 
2448
static EBool s_SkippableString (char * str)
 
2449
{
 
2450
    if (str == NULL
 
2451
        ||  s_StringNICmp (str, "matrix", 6) == 0
 
2452
        ||  s_StringNICmp (str, "#NEXUS", 6) == 0
 
2453
        ||  s_StringNICmp (str, "CLUSTAL W", 8) == 0
 
2454
        ||  s_SkippableNexusComment (str)
 
2455
        ||  s_IsTwoNumbersSeparatedBySpace (str)
 
2456
        ||  s_IsConsensusLine (str)
 
2457
        ||  str [0] == ';') {
 
2458
        return eTrue;
 
2459
    } else {
 
2460
        return eFalse;
 
2461
    }
 
2462
}
 
2463
 
 
2464
 
 
2465
/* This function determines whether or not str contains a blank line.
 
2466
 */
 
2467
static EBool s_IsBlank (char * str)
 
2468
{
 
2469
    size_t len;
 
2470
 
 
2471
    if (str == NULL) {
 
2472
        return eTrue;
 
2473
    }
 
2474
    len = strspn (str, " \t\r");
 
2475
    if (len == strlen (str)) {
 
2476
        return eTrue;
 
2477
    }
 
2478
    return eFalse;
 
2479
}
 
2480
 
 
2481
 
 
2482
/* This function determines whether or not linestring contains a line
 
2483
 * indicating the end of sequence data (organism information and definition
 
2484
 * lines may occur after this line).
 
2485
 */
 
2486
static EBool s_FoundStopLine (char * linestring)
 
2487
{
 
2488
    if (linestring == NULL) {
 
2489
        return eFalse;
 
2490
    }
 
2491
    if (s_StringNICmp (linestring, "endblock", 8) == 0
 
2492
        ||  s_StringNICmp (linestring, "end;", 4) == 0) {
 
2493
        return eTrue;
 
2494
    }
 
2495
    return eFalse;
 
2496
}
 
2497
 
 
2498
 
 
2499
/* This function identifies the beginning line of an ASN.1 file, which
 
2500
 * cannot be read by the alignment reader.
 
2501
 */
 
2502
static EBool s_IsASN1 (char * linestring)
 
2503
{
 
2504
    if (linestring != NULL  &&  strstr (linestring, "::=") != NULL) {
 
2505
        return eTrue;
 
2506
    } else {
 
2507
        return eFalse;
 
2508
    }
 
2509
}
 
2510
 
 
2511
 
 
2512
/* The following functions are used to locate and read comments enclosed
 
2513
 * in brackets.  These comments sometimes include organism information.
 
2514
 */
 
2515
 
 
2516
/* This function frees memory associated with a SCommentLoc structure. */
 
2517
static void s_CommentLocFree (TCommentLocPtr clp)
 
2518
{
 
2519
    if (clp == NULL) {
 
2520
        return;
 
2521
    }
 
2522
    s_CommentLocFree (clp->next);
 
2523
    free (clp);
 
2524
}
 
2525
 
 
2526
 
 
2527
/* This function finds the first comment enclosed in brackets and creates
 
2528
 * a SCommentLoc structure to indicate the position of the comment
 
2529
 * in the string.  The function returns a pointer to this structure if a
 
2530
 * comment is found or a NULL if the string does not contain a bracketed 
 
2531
 * comment.
 
2532
 */
 
2533
static TCommentLocPtr s_FindComment (char * string)
 
2534
{
 
2535
    char *         cp_start;
 
2536
    char *         cp_end;
 
2537
    TCommentLocPtr clp;
 
2538
 
 
2539
    if (string == NULL) {
 
2540
        return NULL;
 
2541
    }
 
2542
    cp_start = strstr (string, "[");
 
2543
    if (cp_start != NULL) {
 
2544
        cp_end = strstr (cp_start, "]");
 
2545
        if (cp_end != NULL) {
 
2546
            clp = (TCommentLocPtr) malloc (sizeof (SCommentLoc));
 
2547
            if (clp == NULL) {
 
2548
                return NULL;
 
2549
            }
 
2550
            clp->start = cp_start;
 
2551
            clp->end = cp_end;
 
2552
            clp->next = NULL;
 
2553
            return clp;
 
2554
        }
 
2555
    }
 
2556
    return NULL;
 
2557
}
 
2558
 
 
2559
 
 
2560
/* This function removes a comment from a line. */
 
2561
static void s_RemoveCommentFromLine (char * linestring)
 
2562
{
 
2563
    TCommentLocPtr clp;
 
2564
 
 
2565
    if (linestring == NULL) {
 
2566
        return;
 
2567
    }
 
2568
 
 
2569
    clp = s_FindComment (linestring);
 
2570
    while (clp != NULL) {
 
2571
        strcpy (clp->start, clp->end + 1);
 
2572
        s_CommentLocFree (clp);
 
2573
        clp = s_FindComment (linestring);
 
2574
    }
 
2575
 
 
2576
    /* if we have read an organism comment and that's all there was on the
 
2577
     * line, get rid of the arrow character as well so it doesn't end up 
 
2578
     * in the sequence data
 
2579
     */
 
2580
    if ( linestring [0] == '>'  &&  linestring [1] == 0) {
 
2581
        linestring [0] = 0;
 
2582
    }
 
2583
 
 
2584
    /* if the line now contains only space, truncate it */
 
2585
    if (strspn (linestring, " \t\r") == strlen (linestring)) {
 
2586
        linestring [0] = 0;
 
2587
    }
 
2588
    
 
2589
}
 
2590
 
 
2591
 
 
2592
/* This function determines whether or not a comment describes an organism
 
2593
 * by looking for org= or organism= inside the brackets.
 
2594
 */
 
2595
static EBool s_IsOrganismComment (TCommentLocPtr clp)
 
2596
{
 
2597
    int    len;
 
2598
    char * cp;
 
2599
    char * cp_end;
 
2600
 
 
2601
    if (clp == NULL  ||  clp->start == NULL  ||  clp->end == NULL) {
 
2602
        return eFalse;
 
2603
    }
 
2604
 
 
2605
    cp = clp->start;
 
2606
    if (*cp != '[') {
 
2607
        return eFalse;
 
2608
    }
 
2609
    cp ++;
 
2610
    len = strspn ( clp->start, " \t\r");
 
2611
    cp = cp + len;
 
2612
    cp_end = strstr (cp, "=");
 
2613
    if (cp_end == NULL) {
 
2614
        return eFalse;
 
2615
    }
 
2616
    cp_end --;
 
2617
    while (cp_end > cp  &&  isspace ((int )*cp_end)) {
 
2618
      cp_end --;
 
2619
    }
 
2620
    cp_end ++;
 
2621
    if ((cp_end - cp == 3  &&  s_StringNICmp (cp, "org", 3) == 0)
 
2622
        ||  (cp_end - cp == 8  &&  s_StringNICmp (cp, "organism", 8) == 0)) {
 
2623
        return eTrue;
 
2624
    }
 
2625
    return eFalse;
 
2626
}
 
2627
 
 
2628
 
 
2629
/* This function finds an organism comment, which includes the first bracketed
 
2630
 * comment with org= or organism=, plus any additional bracketed comments
 
2631
 * separated only by whitespace from the org= or organism= comment.
 
2632
 * The function returns a pointer to a SCommentLoc structure describing
 
2633
 * the location of the organism comment.
 
2634
 */
 
2635
static TCommentLocPtr s_FindOrganismComment (char * string)
 
2636
{
 
2637
    TCommentLocPtr clp, next_clp;
 
2638
 
 
2639
    if (string == NULL) {
 
2640
        return NULL;
 
2641
    }
 
2642
 
 
2643
    clp = s_FindComment (string);
 
2644
    while (clp != NULL  &&  ! s_IsOrganismComment (clp)) {
 
2645
        clp = s_FindComment (clp->end);
 
2646
    }
 
2647
 
 
2648
    if (clp == NULL) {
 
2649
        return NULL;
 
2650
    }
 
2651
 
 
2652
    next_clp = s_FindComment (clp->end);
 
2653
    while (next_clp != NULL  && 
 
2654
        (int) strspn (clp->end + 1, " \t\r") == next_clp->start - clp->end - 1
 
2655
        &&  ! s_IsOrganismComment (next_clp))
 
2656
    {
 
2657
        clp->end = next_clp->end;
 
2658
        next_clp = s_FindComment (clp->end);
 
2659
    }
 
2660
    return clp;
 
2661
}
 
2662
 
 
2663
 
 
2664
/* This function removes an organism comment from a line. */
 
2665
static void s_RemoveOrganismCommentFromLine (char * string)
 
2666
{
 
2667
    TCommentLocPtr clp;
 
2668
 
 
2669
    while ((clp = s_FindOrganismComment (string)) != NULL) {
 
2670
        strcpy (clp->start, clp->end + 1);
 
2671
        s_CommentLocFree (clp);
 
2672
    }
 
2673
}
 
2674
 
 
2675
 
 
2676
/* This function creates an ordered list of comments within an organism
 
2677
 * comment and returns a pointer to the first item in the linked list.
 
2678
 * In an ordered org name, the org= value appears first, followed by other
 
2679
 * bracketed values in alphabetical order.
 
2680
 */
 
2681
static TCommentLocPtr s_CreateOrderedOrgCommentList (TCommentLocPtr org_clp)
 
2682
{
 
2683
    TCommentLocPtr clp, prev_clp, next_clp, clp_list, ordered_start;
 
2684
    int           next_len, this_len, len;
 
2685
  
 
2686
    if (org_clp == NULL) {
 
2687
        return NULL;
 
2688
    }
 
2689
 
 
2690
    clp_list = s_FindComment (org_clp->start); /* this is the org= */
 
2691
    prev_clp = NULL;
 
2692
    ordered_start = s_FindComment (clp_list->end);
 
2693
    if (ordered_start == NULL) {
 
2694
        return clp_list;
 
2695
    }
 
2696
    clp = s_FindComment (ordered_start->end);
 
2697
    while (clp != NULL  &&  clp->start < org_clp->end) {
 
2698
        /* insert new comment into list */
 
2699
        prev_clp = NULL;
 
2700
        next_clp = ordered_start;
 
2701
        next_len = next_clp->end - next_clp->start;
 
2702
        this_len = clp->end - clp->start;
 
2703
        len = next_len > this_len ? next_len : this_len;
 
2704
        while (next_clp != NULL
 
2705
          &&  strncmp (next_clp->start, clp->start, len) < 0)
 
2706
        {
 
2707
            prev_clp = next_clp;
 
2708
            next_clp = next_clp->next;
 
2709
            if (next_clp != NULL) {
 
2710
                next_len = next_clp->end - next_clp->start;
 
2711
                len = next_len > this_len ? next_len : this_len;
 
2712
            }
 
2713
        }
 
2714
        if (prev_clp == NULL) {
 
2715
            clp->next = ordered_start;
 
2716
            ordered_start = clp;
 
2717
        } else {
 
2718
            clp->next = prev_clp->next;
 
2719
            prev_clp->next = clp;
 
2720
        }
 
2721
        clp = s_FindComment (clp->end);
 
2722
    }
 
2723
    clp_list->next = ordered_start;
 
2724
    return clp_list;
 
2725
}
 
2726
 
 
2727
 
 
2728
/* This function creates an ordered organism name based on the bracketed
 
2729
 * comments contained in the location described by org_clp.
 
2730
 */
 
2731
static char * s_CreateOrderedOrgName (TCommentLocPtr org_clp)
 
2732
{
 
2733
    TCommentLocPtr clp, clp_list;
 
2734
    char *         ordered_org_name;
 
2735
    char *         cp;
 
2736
 
 
2737
    if (org_clp == NULL) {
 
2738
        return NULL;
 
2739
    }
 
2740
 
 
2741
    ordered_org_name = malloc (org_clp->end - org_clp->start + 2);
 
2742
    if (ordered_org_name == NULL) {
 
2743
        return NULL;
 
2744
    }
 
2745
    ordered_org_name [0] = 0;
 
2746
    clp_list = s_CreateOrderedOrgCommentList (org_clp);
 
2747
    cp = ordered_org_name;
 
2748
    for (clp = clp_list; clp != NULL; clp = clp->next) {
 
2749
        strncpy (cp, clp->start, clp->end - clp->start + 1);
 
2750
        cp += clp->end - clp->start + 1;
 
2751
        *cp = 0;
 
2752
    }
 
2753
    
 
2754
    s_CommentLocFree (clp_list);
 
2755
 
 
2756
    return ordered_org_name;
 
2757
}
 
2758
 
 
2759
 
 
2760
/* This function is used to read any organism names that may appear in
 
2761
 * string, including any modifiers that may appear after the organism name.
 
2762
 */
 
2763
static void s_ReadOrgNamesFromText 
 
2764
(char *           string,
 
2765
 int              line_num,
 
2766
 SAlignRawFilePtr afrp)
 
2767
{
 
2768
    TCommentLocPtr clp;
 
2769
    char *         org_name;
 
2770
    char *         cp;
 
2771
    char *         defline;
 
2772
    char *         comment_end;
 
2773
    int            defline_offset;
 
2774
  
 
2775
    if (string == NULL  ||  afrp == NULL) {
 
2776
        return;
 
2777
    }
 
2778
 
 
2779
    clp = s_FindOrganismComment (string);
 
2780
    if (clp == NULL && (strstr (string, "org=") != NULL || strstr (string, "organism=") != NULL))
 
2781
    {
 
2782
      s_ReportOrgCommentError (string, afrp->report_error, afrp->report_error_userdata);
 
2783
    }
 
2784
    while (clp != NULL) {
 
2785
        org_name = s_CreateOrderedOrgName (clp);
 
2786
        afrp->organisms = s_AddLineInfo (afrp->organisms, org_name, line_num,
 
2787
                                       clp->start - string);
 
2788
        free (org_name);
 
2789
        afrp->num_organisms ++;
 
2790
        defline = NULL;
 
2791
        defline_offset = 0;
 
2792
        if (*clp->end != 0) {
 
2793
            cp = clp->end + 1;
 
2794
            cp += strspn (cp, " \t\r\n");
 
2795
            if (*cp != 0) {
 
2796
                defline = clp->end + 1;
 
2797
                defline_offset = clp->end - string + 1;
 
2798
            }
 
2799
        }
 
2800
        afrp->deflines = s_AddLineInfo (afrp->deflines, defline, line_num,
 
2801
                                      defline_offset);
 
2802
        afrp->num_deflines ++;
 
2803
                                      
 
2804
        comment_end = clp->end;
 
2805
        s_CommentLocFree (clp);
 
2806
        clp = s_FindOrganismComment (comment_end);
 
2807
    }
 
2808
}
 
2809
 
 
2810
 
 
2811
/* The following group of functions manages the SAlignRawSeq structure,
 
2812
 * which is used to track the IDs of sequences in the file, the sequence
 
2813
 * characters for those IDs, and the locations of the IDs and sequence
 
2814
 * characters.
 
2815
 */
 
2816
 
 
2817
/* This function allocates memory for an SAlignRawSeq structure,
 
2818
 * initializes its member variables, and returns a pointer to the newly
 
2819
 * allocated structure.
 
2820
 */
 
2821
static TAlignRawSeqPtr s_AlignRawSeqNew (TAlignRawSeqPtr list)
 
2822
{
 
2823
    TAlignRawSeqPtr arsp, last;
 
2824
 
 
2825
    arsp = (TAlignRawSeqPtr)malloc (sizeof (SAlignRawSeq));
 
2826
    if (arsp == NULL) {
 
2827
        return NULL;
 
2828
    }
 
2829
    arsp->id            = NULL;
 
2830
    arsp->sequence_data = NULL;
 
2831
    arsp->id_lines      = NULL;
 
2832
    arsp->next          = NULL;
 
2833
 
 
2834
    last = list;
 
2835
    while (last != NULL && last->next != NULL) {
 
2836
        last = last->next;
 
2837
    }
 
2838
    if (last != NULL) {
 
2839
        last->next = arsp;
 
2840
    }
 
2841
    return arsp;
 
2842
}
 
2843
 
 
2844
 
 
2845
/* This function frees the memory associated with an SAlignRawSeq
 
2846
 * structure's member variables and with the structure itself.
 
2847
 */
 
2848
static void s_AlignRawSeqFree (TAlignRawSeqPtr arsp)
 
2849
{
 
2850
    if (arsp == NULL) {
 
2851
        return;
 
2852
    }
 
2853
    s_AlignRawSeqFree (arsp->next);
 
2854
    free (arsp->id);
 
2855
    s_LineInfoFree (arsp->sequence_data);
 
2856
    s_IntLinkFree (arsp->id_lines);
 
2857
}
 
2858
 
 
2859
 
 
2860
/* This function returns a pointer to the sequence in list with the specified
 
2861
 * ID, unless there is no such sequence, in which case the function returns
 
2862
 * NULL.
 
2863
 */
 
2864
static TAlignRawSeqPtr 
 
2865
s_FindAlignRawSeqById 
 
2866
(TAlignRawSeqPtr list,
 
2867
 char *          id)
 
2868
{
 
2869
    TAlignRawSeqPtr arsp;
 
2870
 
 
2871
    for (arsp = list; arsp != NULL; arsp = arsp->next) {
 
2872
        if (strcmp (arsp->id, id) == 0) {
 
2873
            return arsp;
 
2874
        }
 
2875
    }
 
2876
    return NULL;
 
2877
}
 
2878
 
 
2879
 
 
2880
/* This function finds the position of a given ID in the sequence list,
 
2881
 * unless the ID is not found in the list, in which case the function returns
 
2882
 * -1.
 
2883
 */
 
2884
static int  
 
2885
s_FindAlignRawSeqOffsetById 
 
2886
(TAlignRawSeqPtr list, 
 
2887
 char *          id)
 
2888
{
 
2889
    TAlignRawSeqPtr arsp;
 
2890
    int             offset;
 
2891
 
 
2892
    for (arsp = list, offset = 0; arsp != NULL; arsp = arsp->next, offset++) {
 
2893
        if (strcmp (arsp->id, id) == 0) {
 
2894
            return offset;
 
2895
        }
 
2896
    }
 
2897
    return -1;
 
2898
}
 
2899
 
 
2900
 
 
2901
/* This function returns a pointer to the memory in which the ID for the
 
2902
 * Nth sequence is stored, unless there aren't that many sequences, in which
 
2903
 * case NULL is returned.
 
2904
 */
 
2905
static char * 
 
2906
s_GetAlignRawSeqIDByOffset 
 
2907
(TAlignRawSeqPtr list,
 
2908
 int  offset)
 
2909
{
 
2910
    TAlignRawSeqPtr arsp;
 
2911
    int            index;
 
2912
 
 
2913
    arsp = list;
 
2914
    index = 0;
 
2915
    while ( arsp != NULL  &&  index != offset ) {
 
2916
        arsp = arsp->next;
 
2917
        index++;
 
2918
    }
 
2919
    if (index == offset  &&  arsp != NULL) {
 
2920
        return arsp->id;
 
2921
    } else {
 
2922
        return NULL;
 
2923
    }
 
2924
}
 
2925
 
 
2926
 
 
2927
/* This function adds data to a sequence by looking for the specified ID in
 
2928
 * the list.  If the id is not found, a new sequence with that ID is added to
 
2929
 * the end of the list.
 
2930
 * The function returns a pointer to the first item in the list.
 
2931
 */
 
2932
static TAlignRawSeqPtr
 
2933
s_AddAlignRawSeqById
 
2934
(TAlignRawSeqPtr list,
 
2935
 char *  id,
 
2936
 char *  data,
 
2937
 int     id_line_num,
 
2938
 int     data_line_num,
 
2939
 int     data_line_offset)
 
2940
{
 
2941
    TAlignRawSeqPtr arsp;
 
2942
    TIntLinkPtr     ilp;
 
2943
 
 
2944
    arsp = s_FindAlignRawSeqById (list, id);
 
2945
    if (arsp == NULL) {
 
2946
        arsp = s_AlignRawSeqNew (list);
 
2947
        if (arsp == NULL) {
 
2948
            return NULL;
 
2949
        }
 
2950
        if (list == NULL) list = arsp;
 
2951
        arsp->id = strdup (id);
 
2952
    }
 
2953
    arsp->sequence_data = s_AddLineInfo (arsp->sequence_data,
 
2954
                                       data,
 
2955
                                       data_line_num,
 
2956
                                       data_line_offset);
 
2957
    ilp = s_IntLinkNew (id_line_num, arsp->id_lines);
 
2958
    if (arsp->id_lines == NULL) arsp->id_lines = ilp;
 
2959
    return list;
 
2960
}
 
2961
 
 
2962
 
 
2963
/* This function adds data to the Nth sequence in the sequence list and
 
2964
 * returns eTrue, unless there aren't that many sequences in the list, in
 
2965
 * which case the function returns eFalse.
 
2966
 */
 
2967
static EBool 
 
2968
s_AddAlignRawSeqByIndex 
 
2969
(TAlignRawSeqPtr list,
 
2970
 int     index,
 
2971
 char *  data,
 
2972
 int     data_line_num,
 
2973
 int     data_line_offset)
 
2974
{
 
2975
    TAlignRawSeqPtr arsp;
 
2976
    int            curr;
 
2977
 
 
2978
    curr = 0;
 
2979
    for (arsp = list; arsp != NULL  &&  curr < index; arsp = arsp->next) {
 
2980
        curr++;
 
2981
    }
 
2982
    if (arsp == NULL) {
 
2983
        return eFalse;
 
2984
    } else {
 
2985
        arsp->sequence_data = s_AddLineInfo (arsp->sequence_data,
 
2986
                                           data,
 
2987
                                           data_line_num,
 
2988
                                           data_line_offset);
 
2989
        return eTrue;
 
2990
    }
 
2991
}
 
2992
 
 
2993
 
 
2994
/* This function frees memory associated with the SAlignRawFileData structure.
 
2995
 */
 
2996
static void s_AlignFileRawFree (SAlignRawFilePtr afrp)
 
2997
{
 
2998
    if (afrp == NULL) {
 
2999
        return;
 
3000
    }
 
3001
 
 
3002
    s_LineInfoFree (afrp->organisms);
 
3003
    s_LineInfoFree (afrp->deflines);
 
3004
    s_LineInfoFree (afrp->line_list);
 
3005
    s_AlignRawSeqFree (afrp->sequences);
 
3006
    s_IntLinkFree (afrp->offset_list);
 
3007
    free (afrp);
 
3008
}
 
3009
 
 
3010
 
 
3011
/* This function allocates memory for an SAlignRawFileData structure and
 
3012
 * initializes its member variables.  The function returns a pointer to
 
3013
 * the newly allocated structure.
 
3014
 */
 
3015
static SAlignRawFilePtr s_AlignFileRawNew (void)
 
3016
{
 
3017
    SAlignRawFilePtr afrp;
 
3018
 
 
3019
    afrp = (SAlignRawFilePtr)malloc (sizeof (SAlignRawFileData));
 
3020
    if (afrp == NULL) {
 
3021
        return NULL;
 
3022
    }
 
3023
    afrp->marked_ids            = eFalse;
 
3024
    afrp->line_list             = NULL;
 
3025
    afrp->organisms             = NULL;
 
3026
    afrp->num_organisms         = 0;
 
3027
    afrp->deflines              = NULL;
 
3028
    afrp->num_deflines          = 0;
 
3029
    afrp->block_size            = 0;
 
3030
    afrp->offset_list           = NULL;
 
3031
    afrp->sequences             = NULL;
 
3032
    afrp->report_error          = NULL;
 
3033
    afrp->report_error_userdata = NULL;
 
3034
    afrp->alphabet              = NULL;
 
3035
    afrp->expected_num_sequence = 0;
 
3036
    afrp->expected_sequence_len = 0;
 
3037
    afrp->num_segments          = 1;
 
3038
    return afrp;
 
3039
}
 
3040
 
 
3041
 
 
3042
/* The following functions are used to analyze the structure of a file and
 
3043
 * assemble the sequences listed in the file.
 
3044
 * Sequence data in a file is organized in one of two general formats - 
 
3045
 * interleaved or contiguous.  Interleaved data can be recognized by looking
 
3046
 * for repeated blocks of the same number of lines within a file separated
 
3047
 * by blank or skippable lines from other lines in the file.  The first of
 
3048
 * these blocks must have at least two elements separated by whitespace
 
3049
 * in each line, the first of these elements is the ID for the sequence in
 
3050
 * that row and for the sequences in that position within the block for the
 
3051
 * remainder of the file.
 
3052
 * Contiguous data can be recognized by either looking for "marked" sequence
 
3053
 * IDs, which begin with a '>' character, or by looking for repeated patterns
 
3054
 * of lines with the same numbers of characters.
 
3055
 */
 
3056
 
 
3057
/* The following functions are used to analyze interleaved data. */
 
3058
 
 
3059
/* This function creates a SLengthListData structure that describes the pattern
 
3060
 * of character lengths in the string pointed to by cp.
 
3061
 */
 
3062
static SLengthListPtr s_GetBlockPattern (char * cp)
 
3063
{
 
3064
    SLengthListPtr this_pattern;
 
3065
    int           len;
 
3066
 
 
3067
    this_pattern = s_LengthListNew (NULL);
 
3068
    if (this_pattern == NULL) {
 
3069
        return NULL;
 
3070
    }
 
3071
 
 
3072
    this_pattern->num_appearances = 1;
 
3073
    while (*cp != 0) {
 
3074
        len = strcspn (cp, " \t\r");
 
3075
        s_AddLengthRepeat (this_pattern, len);
 
3076
        cp += len;
 
3077
        cp += strspn (cp, " \t\r");
 
3078
    }
 
3079
    return this_pattern;
 
3080
}
 
3081
 
 
3082
 
 
3083
/* This function attempts to predict whether the following lines will be
 
3084
 * an interleaved block.  If so, the function returns the location of the
 
3085
 * beginning of the block, otherwise the function returns -1.
 
3086
 */
 
3087
static int 
 
3088
s_ForecastBlockPattern 
 
3089
(SLengthListPtr pattern_list,
 
3090
 TIntLinkPtr    next_offset,
 
3091
 int            line_start,
 
3092
 int            block_size)
 
3093
{
 
3094
    int  line_counter;
 
3095
    SLengthListPtr llp;
 
3096
 
 
3097
    line_counter = line_start;
 
3098
    if (next_offset != NULL
 
3099
        &&  next_offset->ival - line_counter < block_size) {
 
3100
        return -1;
 
3101
    }
 
3102
    
 
3103
    for (llp = pattern_list;
 
3104
         llp != NULL
 
3105
           &&  (next_offset == NULL  ||  line_counter < next_offset->ival - 1)
 
3106
           &&  line_counter - line_start < block_size;
 
3107
         llp = llp->next)
 
3108
    {
 
3109
        if (llp->lengthrepeats == NULL) {
 
3110
            return -1;
 
3111
        }
 
3112
        line_counter += llp->num_appearances;
 
3113
    }
 
3114
    if (line_counter - line_start == block_size) {
 
3115
        if (llp->next == NULL) {
 
3116
            return line_start;
 
3117
        }
 
3118
        llp = llp->next;
 
3119
        if (llp->lengthrepeats == NULL) {
 
3120
            return line_start;
 
3121
        }
 
3122
    }
 
3123
    return -1;
 
3124
}
 
3125
 
 
3126
 
 
3127
/* This function looks for malformed blocks between the identified blocks
 
3128
 * indicated by the offset_list.  It returns a pointer to the list with the
 
3129
 * new locations inserted at the appropriate locations.
 
3130
 */
 
3131
static TIntLinkPtr
 
3132
s_AugmentBlockPatternOffsetList
 
3133
(SLengthListPtr pattern_list,
 
3134
 TIntLinkPtr    offset_list,
 
3135
 int            block_size)
 
3136
{
 
3137
    int            line_counter;
 
3138
    SLengthListPtr llp;
 
3139
    TIntLinkPtr    next_offset, prev_offset, new_offset;
 
3140
    int            forecast_pos;
 
3141
 
 
3142
    prev_offset = NULL;
 
3143
    next_offset = offset_list;
 
3144
    line_counter = 0;
 
3145
    llp = pattern_list;
 
3146
    while (llp != NULL) {
 
3147
        if (next_offset != NULL  &&  line_counter == next_offset->ival) {
 
3148
            prev_offset = next_offset;
 
3149
            next_offset = next_offset->next;
 
3150
            /* skip past the lines for this block */
 
3151
            while (line_counter - prev_offset->ival < block_size
 
3152
                   &&  llp != NULL)
 
3153
            {
 
3154
                line_counter += llp->num_appearances;
 
3155
                llp = llp->next;
 
3156
            }
 
3157
        } else {
 
3158
            forecast_pos = s_ForecastBlockPattern (llp, next_offset,
 
3159
                                                 line_counter,
 
3160
                                                 block_size);
 
3161
            if (forecast_pos > 0) {
 
3162
                new_offset = s_IntLinkNew (forecast_pos, NULL);
 
3163
                if (new_offset == NULL) {
 
3164
                    return NULL;
 
3165
                }
 
3166
                if (prev_offset == NULL) {
 
3167
                    new_offset->next = offset_list;
 
3168
                    offset_list = new_offset;
 
3169
                } else {
 
3170
                    new_offset->next = next_offset;
 
3171
                    prev_offset->next = new_offset;
 
3172
                }
 
3173
                prev_offset = new_offset;
 
3174
                /* skip past the lines for this block */
 
3175
                while (line_counter - prev_offset->ival < block_size
 
3176
                       &&  llp != NULL)
 
3177
                {
 
3178
                    line_counter += llp->num_appearances;
 
3179
                    llp = llp->next;
 
3180
                }
 
3181
            } else {
 
3182
                line_counter += llp->num_appearances;
 
3183
                llp = llp->next;
 
3184
            }
 
3185
        }
 
3186
    }
 
3187
    return offset_list;
 
3188
}
 
3189
 
 
3190
 
 
3191
/* This function looks for lines that could not be assigned to an interleaved
 
3192
 * block.  It returns eTrue if it finds any such lines after the first offset,
 
3193
 * eFalse otherwise, and reports all instances of unused lines as errors.
 
3194
 */
 
3195
static EBool
 
3196
s_FindUnusedLines 
 
3197
(SLengthListPtr pattern_list,
 
3198
 SAlignRawFilePtr afrp)
 
3199
{
 
3200
    TIntLinkPtr    offset;
 
3201
    SLengthListPtr llp;
 
3202
    int            line_counter;
 
3203
    int            block_line_counter;
 
3204
    EBool          rval = eFalse;
 
3205
    TLineInfoPtr   line_val;
 
3206
    int            skip;
 
3207
 
 
3208
    if (pattern_list == NULL  ||  afrp == NULL
 
3209
        ||  afrp->offset_list == NULL  ||  afrp->block_size < 2) {
 
3210
        return eFalse;
 
3211
    }
 
3212
    
 
3213
    offset = afrp->offset_list;
 
3214
    llp = pattern_list;
 
3215
    line_counter = 0;
 
3216
    line_val = afrp->line_list;
 
3217
 
 
3218
    while (llp != NULL  &&  line_val != NULL) {
 
3219
        while (llp != NULL  &&  line_val != NULL
 
3220
               &&  (offset == NULL  ||  line_counter < offset->ival)) {
 
3221
            if (llp->lengthrepeats != NULL) {
 
3222
                s_ReportUnusedLine (line_counter,
 
3223
                                    line_counter + llp->num_appearances - 1,
 
3224
                                    line_val,
 
3225
                                    afrp->report_error,
 
3226
                                    afrp->report_error_userdata);
 
3227
                if (offset != afrp->offset_list) {
 
3228
                    rval = eTrue;
 
3229
                }
 
3230
            }
 
3231
            line_counter += llp->num_appearances;
 
3232
            for (skip = 0;
 
3233
                 skip < llp->num_appearances  &&  line_val != NULL;
 
3234
                 skip++) {
 
3235
                line_val = line_val->next;
 
3236
            }
 
3237
            llp = llp->next;
 
3238
        }
 
3239
        block_line_counter = 0;
 
3240
        while (block_line_counter < afrp->block_size  &&  llp != NULL) {
 
3241
            block_line_counter += llp->num_appearances;
 
3242
            line_counter += llp->num_appearances;
 
3243
            for (skip = 0;
 
3244
                 skip < llp->num_appearances  &&  line_val != NULL;
 
3245
                 skip++) {
 
3246
                line_val = line_val->next;
 
3247
            }
 
3248
            llp = llp->next;
 
3249
        }
 
3250
        if (offset != NULL) {
 
3251
            offset = offset->next;
 
3252
        }
 
3253
    }
 
3254
    return rval;
 
3255
}
 
3256
 
 
3257
 
 
3258
/* This function examines a list of line lengths, looking for interleaved
 
3259
 * blocks.  If it finds them, it will set the SAlignRawFileData offset_list
 
3260
 * member variable to point to a list of locations for the blocks.
 
3261
 */
 
3262
static void
 
3263
s_FindInterleavedBlocks 
 
3264
(SLengthListPtr pattern_list,
 
3265
 SAlignRawFilePtr afrp)
 
3266
{
 
3267
    SLengthListPtr llp, llp_next;
 
3268
    TSizeInfoPtr   size_list, best_ptr;
 
3269
    TIntLinkPtr    new_offset;
 
3270
    int            line_counter;
 
3271
 
 
3272
    afrp->block_size = 0;
 
3273
    size_list = NULL;
 
3274
    afrp->offset_list = NULL;
 
3275
    for (llp = pattern_list; llp != NULL; llp = llp->next) {
 
3276
        llp_next = llp->next;
 
3277
        if (llp->num_appearances > 1 
 
3278
            &&  (llp_next == NULL  ||  llp_next->lengthrepeats == NULL)) {
 
3279
            size_list = s_AddSizeInfo (size_list, llp->num_appearances);
 
3280
        }
 
3281
    }
 
3282
    best_ptr = s_GetMostPopularSizeInfo (size_list);
 
3283
    if (best_ptr != NULL  &&  best_ptr->num_appearances > 1) {
 
3284
        afrp->block_size = best_ptr->size_value;
 
3285
        line_counter = 0;
 
3286
        for (llp = pattern_list; llp != NULL; llp = llp->next) {
 
3287
            llp_next = llp->next;
 
3288
            if (llp->num_appearances == afrp->block_size
 
3289
                &&  (llp_next == NULL  ||  llp_next->lengthrepeats == NULL))
 
3290
            {
 
3291
                new_offset = s_IntLinkNew (line_counter, afrp->offset_list);
 
3292
                if (new_offset == NULL) {
 
3293
                    return;
 
3294
                }
 
3295
                if (afrp->offset_list == NULL) afrp->offset_list = new_offset;
 
3296
            }
 
3297
            line_counter += llp->num_appearances;
 
3298
        }
 
3299
        afrp->offset_list = s_AugmentBlockPatternOffsetList (pattern_list,
 
3300
                                                           afrp->offset_list, 
 
3301
                                                           afrp->block_size);
 
3302
    }
 
3303
    if (s_FindUnusedLines (pattern_list, afrp)) {
 
3304
        s_IntLinkFree (afrp->offset_list);
 
3305
        afrp->offset_list = NULL;
 
3306
        afrp->block_size = 0;
 
3307
    }
 
3308
    s_SizeInfoFree (size_list);
 
3309
    
 
3310
}
 
3311
 
 
3312
static void s_TrimEndSpace (char *linestring)
 
3313
{
 
3314
    int len;
 
3315
    char *cp;
 
3316
  
 
3317
    if (linestring == NULL) return;
 
3318
    len = strlen (linestring);
 
3319
    cp = linestring + len - 1;
 
3320
    while (cp > linestring && (*cp == ' ' || *cp == '\t' || *cp == '\r' || *cp == '\n'))
 
3321
    {
 
3322
            *cp = 0;
 
3323
            cp--;
 
3324
    }
 
3325
}
 
3326
 
 
3327
static SAlignRawFilePtr
 
3328
s_ReadAlignFileRaw
 
3329
(FReadLineFunction    readfunc,
 
3330
 void *             userdata,
 
3331
 TSequenceInfoPtr     sequence_info,
 
3332
 FReportErrorFunction errfunc,
 
3333
 void *             errdata)
 
3334
{
 
3335
    char *                   linestring;
 
3336
    SAlignRawFilePtr         afrp;
 
3337
    char *                   tmp;
 
3338
    EBool                    found_stop;
 
3339
    int                      overall_line_count;
 
3340
    EBool                    found_expected_ntax = eFalse;
 
3341
    EBool                    found_expected_nchar = eFalse;
 
3342
    EBool                    found_char_comment = eFalse;
 
3343
    SLengthListPtr           pattern_list = NULL;
 
3344
    SLengthListPtr           this_pattern;
 
3345
    char *                   cp;
 
3346
    int                      len;
 
3347
    TIntLinkPtr              new_offset;
 
3348
    EBool                    in_taxa_comment;
 
3349
    EBool                    in_bracketed_comment = eFalse;
 
3350
    TBracketedCommentListPtr comment_list = NULL, last_comment = NULL;
 
3351
    
 
3352
 
 
3353
 
 
3354
    if (readfunc == NULL  ||  sequence_info == NULL) {
 
3355
        return NULL;
 
3356
    }
 
3357
 
 
3358
    afrp = s_AlignFileRawNew ();
 
3359
    if (afrp == NULL) {
 
3360
        return NULL;
 
3361
    }
 
3362
  
 
3363
    afrp->alphabet = strdup (sequence_info->alphabet);
 
3364
    afrp->report_error = errfunc;
 
3365
    afrp->report_error_userdata = errdata;
 
3366
 
 
3367
    overall_line_count = 0;
 
3368
    found_stop = eFalse;
 
3369
    in_taxa_comment = eFalse;
 
3370
    linestring = readfunc (userdata);
 
3371
    if (s_IsASN1 (linestring)) {
 
3372
        s_ReportASN1Error (afrp->report_error, afrp->report_error_userdata);
 
3373
        s_AlignFileRawFree (afrp);
 
3374
        return NULL;
 
3375
    }
 
3376
 
 
3377
    while (linestring != NULL  &&  linestring [0] != EOF) {
 
3378
        s_TrimEndSpace (linestring);
 
3379
        s_ReadOrgNamesFromText (linestring, overall_line_count, afrp);
 
3380
        /* we want to remove the comment from the line for the purpose 
 
3381
         * of looking for blank lines and skipping,
 
3382
         * but save comments for storing in array if line is not skippable or
 
3383
         * blank
 
3384
         */ 
 
3385
        len = strspn (linestring, " \t\r\n");
 
3386
        tmp = strdup (linestring + len);
 
3387
        if (tmp == NULL) {
 
3388
            return NULL;
 
3389
        }
 
3390
 
 
3391
        if (! found_stop && ! in_taxa_comment) {
 
3392
            found_stop = s_FoundStopLine (tmp);
 
3393
        }
 
3394
        if (! found_stop) {
 
3395
            if (! found_expected_ntax  ||  ! found_expected_nchar) {
 
3396
                if (s_IsTwoNumbersSeparatedBySpace (tmp)) {
 
3397
                    s_GetFASTAExpectedNumbers (tmp, afrp);
 
3398
                    found_expected_ntax = eTrue;
 
3399
                    found_expected_nchar = eTrue;
 
3400
               } else {
 
3401
                    s_GetNexusSizeComments (tmp, &found_expected_ntax,
 
3402
                                            &found_expected_nchar, afrp);
 
3403
                }
 
3404
            }
 
3405
            if (! found_char_comment) {
 
3406
                found_char_comment = s_CheckNexusCharInfo (tmp, sequence_info, 
 
3407
                                                   afrp->report_error,
 
3408
                                                   afrp->report_error_userdata);
 
3409
            }
 
3410
            
 
3411
            if (in_taxa_comment) {
 
3412
                if (strncmp (tmp, "end;", 4) == 0) {
 
3413
                    in_taxa_comment = eFalse;
 
3414
                } 
 
3415
                tmp [0] = 0;
 
3416
            } else if (strncmp (tmp, "begin taxa;", 11) == 0) {
 
3417
                tmp [0] = 0;
 
3418
                in_taxa_comment = eTrue;
 
3419
            }
 
3420
 
 
3421
            /* remove complete single-line bracketed comments from line 
 
3422
             *before checking for multiline bracketed comments */
 
3423
            s_RemoveCommentFromLine (tmp);
 
3424
 
 
3425
            if (in_bracketed_comment) {
 
3426
                    len = strspn (linestring, " \t\r\n");
 
3427
                if (last_comment != NULL) 
 
3428
                {
 
3429
                        s_BracketedCommentListAddLine (last_comment, linestring + len,
 
3430
                                                       overall_line_count, len);
 
3431
                }
 
3432
                if (strchr (tmp, ']') != NULL) {
 
3433
                    in_bracketed_comment = eFalse;
 
3434
                }
 
3435
                tmp [0] = 0;
 
3436
            } else if (tmp [0] == '[' && strchr (tmp, ']') == NULL) {
 
3437
                in_bracketed_comment = eTrue;
 
3438
                    len = strspn (linestring, " \t\r\n");
 
3439
                    last_comment = s_BracketedCommentListNew (comment_list,
 
3440
                                                          linestring + len,
 
3441
                                                          overall_line_count, len);
 
3442
                if (comment_list == NULL) 
 
3443
                {
 
3444
                        comment_list = last_comment;
 
3445
                }
 
3446
                tmp [0] = 0;
 
3447
            }
 
3448
 
 
3449
            if (s_SkippableString (tmp)) {
 
3450
                tmp [0] = 0;
 
3451
            }
 
3452
  
 
3453
            if (tmp [0] == '>'  &&  ! found_stop) {
 
3454
                afrp->marked_ids = eTrue;
 
3455
                new_offset = s_IntLinkNew (overall_line_count + 1,
 
3456
                                          afrp->offset_list);
 
3457
                if (afrp->offset_list == NULL) afrp->offset_list = new_offset;
 
3458
            }
 
3459
 
 
3460
            if (! afrp->marked_ids) {
 
3461
                /* add to length list for interleaved block search */
 
3462
                len = strcspn (tmp, " \t\r");
 
3463
                if (len > 0) {
 
3464
                    cp = tmp + len;
 
3465
                    len = strspn (cp, " \t\r");
 
3466
                    if (len > 0) {
 
3467
                        cp = cp + len;
 
3468
                    }
 
3469
                    if (*cp == 0) {
 
3470
                        this_pattern = s_GetBlockPattern (tmp);
 
3471
                    } else {
 
3472
                        this_pattern = s_GetBlockPattern (cp);
 
3473
                    }
 
3474
                    pattern_list = s_AddPatternRepeat (pattern_list,
 
3475
                                                     this_pattern);
 
3476
                } else {
 
3477
                    this_pattern = s_GetBlockPattern (tmp);
 
3478
                    pattern_list = s_AddPatternRepeat (pattern_list,
 
3479
                                                     this_pattern);
 
3480
                }
 
3481
            }
 
3482
 
 
3483
            len = strspn (linestring, " \t\r\n");
 
3484
            afrp->line_list = s_AddLineInfo (afrp->line_list,
 
3485
                                           linestring + len,
 
3486
                                           overall_line_count, len);
 
3487
        }
 
3488
        free (linestring);
 
3489
        free (tmp);
 
3490
        linestring = readfunc (userdata);
 
3491
        overall_line_count ++;
 
3492
    }
 
3493
    afrp->num_segments = s_GetNumSegmentsInAlignment (comment_list, errfunc, errdata);
 
3494
    if (afrp->num_segments > 1) 
 
3495
    {
 
3496
        if (afrp->offset_list != NULL)
 
3497
        {
 
3498
                s_ReportSegmentedAlignmentError (afrp->offset_list,
 
3499
                                                 errfunc, errdata);
 
3500
            s_AlignFileRawFree (afrp);
 
3501
            s_LengthListFree (pattern_list);
 
3502
            s_BracketedCommentListFree (comment_list);
 
3503
            return NULL;                
 
3504
        }
 
3505
        else
 
3506
        {
 
3507
            afrp->offset_list = GetSegmentOffsetList (comment_list);
 
3508
            afrp->marked_ids = eTrue;
 
3509
        }
 
3510
    }
 
3511
    if (! afrp->marked_ids) {
 
3512
        s_FindInterleavedBlocks (pattern_list, afrp);
 
3513
    }
 
3514
    s_LengthListFree (pattern_list);
 
3515
    s_BracketedCommentListFree (comment_list);
 
3516
    return afrp;
 
3517
}
 
3518
 
 
3519
 
 
3520
/* This function analyzes a block to see if it contains, as the first element
 
3521
 * of any of its lines, one of the sequence IDs already identified.  If the
 
3522
 * one of the lines does begin with a sequence ID, all of the lines are
 
3523
 * assumed to begin with sequence IDs and the function returns eTrue, otherwise
 
3524
 * the function returns eFalse.
 
3525
 */
 
3526
static EBool 
 
3527
s_DoesBlockHaveIds 
 
3528
(SAlignRawFilePtr afrp, 
 
3529
 TLineInfoPtr     first_line,
 
3530
 int             num_lines_in_block)
 
3531
{
 
3532
    TLineInfoPtr    lip;
 
3533
    char *          linestring;
 
3534
    char *          this_id;
 
3535
    TAlignRawSeqPtr arsp;
 
3536
    size_t          len;
 
3537
    int             block_offset;
 
3538
 
 
3539
    if (afrp->sequences == NULL) {
 
3540
         return eTrue;
 
3541
    }
 
3542
 
 
3543
    for (lip = first_line, block_offset = 0;
 
3544
         lip != NULL  &&  block_offset < num_lines_in_block;
 
3545
         lip = lip->next, block_offset++)
 
3546
    {
 
3547
        linestring = lip->data;
 
3548
        if (linestring != NULL) {
 
3549
            len = strcspn (linestring, " \t\r");
 
3550
            if (len > 0  &&  len < strlen (linestring)) {
 
3551
                this_id = (char *) malloc (len + 1);
 
3552
                if (this_id == NULL) {
 
3553
                    return eFalse;
 
3554
                }
 
3555
                strncpy (this_id, linestring, len);
 
3556
                this_id [len] = 0;
 
3557
                arsp = s_FindAlignRawSeqById (afrp->sequences, this_id);
 
3558
                free (this_id);
 
3559
                if (arsp != NULL) {
 
3560
                    return eTrue;
 
3561
                }
 
3562
            }
 
3563
        }
 
3564
    }
 
3565
    return eFalse;
 
3566
}
 
3567
 
 
3568
 
 
3569
/* This function analyzes the lines of the block to see if the pattern of
 
3570
 * the lengths of the whitespace-separated pieces of sequence data matches
 
3571
 * for all lines within the block.  The function returns eTrue if this is so,
 
3572
 * otherwise the function returns eFalse.
 
3573
 */
 
3574
static EBool 
 
3575
s_BlockIsConsistent
 
3576
(SAlignRawFilePtr afrp,
 
3577
 TLineInfoPtr     first_line,
 
3578
 int              num_lines_in_block,
 
3579
 EBool            has_ids,
 
3580
 EBool            first_block)
 
3581
{
 
3582
    TLineInfoPtr   lip;
 
3583
    SLengthListPtr list, this_pattern, best;
 
3584
    int            len, block_offset, id_offset;
 
3585
    char *         tmp_id;
 
3586
    EBool          rval;
 
3587
    char *         cp;
 
3588
 
 
3589
    rval = eTrue;
 
3590
    list = NULL;
 
3591
    for (lip = first_line, block_offset = 0;
 
3592
         lip != NULL  &&  block_offset < num_lines_in_block;
 
3593
         lip = lip->next, block_offset ++)
 
3594
    {
 
3595
        cp = lip->data;
 
3596
        if (has_ids) {
 
3597
            len = strcspn (cp, " \t\r");
 
3598
            tmp_id = (char *) malloc ( (len + 1) * sizeof (char));
 
3599
            if (tmp_id == NULL) {
 
3600
                return eFalse;
 
3601
            }
 
3602
            strncpy (tmp_id, cp, len);
 
3603
            tmp_id [len] = 0;
 
3604
            id_offset = s_FindAlignRawSeqOffsetById (afrp->sequences, tmp_id);
 
3605
            if (id_offset != block_offset  &&  ! first_block) {
 
3606
                rval = eFalse;
 
3607
                s_ReportInconsistentID (tmp_id, lip->line_num,
 
3608
                                      afrp->report_error,
 
3609
                                      afrp->report_error_userdata);
 
3610
            }
 
3611
            free (tmp_id);
 
3612
            cp += len;
 
3613
            cp += strspn (cp, " \t\r");
 
3614
        }
 
3615
        this_pattern = s_GetBlockPattern (cp);
 
3616
        list = s_AddLengthList (list, this_pattern);
 
3617
    }
 
3618
 
 
3619
    /* Now find the pattern with the most appearances */
 
3620
    best = NULL;
 
3621
    for (this_pattern = list;
 
3622
         this_pattern != NULL;
 
3623
         this_pattern = this_pattern->next)
 
3624
    {
 
3625
        if (this_pattern->num_appearances == 0) continue;
 
3626
        if (best == NULL 
 
3627
          ||  this_pattern->num_appearances > best->num_appearances)
 
3628
        {
 
3629
            best = this_pattern;
 
3630
        }
 
3631
    }
 
3632
 
 
3633
    /* now identify and report inconsistent lines */
 
3634
    for (lip = first_line, block_offset = 0;
 
3635
         lip != NULL  &&  block_offset < num_lines_in_block;
 
3636
         lip = lip->next, block_offset ++)
 
3637
    {
 
3638
        cp = lip->data;
 
3639
        if (has_ids) {
 
3640
            len = strcspn (cp, " \t\r");
 
3641
            tmp_id = (char *) malloc ( (len + 1) * sizeof (char));
 
3642
            if (tmp_id == NULL) {
 
3643
                return eFalse;
 
3644
            }
 
3645
            strncpy (tmp_id, cp, len);
 
3646
            tmp_id [len] = 0;
 
3647
            cp += len;
 
3648
            cp += strspn (cp, " \t\r");
 
3649
        } else {
 
3650
            tmp_id = s_GetAlignRawSeqIDByOffset (afrp->sequences, block_offset);
 
3651
        }
 
3652
        this_pattern = s_GetBlockPattern (cp);
 
3653
        if ( ! s_DoLengthPatternsMatch (this_pattern, best)) {
 
3654
            rval = eFalse;
 
3655
            s_ReportInconsistentBlockLine (tmp_id, lip->line_num,
 
3656
                                         afrp->report_error,
 
3657
                                         afrp->report_error_userdata);
 
3658
        }
 
3659
        s_LengthListFree (this_pattern);
 
3660
        if (has_ids) {
 
3661
            free (tmp_id);
 
3662
        }
 
3663
    }
 
3664
    s_LengthListFree (list);
 
3665
    return rval;
 
3666
}
 
3667
 
 
3668
 
 
3669
/* This function processes a block of lines and adds the sequence data from
 
3670
 * each line in the block to the appropriate sequence in the list.
 
3671
 */
 
3672
static void 
 
3673
s_ProcessBlockLines 
 
3674
(SAlignRawFilePtr afrp,
 
3675
 TLineInfoPtr     lines,
 
3676
 int              num_lines_in_block,
 
3677
 EBool            first_block)
 
3678
{
 
3679
    TLineInfoPtr  lip;
 
3680
    char *        linestring;
 
3681
    char *        cp;
 
3682
    char *        this_id;
 
3683
    int           len;
 
3684
    int           line_number;
 
3685
    EBool         this_block_has_ids;
 
3686
    int           pos;
 
3687
 
 
3688
    this_block_has_ids = s_DoesBlockHaveIds (afrp, lines, num_lines_in_block);
 
3689
    s_BlockIsConsistent (afrp, lines, num_lines_in_block, this_block_has_ids,
 
3690
                       first_block);
 
3691
    for (lip = lines, line_number = 0;
 
3692
         lip != NULL  &&  line_number < num_lines_in_block;
 
3693
         lip = lip->next, line_number ++)
 
3694
    {
 
3695
        linestring = lip->data;
 
3696
        if (linestring != NULL) {
 
3697
            pos = 0;
 
3698
            if (this_block_has_ids) {
 
3699
                len = strcspn (linestring, " \t\r");
 
3700
                this_id = (char *) malloc (len + 1);
 
3701
                if (this_id == NULL) {
 
3702
                    return;
 
3703
                }
 
3704
                strncpy (this_id, linestring, len);
 
3705
                this_id [len] = 0;
 
3706
                cp = linestring + len;
 
3707
                pos += len;
 
3708
                len = strspn (linestring, " \t\r");
 
3709
                cp += len;
 
3710
                pos += len;
 
3711
                afrp->sequences = s_AddAlignRawSeqById (afrp->sequences,
 
3712
                                                      this_id, cp,
 
3713
                                                      lip->line_num,
 
3714
                                                      lip->line_num,
 
3715
                                           lip->line_offset + cp - linestring);
 
3716
                free (this_id);
 
3717
            } else {
 
3718
                if (! s_AddAlignRawSeqByIndex (afrp->sequences, line_number,
 
3719
                                             linestring, 
 
3720
                                             lip->line_num, lip->line_offset))
 
3721
                {
 
3722
                    s_ReportBlockLengthError ("", lip->line_num,
 
3723
                                            afrp->block_size,
 
3724
                                            line_number,
 
3725
                                            afrp->report_error,
 
3726
                                            afrp->report_error_userdata);
 
3727
                }
 
3728
            }
 
3729
        }
 
3730
    }
 
3731
}
 
3732
 
 
3733
 
 
3734
/* This function removes comments from the lines of an interleaved block of
 
3735
 * data.
 
3736
 */
 
3737
static void
 
3738
s_RemoveCommentsFromBlock
 
3739
(TLineInfoPtr first_line,
 
3740
 int         num_lines_in_block)
 
3741
{
 
3742
    TLineInfoPtr lip;
 
3743
    int         block_offset;
 
3744
 
 
3745
    for (lip = first_line, block_offset = 0;
 
3746
         lip != NULL  &&  block_offset < num_lines_in_block;
 
3747
         lip = lip->next)
 
3748
    {                   
 
3749
        s_RemoveCommentFromLine (lip->data);
 
3750
    }
 
3751
}
 
3752
 
 
3753
 
 
3754
/* This function processes the interleaved block of data found at each
 
3755
 * location listed in afrp->offset_list.
 
3756
 */
 
3757
static void s_ProcessAlignRawFileByBlockOffsets (SAlignRawFilePtr afrp)
 
3758
{
 
3759
    int           line_counter;
 
3760
    TIntLinkPtr   offset_ptr;
 
3761
    TLineInfoPtr  lip;
 
3762
    EBool         first_block = eTrue;
 
3763
    EBool         in_taxa_comment = eFalse;
 
3764
 
 
3765
    if (afrp == NULL) {
 
3766
        return;
 
3767
    }
 
3768
 
 
3769
    line_counter = 0;
 
3770
    offset_ptr = afrp->offset_list;
 
3771
    lip = afrp->line_list;
 
3772
    while (lip != NULL  &&  offset_ptr != NULL
 
3773
           &&  (in_taxa_comment  ||  ! s_FoundStopLine (lip->data))) {
 
3774
        if (in_taxa_comment) {
 
3775
            if (strncmp (lip->data, "end;", 4) == 0) {
 
3776
                in_taxa_comment = eFalse;
 
3777
            } 
 
3778
        } else if (lip->data != NULL
 
3779
            &&  strncmp (lip->data, "begin taxa;", 11) == 0) {
 
3780
            in_taxa_comment = eTrue;
 
3781
        }
 
3782
        if (line_counter == offset_ptr->ival) {
 
3783
            s_RemoveCommentsFromBlock (lip, afrp->block_size);
 
3784
            s_ProcessBlockLines (afrp, lip, afrp->block_size, first_block);
 
3785
            first_block = eFalse;
 
3786
            offset_ptr = offset_ptr->next;
 
3787
        }
 
3788
        lip = lip->next;
 
3789
        line_counter ++;
 
3790
    }
 
3791
}
 
3792
 
 
3793
 
 
3794
/* The following functions are used to analyze contiguous data. */
 
3795
 
 
3796
static void 
 
3797
s_CreateSequencesBasedOnTokenPatterns 
 
3798
(TLineInfoPtr     token_list,
 
3799
 TIntLinkPtr      offset_list,
 
3800
 SLengthListPtr * anchorpattern,
 
3801
 SAlignRawFilePtr afrp)
 
3802
{
 
3803
    TLineInfoPtr lip;
 
3804
    int          line_counter;
 
3805
    TIntLinkPtr  offset_ptr, next_offset_ptr;
 
3806
    char *       curr_id;
 
3807
    TSizeInfoPtr sip;
 
3808
    int          pattern_line_counter;
 
3809
    int          curr_seg;
 
3810
 
 
3811
    if (token_list == NULL  ||  offset_list == NULL
 
3812
        ||  anchorpattern == NULL 
 
3813
        ||  afrp == NULL)
 
3814
    {
 
3815
        return;
 
3816
    }
 
3817
    for (curr_seg = 0; curr_seg < afrp->num_segments; curr_seg ++)
 
3818
    {
 
3819
        if (anchorpattern [curr_seg] == NULL || anchorpattern [curr_seg]->lengthrepeats == NULL)
 
3820
        {
 
3821
                return;
 
3822
        }
 
3823
    }
 
3824
 
 
3825
    line_counter = 0;
 
3826
    lip = token_list;
 
3827
    offset_ptr = offset_list;
 
3828
    curr_seg = 0;
 
3829
  
 
3830
    for (offset_ptr = offset_list;
 
3831
         offset_ptr != NULL  &&  lip != NULL;
 
3832
         offset_ptr = offset_ptr->next)
 
3833
    {
 
3834
        next_offset_ptr = offset_ptr->next;
 
3835
        while (line_counter < offset_ptr->ival - 1  &&  lip != NULL) {
 
3836
            lip = lip->next;
 
3837
            line_counter ++;
 
3838
        }
 
3839
        if (lip != NULL) {
 
3840
            curr_id = lip->data;
 
3841
            lip = lip->next;
 
3842
            line_counter ++;
 
3843
            for (sip = anchorpattern[curr_seg]->lengthrepeats;
 
3844
                 sip != NULL
 
3845
                   &&  lip != NULL
 
3846
                   &&  (next_offset_ptr == NULL 
 
3847
                     ||  line_counter < next_offset_ptr->ival - 1);
 
3848
                 sip = sip->next)
 
3849
            {
 
3850
                for (pattern_line_counter = 0;
 
3851
                     pattern_line_counter < sip->num_appearances
 
3852
                         &&  lip != NULL
 
3853
                         &&  (next_offset_ptr == NULL
 
3854
                             ||  line_counter < next_offset_ptr->ival - 1);
 
3855
                     pattern_line_counter ++)
 
3856
                {
 
3857
                    if ((int) strlen (lip->data) != sip->size_value) {
 
3858
                        s_ReportLineLengthError (curr_id, lip, sip->size_value,
 
3859
                                               afrp->report_error,
 
3860
                                               afrp->report_error_userdata);
 
3861
                    }
 
3862
                    afrp->sequences = s_AddAlignRawSeqById (afrp->sequences, 
 
3863
                                                          curr_id, 
 
3864
                                                          lip->data,
 
3865
                                                          lip->line_num,
 
3866
                                                          lip->line_num,
 
3867
                                                          lip->line_offset);
 
3868
                    lip = lip->next;
 
3869
                    line_counter ++;
 
3870
                }
 
3871
            }
 
3872
            if (sip != NULL  &&  lip != NULL) {
 
3873
                s_ReportBlockLengthError (curr_id, lip->line_num,
 
3874
                                        afrp->block_size,
 
3875
                                        line_counter - offset_ptr->ival,
 
3876
                                        afrp->report_error,
 
3877
                                        afrp->report_error_userdata);
 
3878
            }
 
3879
        }
 
3880
        curr_seg ++;
 
3881
        if (curr_seg >= afrp->num_segments)
 
3882
        {
 
3883
                curr_seg = 0;
 
3884
        }
 
3885
    }        
 
3886
}
 
3887
 
 
3888
 
 
3889
/* The following functions are used for analyzing contiguous data with
 
3890
 * marked IDs.
 
3891
 */
 
3892
 
 
3893
/* This function creates a new LengthList pattern for each marked ID.
 
3894
 * After each new list is created, the function checks to see if the
 
3895
 * new pattern matches any pattern already in the list of patterns seen.
 
3896
 * If so, the function deletes the new pattern and increments 
 
3897
 * num_appearances for the pattern in the list, otherwise the function
 
3898
 * adds the new pattern to the list.
 
3899
 * When the list is complete, the function finds the pattern with the 
 
3900
 * most appearances and returns that pattern as the anchor pattern to use
 
3901
 * when checking sequence data blocks for consistency with one another.
 
3902
 */
 
3903
static SLengthListPtr *
 
3904
s_CreateAnchorPatternForMarkedIDs 
 
3905
(SAlignRawFilePtr afrp)
 
3906
{
 
3907
    SLengthListPtr * list;
 
3908
    SLengthListPtr * best;
 
3909
    SLengthListPtr this_pattern;
 
3910
    char *         cp;
 
3911
    TLineInfoPtr   lip;
 
3912
    int            curr_seg;
 
3913
 
 
3914
    if (afrp == NULL) {
 
3915
        return NULL;
 
3916
    }
 
3917
 
 
3918
    /* initialize length lists */
 
3919
    list = (SLengthListPtr *) malloc (afrp->num_segments * sizeof (SLengthListPtr));
 
3920
    if (list == NULL) 
 
3921
    {
 
3922
        return NULL;
 
3923
    }
 
3924
    for (curr_seg = 0; curr_seg < afrp->num_segments; curr_seg ++)
 
3925
    {
 
3926
        list[curr_seg] = NULL;
 
3927
    }
 
3928
    /* initialize best ptrs */
 
3929
    /* list is one element longer, to hold null terminator */
 
3930
    best = (SLengthListPtr *) malloc ((afrp->num_segments + 1) * sizeof (SLengthListPtr));
 
3931
    if (best == NULL) 
 
3932
    {
 
3933
        return NULL;
 
3934
    }
 
3935
    for (curr_seg = 0; curr_seg < afrp->num_segments + 1; curr_seg ++)
 
3936
    {
 
3937
        best[curr_seg] = NULL;
 
3938
    }
 
3939
    
 
3940
    /* initialize pattern */
 
3941
    this_pattern = NULL;
 
3942
 
 
3943
    curr_seg = 0;
 
3944
    for (lip = afrp->line_list;
 
3945
         lip != NULL  &&  ! s_FoundStopLine (lip->data);
 
3946
         lip = lip->next)
 
3947
    {
 
3948
        if (lip->data == NULL) continue;
 
3949
        if (lip->data [0] == ']' || lip->data [0] == '[') continue;
 
3950
        if (lip->data [0] == '>') {
 
3951
            if (this_pattern != NULL) {
 
3952
                list [curr_seg] = s_AddLengthList (list [curr_seg], this_pattern);
 
3953
                curr_seg ++;
 
3954
                if (curr_seg >= afrp->num_segments) 
 
3955
                {
 
3956
                        curr_seg = 0;
 
3957
                }
 
3958
            }
 
3959
            this_pattern = s_LengthListNew (NULL);
 
3960
            if (this_pattern == NULL) {
 
3961
                for (curr_seg = 0; curr_seg < afrp->num_segments; curr_seg ++)
 
3962
                {
 
3963
                  s_LengthListFree (list [curr_seg]);
 
3964
                }
 
3965
                free (list);
 
3966
                return NULL;
 
3967
            }
 
3968
            this_pattern->num_appearances = 1;
 
3969
        } else if (this_pattern != NULL) {
 
3970
            /* This section gets rid of base pair number comments */
 
3971
            cp = lip->data;
 
3972
            while ( isspace ((int )*cp)  ||  isdigit ((int )*cp)) {
 
3973
                cp++;
 
3974
            }
 
3975
            s_AddLengthRepeat (this_pattern, strlen (cp));
 
3976
        }
 
3977
    }
 
3978
    if (this_pattern != NULL) {
 
3979
        list[curr_seg] = s_AddLengthList (list [curr_seg], this_pattern);
 
3980
    }
 
3981
 
 
3982
    /* Now find the pattern with the most appearances for each segment*/
 
3983
    for (curr_seg = 0; curr_seg < afrp->num_segments; curr_seg++)
 
3984
    {
 
3985
        for (this_pattern = list [curr_seg];
 
3986
             this_pattern != NULL;
 
3987
             this_pattern = this_pattern->next)
 
3988
        {
 
3989
            if (this_pattern->num_appearances == 0) continue;
 
3990
            if (best [curr_seg] == NULL 
 
3991
              ||  this_pattern->num_appearances > best[curr_seg]->num_appearances)
 
3992
            {
 
3993
                best[curr_seg] = this_pattern;
 
3994
            }
 
3995
            
 
3996
        }
 
3997
 
 
3998
        /* free all patterns before and after anchor pattern */
 
3999
        if (best [curr_seg] != NULL) {
 
4000
            s_LengthListFree (best [curr_seg]->next);
 
4001
            best [curr_seg]->next = NULL;
 
4002
        }
 
4003
 
 
4004
        if (best [curr_seg] != list [curr_seg]) {
 
4005
            this_pattern = list [curr_seg];
 
4006
            while ( this_pattern != NULL  &&  this_pattern->next != best[curr_seg] ) {
 
4007
                this_pattern = this_pattern->next;
 
4008
            }
 
4009
            if (this_pattern != NULL) {
 
4010
                this_pattern->next = NULL;
 
4011
                s_LengthListFree (list [curr_seg]);
 
4012
            }
 
4013
        }
 
4014
    }
 
4015
 
 
4016
    for (curr_seg = 0; curr_seg < afrp->num_segments; curr_seg ++)
 
4017
    {
 
4018
        if (best[curr_seg] == NULL) 
 
4019
        {
 
4020
                for (curr_seg = 0; curr_seg < afrp->num_segments; curr_seg ++)
 
4021
                {
 
4022
                        s_LengthListFree (best [curr_seg]);
 
4023
                }
 
4024
                return NULL;
 
4025
        }
 
4026
    }
 
4027
    
 
4028
    return best;
 
4029
}
 
4030
 
 
4031
 
 
4032
/* This function removes base pair count comments from the data sections
 
4033
 * for contiguous marked ID sequences.
 
4034
 */
 
4035
static void s_RemoveBasePairCountCommentsFromData (SAlignRawFilePtr afrp)
 
4036
{
 
4037
    TIntLinkPtr  this_offset, next_offset;
 
4038
    TLineInfoPtr lip;
 
4039
    int          line_count;
 
4040
    char *       cp;
 
4041
 
 
4042
    if (afrp == NULL  ||  afrp->offset_list == NULL) {
 
4043
        return;
 
4044
    }
 
4045
    this_offset = afrp->offset_list;
 
4046
    next_offset = this_offset->next;
 
4047
    lip = afrp->line_list;
 
4048
    line_count = 0;
 
4049
    while (lip != NULL  &&  this_offset != NULL) {
 
4050
        if (line_count == this_offset->ival) {
 
4051
            while (lip != NULL  && 
 
4052
                   (next_offset == NULL
 
4053
                   ||  line_count < next_offset->ival - 1)) {
 
4054
                cp = lip->data;
 
4055
                if (cp != NULL) {
 
4056
                    cp += strspn (cp, " \t\r\n1234567890");
 
4057
                    if (cp != lip->data) {
 
4058
                        strcpy (lip->data, cp);
 
4059
                    }
 
4060
                }
 
4061
                line_count ++;
 
4062
                lip = lip->next;
 
4063
            }
 
4064
            this_offset = this_offset->next;
 
4065
            if (this_offset != NULL) {
 
4066
                next_offset = this_offset->next;
 
4067
            }
 
4068
        } else {
 
4069
            line_count ++;
 
4070
            lip = lip->next;
 
4071
        }
 
4072
    }
 
4073
}
 
4074
 
 
4075
 
 
4076
/* This function assumes that the offset_list has already been populated
 
4077
 * with the locations of the data blocks.  It analyzes the blocks of data
 
4078
 * to find the most frequently occurring pattern of lengths of data and then
 
4079
 * uses that pattern to attach the data to the correct IDs and report any
 
4080
 * errors in formatting.
 
4081
 */
 
4082
static void s_ProcessAlignFileRawForMarkedIDs (SAlignRawFilePtr afrp)
 
4083
{
 
4084
    SLengthListPtr * anchorpattern;
 
4085
 
 
4086
    if (afrp == NULL) {
 
4087
        return;
 
4088
    }
 
4089
 
 
4090
    s_RemoveBasePairCountCommentsFromData (afrp);
 
4091
    anchorpattern = s_CreateAnchorPatternForMarkedIDs (afrp);
 
4092
    if (anchorpattern == NULL  ||  afrp->offset_list == NULL) {
 
4093
        return;
 
4094
    }
 
4095
    s_CreateSequencesBasedOnTokenPatterns (afrp->line_list, afrp->offset_list,
 
4096
                                         anchorpattern, afrp);
 
4097
}
 
4098
 
 
4099
 
 
4100
/* The following functions are used for analyzing contiguous sequence data
 
4101
 * without marked IDs.
 
4102
 */
 
4103
 
 
4104
/* This function left-shifts a string, character by character. */
 
4105
static void
 
4106
s_StringLeftShift
 
4107
(char * cp_from,
 
4108
 char * cp_to)
 
4109
{
 
4110
    if (cp_from == cp_to  ||  cp_from == NULL  ||  cp_to == NULL) {
 
4111
        return;
 
4112
    }
 
4113
    while (*cp_to != 0) {
 
4114
        *cp_from = *cp_to;
 
4115
        cp_from++;
 
4116
        cp_to++;
 
4117
    }
 
4118
    *cp_from = 0;
 
4119
}
 
4120
 
 
4121
 
 
4122
/* This function removes bracketed comments from a linked list of 
 
4123
 * SLineInfo structures.  The function returns a pointer to the
 
4124
 * list without the comments.
 
4125
 */
 
4126
static TLineInfoPtr s_RemoveCommentsFromTokens (TLineInfoPtr list)
 
4127
{
 
4128
    TLineInfoPtr  lip;
 
4129
    int           num_comment_starts;
 
4130
    char *        cp_l;
 
4131
    char *        cp_r;
 
4132
    char *        cp;
 
4133
    EBool         in_comment;
 
4134
 
 
4135
    num_comment_starts = 0;
 
4136
    in_comment = eFalse;
 
4137
    for (lip = list;  lip != NULL;  lip = lip->next) {
 
4138
        if (lip->data == NULL) {
 
4139
            lip->delete_me = eTrue;
 
4140
        } else {
 
4141
            cp_l = NULL;
 
4142
            cp_r = NULL;
 
4143
            for (cp = lip->data; *cp != 0; cp++) {
 
4144
                if (*cp == ']') {
 
4145
                    if (cp_r == NULL) {
 
4146
                        s_StringLeftShift (lip->data, cp + 1);
 
4147
                        cp = lip->data - 1;
 
4148
                    } else {
 
4149
                        s_StringLeftShift (cp_r, cp + 1);
 
4150
                        cp = cp_r;
 
4151
                        if (cp_r > lip->data) {
 
4152
                            cp_r --;
 
4153
                            while (cp_r >= lip->data  &&  *cp_r != '[') {
 
4154
                                cp_r --;
 
4155
                            }
 
4156
                            if (cp_r < lip->data) {
 
4157
                                cp_r = NULL;
 
4158
                            }
 
4159
                        } else {
 
4160
                            cp_r = NULL;
 
4161
                        }
 
4162
                    }
 
4163
                    if (num_comment_starts > 0) {
 
4164
                        num_comment_starts --;
 
4165
                    }
 
4166
                } else if (*cp == '[') {
 
4167
                    cp_r = cp;
 
4168
                    num_comment_starts ++;
 
4169
                }
 
4170
            }
 
4171
            if (in_comment) {
 
4172
                if (num_comment_starts == 0) {
 
4173
                    in_comment = eFalse;
 
4174
                } else {
 
4175
                    lip->delete_me = eTrue;
 
4176
                }
 
4177
            } else if (num_comment_starts > 0) {
 
4178
                cp_r = strchr (lip->data, '[');
 
4179
                if (cp_r != NULL) {
 
4180
                    *cp_r = 0;
 
4181
                }
 
4182
                in_comment = eTrue;
 
4183
            }
 
4184
            if (lip->data [0] == 0) {
 
4185
                lip->delete_me = eTrue;
 
4186
            }
 
4187
        }
 
4188
    }
 
4189
    list = s_DeleteLineInfos (list);
 
4190
    return list;
 
4191
}
 
4192
 
 
4193
 
 
4194
/* This function removes Nexus comments from a linked list of SLineInfo
 
4195
 * structures.  The function returns a pointer to the list without the
 
4196
 * comments.
 
4197
 */
 
4198
static TLineInfoPtr s_RemoveNexusCommentsFromTokens (TLineInfoPtr list) 
 
4199
{
 
4200
    TLineInfoPtr lip, start_lip, end_lip;
 
4201
 
 
4202
    lip = list;
 
4203
    start_lip = NULL;
 
4204
    end_lip = NULL;
 
4205
    while (lip != NULL) {
 
4206
        if (s_StringICmp (lip->data, "#NEXUS") == 0) {
 
4207
            start_lip = lip;
 
4208
            end_lip = lip;
 
4209
            while (end_lip != NULL 
 
4210
                   &&  s_StringICmp (end_lip->data, "matrix") != 0) {
 
4211
                end_lip = end_lip->next;
 
4212
            }
 
4213
            if (end_lip != NULL) {
 
4214
                while (start_lip != end_lip) {
 
4215
                    start_lip->delete_me = eTrue;
 
4216
                    start_lip = start_lip->next;
 
4217
                }
 
4218
                end_lip->delete_me = eTrue;
 
4219
                lip = end_lip->next;
 
4220
            } else {
 
4221
                lip = lip->next;
 
4222
            }
 
4223
        } else {
 
4224
            lip = lip->next;
 
4225
        }
 
4226
    }
 
4227
    list = s_DeleteLineInfos (list);
 
4228
    return list;
 
4229
}
 
4230
 
 
4231
 
 
4232
/* This function finds the number of characters that occur most frequently
 
4233
 * in a token and returns a pointer to a SSizeInfo structure that
 
4234
 * describes the most common length and the number of times it appears.
 
4235
 */
 
4236
static TSizeInfoPtr 
 
4237
s_FindMostFrequentlyOccurringTokenLength
 
4238
(TSizeInfoPtr list,
 
4239
 int          not_this_size)
 
4240
{
 
4241
    TSizeInfoPtr list_ptr, new_list, best_ptr, return_best;
 
4242
 
 
4243
    new_list = NULL;
 
4244
    for (list_ptr = list;  list_ptr != NULL;  list_ptr = list_ptr->next) {
 
4245
        if (not_this_size != list_ptr->size_value) {
 
4246
            new_list = s_AddSizeInfoAppearances (new_list,
 
4247
                                               list_ptr->size_value,
 
4248
                                               list_ptr->num_appearances);
 
4249
        }
 
4250
    }
 
4251
    best_ptr = s_GetMostPopularSizeInfo (new_list);
 
4252
    return_best = NULL;
 
4253
    if (best_ptr != NULL) {
 
4254
        return_best = s_SizeInfoNew (NULL);
 
4255
        if (return_best != NULL) {
 
4256
            return_best->size_value = best_ptr->size_value;
 
4257
            return_best->num_appearances = best_ptr->num_appearances;
 
4258
        }
 
4259
    }
 
4260
    s_SizeInfoFree (new_list);
 
4261
    return return_best;
 
4262
}
 
4263
 
 
4264
 
 
4265
/* This function examines all instances of an anchor pattern in the data
 
4266
 * and checks to see if the line immediately after the anchor pattern should
 
4267
 * be used as part of the anchor pattern.  This function exists because 
 
4268
 * frequently, but not always, contiguous data will consist of multiple lines
 
4269
 * of data of the same length (for example, 80 characters), followed by one
 
4270
 * shorter line with the remaining data.  We must also make sure that we do
 
4271
 * not accidentally include the ID of the next sequence in the data of the
 
4272
 * previous sequence.
 
4273
 */
 
4274
static void 
 
4275
s_ExtendAnchorPattern 
 
4276
(SLengthListPtr anchorpattern,
 
4277
 TSizeInfoPtr   line_lengths)
 
4278
{
 
4279
    TSizeInfoPtr last_line_lengths, sip, sip_next, twoafter;
 
4280
    int         best_last_line_length;
 
4281
    int         anchor_line_length;
 
4282
 
 
4283
    if (anchorpattern == NULL 
 
4284
        ||  anchorpattern->lengthrepeats == NULL
 
4285
        ||  line_lengths == NULL) {
 
4286
       return;
 
4287
    }
 
4288
 
 
4289
    last_line_lengths = NULL;
 
4290
    anchor_line_length = anchorpattern->lengthrepeats->size_value;
 
4291
 
 
4292
    /* also check to make sure that there's more than one line between
 
4293
     * this pattern and the next pattern, otherwise the next line is the
 
4294
     * ID for the next pattern and shouldn't be included in the anchor
 
4295
     */
 
4296
    for (sip = line_lengths;  sip != NULL;  sip = sip->next) {
 
4297
        if (s_SizeInfoIsEqual (sip, anchorpattern->lengthrepeats)) {
 
4298
            sip_next = sip->next;
 
4299
            if (sip_next != NULL
 
4300
                &&  sip_next->size_value > 0
 
4301
                &&  sip_next->size_value != anchor_line_length
 
4302
                &&  ((twoafter = sip_next->next) == NULL
 
4303
                   ||  twoafter->size_value != anchor_line_length))
 
4304
            {
 
4305
                last_line_lengths = s_AddSizeInfo (last_line_lengths,
 
4306
                                                 sip_next->size_value);
 
4307
            }
 
4308
        }
 
4309
    }
 
4310
    best_last_line_length = s_GetMostPopularSize (last_line_lengths);
 
4311
    if (best_last_line_length > 0) {
 
4312
        s_AddLengthRepeat (anchorpattern, best_last_line_length);
 
4313
    }
 
4314
    s_SizeInfoFree (last_line_lengths);
 
4315
} 
 
4316
 
 
4317
 
 
4318
/* This function looks for the most frequently occurring pattern, where a 
 
4319
 * pattern is considered to be N contiguous tokens of M characters.  The
 
4320
 * function then checks to see if there is usually a token of a particular
 
4321
 * length that immediately follows this pattern that is not the ID for the
 
4322
 * next sequence.  If so, this line length is added to the pattern.
 
4323
 * The function returns a pointer to this pattern.
 
4324
 */
 
4325
static SLengthListPtr s_FindMostPopularPattern (TSizeInfoPtr list)
 
4326
{
 
4327
    SLengthListPtr patternlist, newpattern;
 
4328
    TSizeInfoPtr   sip, popular_line_length;
 
4329
    SLengthListPtr index, best;
 
4330
    int           not_this_length;
 
4331
 
 
4332
    patternlist = NULL;
 
4333
    for (sip = list;  sip != NULL;  sip = sip->next) {
 
4334
        if (sip->size_value > 0) {
 
4335
            newpattern = s_LengthListNew (NULL);
 
4336
            if (newpattern == NULL) {
 
4337
                s_LengthListFree (patternlist);
 
4338
                return NULL;
 
4339
            }
 
4340
            newpattern->num_appearances = 1;
 
4341
            newpattern->lengthrepeats = s_SizeInfoNew (NULL);
 
4342
            if (newpattern->lengthrepeats == NULL) {
 
4343
                s_LengthListFree (patternlist);
 
4344
                return NULL;
 
4345
            }
 
4346
            newpattern->lengthrepeats->size_value = sip->size_value;
 
4347
            newpattern->lengthrepeats->num_appearances = sip->num_appearances;
 
4348
            patternlist = s_AddLengthList (patternlist, newpattern);
 
4349
        }
 
4350
    }
 
4351
    if (patternlist == NULL) {
 
4352
        return NULL;
 
4353
    }
 
4354
 
 
4355
    best = NULL;
 
4356
    for (index = patternlist;  index != NULL;  index = index->next) {
 
4357
        if (index->lengthrepeats->num_appearances < 2) {
 
4358
            continue;
 
4359
        }
 
4360
        if (best==NULL  ||  best->num_appearances < index->num_appearances) {
 
4361
            best = index;
 
4362
        } else if (best->num_appearances == index->num_appearances
 
4363
            &&  best->lengthrepeats->size_value < 
 
4364
                                  index->lengthrepeats->size_value) {
 
4365
            best = index;
 
4366
        }
 
4367
    }
 
4368
 
 
4369
    /* Free data in list before best pattern */
 
4370
    index = patternlist;
 
4371
    while ( index != NULL  &&  index->next != best ) {
 
4372
         index = index->next;
 
4373
    }
 
4374
    if (index != NULL) {
 
4375
        index->next = NULL;
 
4376
        s_LengthListFree (patternlist);
 
4377
    }
 
4378
    /* Free data in list after best pattern */
 
4379
    if (best != NULL) {
 
4380
        s_LengthListFree (best->next);
 
4381
        best->next = NULL;
 
4382
    }
 
4383
 
 
4384
    popular_line_length = s_FindMostFrequentlyOccurringTokenLength (list, 0);
 
4385
 
 
4386
    if (best != NULL  &&  best->lengthrepeats != NULL
 
4387
      &&  popular_line_length != NULL
 
4388
      &&  best->lengthrepeats->size_value == popular_line_length->size_value)
 
4389
    {
 
4390
        not_this_length = popular_line_length->size_value;
 
4391
        s_SizeInfoFree (popular_line_length);
 
4392
        popular_line_length = s_FindMostFrequentlyOccurringTokenLength (list,
 
4393
                                                        not_this_length);
 
4394
    }
 
4395
 
 
4396
    if (best == NULL
 
4397
        ||  (popular_line_length != NULL
 
4398
          &&  popular_line_length->size_value > best->lengthrepeats->size_value
 
4399
          &&  popular_line_length->num_appearances > best->num_appearances))
 
4400
    {
 
4401
        if (best == NULL) {
 
4402
            best = s_LengthListNew (NULL);
 
4403
            if (best == NULL) {
 
4404
                return NULL;
 
4405
            }
 
4406
        }
 
4407
        best->lengthrepeats = s_SizeInfoNew (NULL);
 
4408
        if (best->lengthrepeats == NULL) {
 
4409
            return NULL;
 
4410
        }
 
4411
        best->lengthrepeats->size_value = popular_line_length->size_value;
 
4412
        best->lengthrepeats->num_appearances = 1;
 
4413
    } else {
 
4414
        /* extend anchor pattern to include best length of last line */
 
4415
        s_ExtendAnchorPattern (best, list);
 
4416
    }
 
4417
 
 
4418
    s_SizeInfoFree (popular_line_length);
 
4419
 
 
4420
    return best;
 
4421
}
 
4422
 
 
4423
 
 
4424
/* This function creates an SIntLink list to describe the locations
 
4425
 * of occurrences of the anchorpattern in the SSizeInfo list.
 
4426
 * The function returns a pointer to the SIntLink list.
 
4427
 */
 
4428
static TIntLinkPtr 
 
4429
s_CreateOffsetList 
 
4430
(TSizeInfoPtr list,
 
4431
 SLengthListPtr anchorpattern)
 
4432
{
 
4433
    int          line_counter;
 
4434
    TIntLinkPtr  offset_list, new_offset;
 
4435
    TSizeInfoPtr sip, prev_sip;
 
4436
 
 
4437
    if (list == NULL  ||  anchorpattern == NULL) {
 
4438
        return NULL;
 
4439
    }
 
4440
    line_counter = 0;
 
4441
    offset_list = NULL;
 
4442
    prev_sip = NULL;
 
4443
    for (sip = list;  sip != NULL;  sip = sip->next) {
 
4444
        if (s_SizeInfoIsEqual (sip, anchorpattern->lengthrepeats)) {
 
4445
            new_offset = s_IntLinkNew (line_counter, offset_list);
 
4446
            if (new_offset == NULL) {
 
4447
                s_IntLinkFree (offset_list);
 
4448
                return NULL;
 
4449
            }
 
4450
            if (offset_list == NULL) {
 
4451
                offset_list = new_offset;
 
4452
            }
 
4453
        }
 
4454
 
 
4455
        line_counter += sip->num_appearances;
 
4456
        prev_sip = sip;
 
4457
    }
 
4458
    return offset_list;
 
4459
}
 
4460
 
 
4461
 
 
4462
/* This function determines whether or not the number of expected sequence
 
4463
 * characters are available starting at a token after line_start and stopping
 
4464
 * at least one token before the next known sequence data block in the list.
 
4465
 * If so, the function returns the number of the token at which the sequence
 
4466
 * data begins.  Otherwise the function returns -1.
 
4467
 */
 
4468
static int  
 
4469
s_ForecastPattern 
 
4470
(int          line_start,
 
4471
 int          pattern_length,
 
4472
 TIntLinkPtr  next_offset,
 
4473
 int          sip_offset,
 
4474
 TSizeInfoPtr list)
 
4475
{
 
4476
    int  offset, end_offset;
 
4477
    TSizeInfoPtr sip;
 
4478
    int  line_counter, num_chars;
 
4479
  
 
4480
    if (list == NULL) {
 
4481
        return -1;
 
4482
    }
 
4483
 
 
4484
    for (offset = sip_offset; offset < list->num_appearances; offset++) {
 
4485
        line_counter = line_start + offset;
 
4486
        num_chars = list->size_value * (list->num_appearances - offset); 
 
4487
        sip = list;
 
4488
        while (num_chars < pattern_length
 
4489
                &&  (next_offset == NULL  ||  line_counter < next_offset->ival)
 
4490
                &&  sip->next != NULL)
 
4491
        {
 
4492
            sip = sip->next;
 
4493
            for (end_offset = 0;
 
4494
                 end_offset < sip->num_appearances
 
4495
                     &&  num_chars < pattern_length
 
4496
                     &&  (next_offset == NULL
 
4497
                          ||  line_counter < next_offset->ival);
 
4498
                 end_offset ++)
 
4499
            {
 
4500
                num_chars += sip->size_value;
 
4501
                line_counter ++;
 
4502
            }
 
4503
        }
 
4504
        if (num_chars == pattern_length) {
 
4505
            return line_start + offset;
 
4506
        }
 
4507
    }
 
4508
    return -1;
 
4509
}
 
4510
 
 
4511
 
 
4512
/* This function examines the offset list and searches for holes where blocks
 
4513
 * of sequence data without the exact expected formatting might exist.  The
 
4514
 * function adds the offsets of any new blocks to the list and returns a
 
4515
 * pointer to the augmented offset list.
 
4516
 */
 
4517
static TIntLinkPtr 
 
4518
s_AugmentOffsetList 
 
4519
(TIntLinkPtr    offset_list,
 
4520
 TSizeInfoPtr   list,
 
4521
 SLengthListPtr anchorpattern)
 
4522
{
 
4523
    int           pattern_length;
 
4524
    TSizeInfoPtr  sip;
 
4525
    TIntLinkPtr   prev_offset, next_offset, new_offset;
 
4526
    int           line_counter, forecast_position, line_skip;
 
4527
    EBool         skipped_previous = eFalse;
 
4528
    int           num_chars;
 
4529
 
 
4530
    if (list == NULL  ||  anchorpattern == NULL) {
 
4531
        return offset_list;
 
4532
    }
 
4533
 
 
4534
    pattern_length = 0;
 
4535
    for (sip = anchorpattern->lengthrepeats;  sip != NULL;  sip = sip->next) {
 
4536
        pattern_length += (sip->size_value * sip->num_appearances);
 
4537
    }
 
4538
    if (pattern_length == 0) {
 
4539
        return offset_list;
 
4540
    }
 
4541
 
 
4542
    prev_offset = NULL;
 
4543
    next_offset = offset_list;
 
4544
    line_counter = 0;
 
4545
    sip = list;
 
4546
    while (sip != NULL) {
 
4547
        /* if we are somehow out of synch, don't get caught in infinite loop */
 
4548
        if (next_offset != NULL  &&  line_counter > next_offset->ival) {
 
4549
            next_offset = next_offset->next;
 
4550
        } else if (next_offset != NULL  &&  line_counter == next_offset->ival) {
 
4551
            skipped_previous = eFalse;
 
4552
            prev_offset = next_offset;
 
4553
            next_offset = next_offset->next;
 
4554
            /* advance sip and line counter past the end of this pattern */
 
4555
            num_chars = 0;
 
4556
            while (num_chars < pattern_length  &&  sip != NULL) {
 
4557
                num_chars += sip->size_value * sip->num_appearances;
 
4558
                line_counter += sip->num_appearances;
 
4559
                sip = sip->next;
 
4560
            }
 
4561
        } else if (skipped_previous) {
 
4562
            line_skip = 0;
 
4563
            while (sip != NULL  &&  line_skip < sip->num_appearances 
 
4564
                  &&  (next_offset == NULL
 
4565
                       ||  line_counter < next_offset->ival)) {
 
4566
                /* see if we can build a pattern that matches the pattern 
 
4567
                 * length we want
 
4568
                 */
 
4569
                forecast_position = s_ForecastPattern (line_counter,
 
4570
                                                     pattern_length,
 
4571
                                                     next_offset, line_skip,
 
4572
                                                     sip);
 
4573
                if (forecast_position > 0) {
 
4574
                    new_offset = s_IntLinkNew (forecast_position, NULL);
 
4575
                    if (new_offset == NULL) {
 
4576
                        return NULL;
 
4577
                    }
 
4578
                    if (prev_offset == NULL) {
 
4579
                        new_offset->next = offset_list;
 
4580
                        offset_list = new_offset;
 
4581
                    } else {
 
4582
                        new_offset->next = next_offset;
 
4583
                        prev_offset->next = new_offset;
 
4584
                    }
 
4585
                    prev_offset = new_offset;
 
4586
                    /* now advance sip and line counter past the end 
 
4587
                     * of the pattern we have just created
 
4588
                     */
 
4589
                    num_chars = 0;
 
4590
                    while (num_chars < pattern_length  &&  sip != NULL) {
 
4591
                        for (line_skip = 0;
 
4592
                             line_skip < sip->num_appearances
 
4593
                                 &&  num_chars < pattern_length;
 
4594
                             line_skip++)
 
4595
                        {
 
4596
                            num_chars += sip->size_value;
 
4597
                            line_counter ++;
 
4598
                        }
 
4599
                        if (line_skip == sip->num_appearances) {
 
4600
                            sip = sip->next;
 
4601
                            line_skip = 0;
 
4602
                        }
 
4603
                    }
 
4604
                } else {
 
4605
                    line_counter += sip->num_appearances;
 
4606
                    sip = sip->next;
 
4607
                    line_skip = 0;
 
4608
                }
 
4609
            }
 
4610
        } else {
 
4611
            skipped_previous = eTrue;
 
4612
            line_counter += sip->num_appearances;
 
4613
            sip = sip->next;
 
4614
        }
 
4615
    }
 
4616
    return offset_list;
 
4617
}
 
4618
 
 
4619
 
 
4620
/* This function finds the most frequently occurring distance between
 
4621
 * two sequence data blocks and returns that value.
 
4622
 */
 
4623
static int  s_GetMostPopularPatternLength (TIntLinkPtr offset_list)
 
4624
{
 
4625
    int          line_counter, best_length;
 
4626
    TSizeInfoPtr pattern_length_list;
 
4627
    TIntLinkPtr  offset;
 
4628
 
 
4629
    if (offset_list == NULL) {
 
4630
        return -1;
 
4631
    }
 
4632
 
 
4633
    line_counter = -1;
 
4634
    pattern_length_list = NULL;
 
4635
    for (offset = offset_list;  offset != NULL;  offset = offset->next) {
 
4636
        if (line_counter != -1) {
 
4637
            pattern_length_list = s_AddSizeInfo (pattern_length_list,
 
4638
                                               offset->ival - line_counter);
 
4639
        }
 
4640
        line_counter = offset->ival;
 
4641
    }
 
4642
    best_length = s_GetMostPopularSize (pattern_length_list);
 
4643
    s_SizeInfoFree (pattern_length_list);
 
4644
    return best_length;
 
4645
}
 
4646
 
 
4647
 
 
4648
/* This function finds the most frequently appearing number of characters 
 
4649
 * in a block of sequence data and returns that value.
 
4650
 */
 
4651
static int 
 
4652
s_GetBestCharacterLength 
 
4653
(TLineInfoPtr token_list,
 
4654
 TIntLinkPtr  offset_list,
 
4655
 int          block_length)
 
4656
{
 
4657
    TLineInfoPtr lip;
 
4658
    TIntLinkPtr  prev_offset, new_offset;
 
4659
    int          line_diff, num_chars, best_num_chars;
 
4660
    TSizeInfoPtr pattern_length_list = NULL;
 
4661
 
 
4662
    if (token_list == NULL  ||  offset_list == NULL  ||  block_length < 1) {
 
4663
        return -1;
 
4664
    }
 
4665
    /* get length of well-formatted block size */
 
4666
    lip = token_list;
 
4667
    prev_offset = NULL;
 
4668
    for (new_offset = offset_list;
 
4669
         new_offset != NULL  &&  lip != NULL;
 
4670
         new_offset = new_offset->next)
 
4671
    {
 
4672
        if (prev_offset == NULL) {
 
4673
            /* skip first tokens */
 
4674
            for (line_diff = 0;
 
4675
                 line_diff < new_offset->ival  &&  lip != NULL;
 
4676
                 line_diff ++)
 
4677
            {
 
4678
                lip = lip->next;
 
4679
            }
 
4680
        }
 
4681
        if (prev_offset != NULL) {
 
4682
            num_chars = 0;
 
4683
            for (line_diff = 0;
 
4684
                 line_diff < new_offset->ival - prev_offset->ival
 
4685
                     &&  lip != NULL;
 
4686
                 line_diff ++)
 
4687
            {
 
4688
                if (line_diff < new_offset->ival - prev_offset->ival - 1) {
 
4689
                    num_chars += strlen (lip->data);
 
4690
                }
 
4691
                lip = lip->next;
 
4692
            }
 
4693
            if (new_offset->ival - prev_offset->ival == block_length) {
 
4694
                pattern_length_list = s_AddSizeInfo (pattern_length_list,
 
4695
                                                   num_chars);
 
4696
            }
 
4697
        }
 
4698
        prev_offset = new_offset;
 
4699
    }
 
4700
    best_num_chars = s_GetMostPopularSize (pattern_length_list);
 
4701
    if (best_num_chars == 0  &&  pattern_length_list != NULL) {
 
4702
        best_num_chars = pattern_length_list->size_value;
 
4703
    }
 
4704
    s_SizeInfoFree (pattern_length_list);
 
4705
    pattern_length_list = NULL;
 
4706
    return best_num_chars;
 
4707
}
 
4708
 
 
4709
 
 
4710
static int  
 
4711
s_CountCharactersBetweenOffsets 
 
4712
(TLineInfoPtr list,
 
4713
 int          distance,
 
4714
 int          desired_num_chars)
 
4715
{
 
4716
    int          line_diff, num_chars, total_chars, pattern_length, num_starts;
 
4717
    TLineInfoPtr lip;
 
4718
    TIntLinkPtr  length_list, start_list, start_ptr, length;
 
4719
    int          start_of_unknown;
 
4720
    int          num_additional_offsets_needed;
 
4721
 
 
4722
    if (list == NULL  ||  distance == 0  ||  desired_num_chars == 0) {
 
4723
        return 0;
 
4724
    }
 
4725
 
 
4726
    /* because the first offset is the start of a known pattern, we should
 
4727
     * skip to the end of that pattern and start looking for additional
 
4728
     * offsets
 
4729
     */
 
4730
    total_chars = 0;
 
4731
    for (lip = list, line_diff = 0;
 
4732
         lip != NULL  &&  line_diff < distance
 
4733
             &&  total_chars < desired_num_chars;
 
4734
         lip = lip->next, line_diff++) {
 
4735
        num_chars = strlen (lip->data);
 
4736
        total_chars += num_chars;
 
4737
    }
 
4738
    while (lip != NULL && line_diff < distance  &&  s_IsBlank (lip->data)) {
 
4739
        lip = lip->next;
 
4740
        line_diff ++;
 
4741
    }
 
4742
    /* skip over line we would need for ID */
 
4743
    if (lip != NULL) {
 
4744
        lip = lip->next;
 
4745
        line_diff ++;
 
4746
    }
 
4747
  
 
4748
    if (lip == NULL  ||  line_diff == distance) {
 
4749
        return 0;
 
4750
    }
 
4751
    num_starts = 1;
 
4752
    list = lip->next;
 
4753
    start_of_unknown = line_diff;
 
4754
 
 
4755
    length_list = NULL;
 
4756
    total_chars = 0;
 
4757
    for (lip = list;
 
4758
         lip != NULL  &&  line_diff < distance;
 
4759
         lip = lip->next, line_diff++)
 
4760
    {
 
4761
        num_chars = strlen (lip->data);
 
4762
        length = s_IntLinkNew (num_chars, length_list);
 
4763
        if (length_list == NULL) {
 
4764
            length_list = length;
 
4765
        }
 
4766
        total_chars += num_chars;
 
4767
    }
 
4768
 
 
4769
    /* how many offsets do we need? */
 
4770
    num_additional_offsets_needed = (total_chars / desired_num_chars);
 
4771
    if (num_additional_offsets_needed == 0) {
 
4772
        return 0;
 
4773
    }
 
4774
 
 
4775
    /* Find all the places you could start and get the exact right number
 
4776
     * of characters
 
4777
     */
 
4778
    start_list = NULL;
 
4779
    num_starts = 0;
 
4780
    pattern_length = 0;
 
4781
    for (start_ptr = length_list, line_diff = start_of_unknown;
 
4782
         start_ptr != NULL  &&  line_diff < distance
 
4783
           &&  pattern_length < distance - line_diff ;
 
4784
         start_ptr = start_ptr->next, line_diff++) {
 
4785
        num_chars = start_ptr->ival;
 
4786
        pattern_length = 1;
 
4787
        length = start_ptr->next;
 
4788
        while (num_chars < desired_num_chars
 
4789
               &&  pattern_length + line_diff < distance
 
4790
               &&  length != NULL)
 
4791
        {
 
4792
            num_chars += length->ival;
 
4793
            pattern_length ++;
 
4794
            length = length->next;
 
4795
        }
 
4796
        if (num_chars == desired_num_chars) {
 
4797
            length = s_IntLinkNew (line_diff, start_list);
 
4798
            if (start_list == NULL) {
 
4799
                start_list = length;
 
4800
            }
 
4801
            num_starts ++;
 
4802
        }
 
4803
    }
 
4804
 
 
4805
    /* now select best set of start points */
 
4806
    
 
4807
    s_IntLinkFree (length_list);
 
4808
    s_IntLinkFree (start_list);
 
4809
    return 0;
 
4810
}
 
4811
 
 
4812
 
 
4813
/* This function inserts new block locations into the offset_list
 
4814
 * by looking for likely starts of abnormal patterns.
 
4815
 */
 
4816
static void s_InsertNewOffsets
 
4817
(TLineInfoPtr token_list,
 
4818
 TIntLinkPtr  offset_list,
 
4819
 int          block_length,
 
4820
 int          best_num_chars,
 
4821
 char *       alphabet)
 
4822
{
 
4823
    TLineInfoPtr lip, prev_start;
 
4824
    TIntLinkPtr  prev_offset, new_offset, splice_offset;
 
4825
    int          line_diff, num_chars, line_start;
 
4826
 
 
4827
    if (token_list == NULL  ||  offset_list == NULL
 
4828
        ||  block_length < 1  ||  best_num_chars < 1)
 
4829
    {
 
4830
        return;
 
4831
    }
 
4832
 
 
4833
    lip = token_list;
 
4834
    prev_offset = NULL;
 
4835
    for (new_offset = offset_list;
 
4836
         new_offset != NULL  &&  lip != NULL;
 
4837
         new_offset = new_offset->next) {
 
4838
        if (prev_offset == NULL) {
 
4839
            /* just advance through tokens */
 
4840
            for (line_diff = 0;
 
4841
                 line_diff < new_offset->ival  &&  lip != NULL;
 
4842
                 line_diff ++) {
 
4843
                lip = lip->next;
 
4844
            }
 
4845
        } else {
 
4846
            if (new_offset->ival - prev_offset->ival == block_length) {
 
4847
                /* just advance through tokens */
 
4848
                for (line_diff = 0;
 
4849
                     line_diff < new_offset->ival - prev_offset->ival 
 
4850
                         &&  lip != NULL;
 
4851
                     line_diff ++) {
 
4852
                    lip = lip->next;
 
4853
                }
 
4854
            } else {
 
4855
                /* look for intermediate breaks */
 
4856
                prev_start = lip;
 
4857
                num_chars = 0;
 
4858
                for (line_diff = 0;
 
4859
                     line_diff < new_offset->ival - prev_offset->ival
 
4860
                         &&  lip != NULL  &&  num_chars < best_num_chars;
 
4861
                     line_diff ++) {
 
4862
                    num_chars += strlen (lip->data);
 
4863
                    lip = lip->next;
 
4864
                }
 
4865
                if (lip == NULL) {
 
4866
                  return;
 
4867
                }
 
4868
                /* set new offset at first line of next pattern */
 
4869
                line_diff ++;
 
4870
                lip = lip->next;
 
4871
                if (line_diff < new_offset->ival - prev_offset->ival) {
 
4872
                    line_start = line_diff + prev_offset->ival;
 
4873
                    /* advance token pointer to new piece */
 
4874
                    while (line_diff < new_offset->ival - prev_offset->ival
 
4875
                           &&  lip != NULL)
 
4876
                    {
 
4877
                        lip = lip->next;
 
4878
                        line_diff ++;
 
4879
                    }
 
4880
                    /* insert new offset value */
 
4881
                    splice_offset = s_IntLinkNew (line_start, NULL);
 
4882
                    if (splice_offset == NULL) {
 
4883
                        return;
 
4884
                    }
 
4885
                    splice_offset->next = new_offset;
 
4886
                    prev_offset->next = splice_offset;
 
4887
 
 
4888
                    s_CountCharactersBetweenOffsets (lip,
 
4889
                                       new_offset->ival - splice_offset->ival,
 
4890
                                       best_num_chars);
 
4891
                }
 
4892
            }
 
4893
        }
 
4894
        prev_offset = new_offset;
 
4895
    }
 
4896
    
 
4897
    /* iterate through the last block */
 
4898
    for (line_diff = 0;
 
4899
         line_diff < block_length && lip != NULL; 
 
4900
         line_diff ++) {
 
4901
        lip = lip->next;
 
4902
    }
 
4903
 
 
4904
    /* if we have room for one more sequence, or even most of one more sequence, add it */
 
4905
    if (lip != NULL  &&  ! s_SkippableString (lip->data)) {
 
4906
        splice_offset = s_IntLinkNew (line_diff + prev_offset->ival, prev_offset);
 
4907
    }
 
4908
}
 
4909
 
 
4910
 
 
4911
/* This function returns true if the string contains digits, false otherwise */
 
4912
static EBool s_ContainsDigits (char *data)
 
4913
{
 
4914
    char *cp;
 
4915
 
 
4916
    if (data == NULL) return eFalse;
 
4917
    for (cp = data; *cp != 0; cp++) {
 
4918
        if (isdigit (*cp)) {
 
4919
            return eTrue;
 
4920
        }
 
4921
    }
 
4922
    return eFalse;
 
4923
}
 
4924
 
 
4925
 
 
4926
/* This function processes the alignment file data by dividing the original
 
4927
 * lines into pieces based on whitespace and looking for patterns of length 
 
4928
 * in the data. 
 
4929
 */
 
4930
static void s_ProcessAlignFileRawByLengthPattern (SAlignRawFilePtr afrp)
 
4931
{
 
4932
    TLineInfoPtr   token_list;
 
4933
    SLengthListPtr list;
 
4934
    TLineInfoPtr   lip;
 
4935
    SLengthListPtr anchorpattern[2];
 
4936
    TIntLinkPtr    offset_list;
 
4937
    int            best_length;
 
4938
    int            best_num_chars;
 
4939
 
 
4940
    if (afrp == NULL  ||  afrp->line_list == NULL) {
 
4941
        return;
 
4942
    }
 
4943
 
 
4944
    token_list = s_BuildTokenList (afrp->line_list);
 
4945
    token_list = s_RemoveCommentsFromTokens (token_list);
 
4946
    token_list = s_RemoveNexusCommentsFromTokens (token_list);
 
4947
 
 
4948
    list = s_LengthListNew ( NULL );
 
4949
    for (lip = token_list;
 
4950
         lip != NULL  &&  ! s_FoundStopLine (lip->data);
 
4951
         lip = lip->next)
 
4952
    {
 
4953
        if (s_SkippableString (lip->data)  ||  s_ContainsDigits(lip->data)) {
 
4954
            s_AddLengthRepeat (list, 0);
 
4955
        } else {
 
4956
            s_AddLengthRepeat (list, strlen (lip->data));
 
4957
        }
 
4958
    }
 
4959
 
 
4960
    anchorpattern [0] = s_FindMostPopularPattern (list->lengthrepeats);
 
4961
    anchorpattern [1] = NULL;
 
4962
    if (anchorpattern [0] == NULL  ||  anchorpattern[0]->lengthrepeats == NULL) {
 
4963
        return;
 
4964
    }
 
4965
 
 
4966
    /* find anchor patterns in original list, 
 
4967
     * find distances between anchor patterns 
 
4968
     */
 
4969
    offset_list = s_CreateOffsetList (list->lengthrepeats, anchorpattern[0]);
 
4970
    offset_list = s_AugmentOffsetList (offset_list,
 
4971
                                     list->lengthrepeats,
 
4972
                                     anchorpattern[0]);
 
4973
 
 
4974
    /* resolve unusual distances between anchor patterns */
 
4975
    best_length = s_GetMostPopularPatternLength (offset_list);
 
4976
    if (best_length < 1  &&  offset_list != NULL  && offset_list->next != NULL) {
 
4977
        best_length = offset_list->next->ival - offset_list->ival;
 
4978
    }
 
4979
    best_num_chars = s_GetBestCharacterLength (token_list, offset_list,
 
4980
                                             best_length);
 
4981
    s_InsertNewOffsets (token_list, offset_list, best_length, best_num_chars,
 
4982
                      afrp->alphabet);
 
4983
 
 
4984
    /* use token before each anchor pattern as ID, use tokens for distance
 
4985
     * between anchor patterns for sequence data
 
4986
     */
 
4987
    s_CreateSequencesBasedOnTokenPatterns (token_list, offset_list,
 
4988
                                       anchorpattern, afrp);
 
4989
  
 
4990
    s_LengthListFree (anchorpattern[0]);
 
4991
    s_LengthListFree (list);
 
4992
    s_LineInfoFree (token_list);
 
4993
}
 
4994
 
 
4995
 
 
4996
/* The following functions are used to convert data from the internal
 
4997
 * representation into the form that will be passed to the calling
 
4998
 * program.  Information from the ID strings is parsed to remove
 
4999
 * definition lines and organism information, the gap characters are
 
5000
 * standardized to '-', the missing characters are standardizes to 'N',
 
5001
 * match characters are replaced with characters from the first record,
 
5002
 * and bad characters are reported.
 
5003
 */
 
5004
 
 
5005
/* This function allocates memory for a new AligmentFileData structure
 
5006
 * and initializes its member variables.
 
5007
 */
 
5008
extern TAlignmentFilePtr AlignmentFileNew (void)
 
5009
{
 
5010
    TAlignmentFilePtr afp;
 
5011
 
 
5012
    afp = (TAlignmentFilePtr) malloc (sizeof (SAlignmentFile));
 
5013
    if (afp == NULL) {
 
5014
        return NULL;
 
5015
    }
 
5016
    afp->num_sequences = 0;
 
5017
    afp->num_organisms = 0;
 
5018
    afp->num_deflines  = 0;
 
5019
    afp->num_segments  = 0;
 
5020
    afp->ids           = NULL;
 
5021
    afp->sequences     = NULL;
 
5022
    afp->organisms     = NULL;
 
5023
    afp->deflines      = NULL;
 
5024
    return afp;
 
5025
}
 
5026
 
 
5027
 
 
5028
/* This function frees the memory associated with an AligmentFileData
 
5029
 * structure and its member variables.
 
5030
 */
 
5031
extern void AlignmentFileFree (TAlignmentFilePtr afp)
 
5032
{
 
5033
    int  index;
 
5034
 
 
5035
    if (afp == NULL) {
 
5036
        return;
 
5037
    }
 
5038
    if (afp->ids != NULL) {
 
5039
        for (index = 0;  index < afp->num_sequences;  index++) {
 
5040
            free (afp->ids [index]);
 
5041
        }  
 
5042
        free (afp->ids);
 
5043
        afp->ids = NULL;
 
5044
    }
 
5045
    if (afp->sequences != NULL) {
 
5046
        for (index = 0;  index < afp->num_sequences;  index++) {
 
5047
            free (afp->sequences [index]);
 
5048
        }  
 
5049
        free (afp->sequences);
 
5050
        afp->sequences = NULL;
 
5051
    }
 
5052
    if (afp->organisms != NULL) {
 
5053
        for (index = 0;  index < afp->num_organisms;  index++) {
 
5054
            free (afp->organisms [index]);
 
5055
        }  
 
5056
        free (afp->organisms);
 
5057
        afp->sequences = NULL;
 
5058
    }
 
5059
    if (afp->deflines != NULL) {
 
5060
        for (index = 0;  index < afp->num_deflines;  index++) {
 
5061
            free (afp->deflines [index]);
 
5062
        }  
 
5063
        free (afp->deflines);
 
5064
        afp->deflines = NULL;
 
5065
    }
 
5066
    free (afp);
 
5067
}
 
5068
 
 
5069
 
 
5070
/* This function parses the identifier string used by the alignment file
 
5071
 * to identify a sequence to find the portion of the string that is actually
 
5072
 * an ID, as opposed to organism information or definition line.
 
5073
 */
 
5074
static char * s_GetIdFromString (char * str)
 
5075
{
 
5076
    char * cp;
 
5077
    char * id;
 
5078
    int    len;
 
5079
 
 
5080
    if (str == NULL) {
 
5081
        return NULL;
 
5082
    }
 
5083
 
 
5084
    cp = str;
 
5085
    cp += strspn (str, " >\t");
 
5086
    len = strcspn (cp, " \t\r\n");
 
5087
    if (len == 0) {
 
5088
        return NULL;
 
5089
    }
 
5090
    id = malloc (len + 1);
 
5091
    if (id == NULL) {
 
5092
        return NULL;
 
5093
    }
 
5094
    strncpy (id, cp, len);
 
5095
    id [ len ] = 0;
 
5096
    return id;
 
5097
}
 
5098
 
 
5099
 
 
5100
/* This function pulls defline information from the ID string, if there is
 
5101
 * any.
 
5102
 */
 
5103
static char * s_GetDeflineFromIdString (char * str)
 
5104
{
 
5105
    char * cp;
 
5106
    int    len;
 
5107
 
 
5108
    if (str == NULL) {
 
5109
        return NULL;
 
5110
    }
 
5111
 
 
5112
    cp = str;
 
5113
    cp += strspn (str, " >\t");
 
5114
    len = strcspn (cp, " \t\r\n");
 
5115
    if (len == 0) {
 
5116
        return NULL; 
 
5117
    }
 
5118
    cp += len;
 
5119
    len = strspn (cp, " \t\r\n");
 
5120
    if (len == 0) {
 
5121
        return NULL; 
 
5122
    }
 
5123
    cp += len;
 
5124
    if (*cp == 0) {
 
5125
        return NULL;
 
5126
    }
 
5127
    return strdup (cp);
 
5128
}
 
5129
 
 
5130
 
 
5131
/* This function takes the ID strings read from the file and parses them
 
5132
 * to obtain a defline (if there is extra text after the ID and/or
 
5133
 * organism information) and to obtain the actual ID for the sequence.
 
5134
 */
 
5135
static EBool s_ReprocessIds (SAlignRawFilePtr afrp)
 
5136
{
 
5137
    TStringCountPtr list, scp;
 
5138
    TAlignRawSeqPtr arsp;
 
5139
    TLineInfoPtr    lip;
 
5140
    char *          id;
 
5141
    int             line_num;
 
5142
    EBool           rval = eTrue;
 
5143
    char *          defline;
 
5144
 
 
5145
    if (afrp == NULL) {
 
5146
        return eFalse;
 
5147
    }
 
5148
 
 
5149
    list = NULL;
 
5150
    lip = afrp->deflines;
 
5151
    for (arsp = afrp->sequences; arsp != NULL; arsp = arsp->next) {
 
5152
        if (arsp->id_lines != NULL) {
 
5153
            line_num = arsp->id_lines->ival;
 
5154
        } else {
 
5155
            line_num = -1;
 
5156
        }
 
5157
        s_RemoveOrganismCommentFromLine (arsp->id);
 
5158
        id = s_GetIdFromString (arsp->id);
 
5159
        if (lip == NULL) {
 
5160
            defline = s_GetDeflineFromIdString (arsp->id);
 
5161
            afrp->deflines = s_AddLineInfo (afrp->deflines, defline,
 
5162
                                            line_num, 0);
 
5163
            free (defline);
 
5164
            afrp->num_deflines ++;
 
5165
        }
 
5166
        free (arsp->id);
 
5167
        arsp->id = id;
 
5168
        list = s_AddStringCount (arsp->id, line_num, list);
 
5169
    }
 
5170
 
 
5171
    for (scp = list;  scp != NULL;  scp = scp->next) {
 
5172
        if (scp->num_appearances > 1) {
 
5173
            rval = eFalse;
 
5174
            s_ReportRepeatedId (scp, afrp->report_error,
 
5175
                              afrp->report_error_userdata);
 
5176
        }
 
5177
    }
 
5178
    return rval;
 
5179
}
 
5180
 
 
5181
 
 
5182
/* This function reports unacceptable characters in a sequence.  Frequently
 
5183
 * there will be more than one character of the same kind (for instance,
 
5184
 * when the user has incorrectly specified a gap character), so repeated
 
5185
 * characters are reported together.  The function advances the data 
 
5186
 * position in the SLineInfoReader structure lirp, and returns the
 
5187
 * current data position for lirp.
 
5188
 */
 
5189
static int 
 
5190
s_ReportRepeatedBadCharsInSequence
 
5191
(TLineInfoReaderPtr   lirp,
 
5192
 char *               id,
 
5193
 char *               reason,
 
5194
 FReportErrorFunction report_error,
 
5195
 void *              report_error_userdata)
 
5196
{
 
5197
    int  bad_line_num, bad_line_offset;
 
5198
    int  num_bad_chars;
 
5199
    char bad_char, curr_char;
 
5200
    int  data_position;
 
5201
 
 
5202
    bad_line_num = s_LineInfoReaderGetCurrentLineNumber (lirp);
 
5203
    bad_line_offset = s_LineInfoReaderGetCurrentLineOffset (lirp);
 
5204
    bad_char = *lirp->curr_line_pos;
 
5205
    num_bad_chars = 1;
 
5206
    data_position = lirp->data_pos + 1;
 
5207
    while ((curr_char = s_FindNthDataChar (lirp, data_position)) == bad_char) {
 
5208
        num_bad_chars ++;
 
5209
        data_position ++;
 
5210
    }
 
5211
    s_ReportBadCharError (id, bad_char, num_bad_chars,
 
5212
                        bad_line_offset, bad_line_num, reason,
 
5213
                        report_error, report_error_userdata);
 
5214
    return data_position;
 
5215
}
 
5216
 
 
5217
 
 
5218
/* This function does context-sensitive replacement of the missing,
 
5219
 * match, and gap characters and also identifies bad characters.
 
5220
 * Gap characters found in the wrong location in the sequence are
 
5221
 * considered an error.  Characters that are not missing, match, or 
 
5222
 * gap characters and are not in the specified sequence alphabet are
 
5223
 * reported as errors.  Match characters in the first sequence are also
 
5224
 * reported as errors.
 
5225
 * The function will return eTrue if any errors were found, or eFalse
 
5226
 * if there were no errors.
 
5227
 */
 
5228
static EBool
 
5229
s_FindBadDataCharsInSequence
 
5230
(TAlignRawSeqPtr      arsp,
 
5231
 TAlignRawSeqPtr      master_arsp,
 
5232
 TSequenceInfoPtr     sip,
 
5233
 int                  num_segments,
 
5234
 FReportErrorFunction report_error,
 
5235
 void *               report_error_userdata)
 
5236
{
 
5237
    TLineInfoReaderPtr lirp, master_lirp;
 
5238
    int                data_position;
 
5239
    int                middle_start;
 
5240
    int                middle_end;
 
5241
    char               curr_char, master_char;
 
5242
    EBool              found_middle_start;
 
5243
    EBool              rval = eFalse;
 
5244
    EBool              match_not_in_beginning_gap;
 
5245
    EBool              match_not_in_end_gap;
 
5246
 
 
5247
    if (arsp == NULL  ||  master_arsp == NULL  ||  sip == NULL) {
 
5248
        return eTrue;
 
5249
    }
 
5250
    lirp = s_LineInfoReaderNew (arsp->sequence_data);
 
5251
    if (lirp == NULL) {
 
5252
        return eTrue;
 
5253
    }
 
5254
    if (arsp != master_arsp) {
 
5255
        master_lirp = s_LineInfoReaderNew (master_arsp->sequence_data);
 
5256
        if (master_lirp == NULL) {
 
5257
            s_LineInfoReaderFree (lirp);
 
5258
            return eTrue;
 
5259
        }
 
5260
    } else {
 
5261
        master_lirp = NULL;
 
5262
    }
 
5263
 
 
5264
    if (strcspn (sip->beginning_gap, sip->match) 
 
5265
                  == strlen (sip->beginning_gap)) {
 
5266
        match_not_in_beginning_gap = eTrue;
 
5267
    } else {
 
5268
        match_not_in_beginning_gap = eFalse;
 
5269
    }
 
5270
 
 
5271
    if (strcspn (sip->end_gap, sip->match) == strlen (sip->end_gap)) {
 
5272
        match_not_in_end_gap = eTrue;
 
5273
    } else {
 
5274
        match_not_in_end_gap = eFalse;
 
5275
    }
 
5276
 
 
5277
    /* First, find middle start and end positions and report characters
 
5278
     * that are not beginning gap before the middle
 
5279
     */
 
5280
    found_middle_start = eFalse;
 
5281
    data_position = 0;
 
5282
    curr_char = s_FindNthDataChar (lirp, data_position);
 
5283
    while (curr_char != 0) {
 
5284
        if (strchr (sip->alphabet, curr_char) != NULL) {
 
5285
            if (! found_middle_start) {
 
5286
                middle_start = data_position;
 
5287
                found_middle_start = eTrue;
 
5288
            }
 
5289
            middle_end = data_position + 1;
 
5290
            data_position ++;
 
5291
        } else if (! found_middle_start) {
 
5292
            if (match_not_in_beginning_gap
 
5293
                &&  strchr (sip->match, curr_char) != NULL)
 
5294
            {
 
5295
                middle_start = data_position;
 
5296
                found_middle_start = eTrue;
 
5297
                middle_end = data_position + 1;
 
5298
                data_position ++;
 
5299
            } else if (strchr (sip->beginning_gap, curr_char) == NULL) {
 
5300
                /* Report error - found character that is not beginning gap
 
5301
                   in beginning gap */
 
5302
                data_position = s_ReportRepeatedBadCharsInSequence (lirp,
 
5303
                                                                  arsp->id,
 
5304
                                "expect only beginning gap characters here",
 
5305
                                report_error, report_error_userdata);
 
5306
                rval = eTrue;
 
5307
            } else {
 
5308
                *lirp->curr_line_pos = '-';
 
5309
                data_position ++;
 
5310
            }
 
5311
        } else {
 
5312
            if (match_not_in_end_gap
 
5313
                &&  strchr (sip->match, curr_char) != NULL)
 
5314
            {
 
5315
                middle_end = data_position + 1;
 
5316
            }
 
5317
            data_position ++;
 
5318
        }
 
5319
        curr_char = s_FindNthDataChar (lirp, data_position);
 
5320
    }
 
5321
 
 
5322
    if (! found_middle_start) {
 
5323
        if (num_segments > 1)
 
5324
        {
 
5325
            return eFalse;
 
5326
        }
 
5327
        else
 
5328
        {
 
5329
            s_ReportMissingSequenceData (arsp->id,
 
5330
                                   report_error, report_error_userdata);
 
5331
            s_LineInfoReaderFree (lirp);
 
5332
            return eTrue;
 
5333
          
 
5334
        }
 
5335
    }
 
5336
 
 
5337
    /* Now complain about bad middle characters */
 
5338
    data_position = middle_start;
 
5339
    while (data_position < middle_end)
 
5340
    {
 
5341
        curr_char = s_FindNthDataChar (lirp, data_position);
 
5342
        while (data_position < middle_end
 
5343
               &&  strchr (sip->alphabet, curr_char) != NULL) {
 
5344
            data_position ++;
 
5345
            curr_char = s_FindNthDataChar (lirp, data_position);
 
5346
        } 
 
5347
        if (curr_char == 0  ||  data_position >= middle_end) {
 
5348
            /* do nothing, done with middle */
 
5349
        } else if (strchr (sip->missing, curr_char) != NULL) {
 
5350
            *lirp->curr_line_pos = 'N';
 
5351
            data_position ++;
 
5352
        } else if (strchr (sip->match, curr_char) != NULL) {
 
5353
            master_char = s_FindNthDataChar (master_lirp, data_position);
 
5354
            if (master_char == 0) {
 
5355
                /* report error - unable to get master char */
 
5356
                if (master_arsp == arsp) {
 
5357
                    data_position = s_ReportRepeatedBadCharsInSequence (lirp,
 
5358
                                arsp->id,
 
5359
                                "can't specify match chars in first sequence",
 
5360
                                report_error, report_error_userdata);
 
5361
                } else {
 
5362
                    data_position = s_ReportRepeatedBadCharsInSequence (lirp,
 
5363
                                arsp->id,
 
5364
                                "can't find source for match chars",
 
5365
                                report_error, report_error_userdata);
 
5366
                }
 
5367
                rval = eTrue;
 
5368
            } else {
 
5369
                *lirp->curr_line_pos = master_char;
 
5370
                data_position ++;
 
5371
            }
 
5372
        } else if (strchr (sip->middle_gap, curr_char) != NULL) {
 
5373
            *lirp->curr_line_pos = '-';
 
5374
            data_position ++;
 
5375
        } else {
 
5376
            /* Report error - found bad character in middle */
 
5377
            data_position = s_ReportRepeatedBadCharsInSequence (lirp,
 
5378
                                      arsp->id,
 
5379
                                      "expect only sequence, missing, match,"
 
5380
                                      " and middle gap characters here",
 
5381
                                      report_error, report_error_userdata);
 
5382
            rval = eTrue;
 
5383
        }
 
5384
    }
 
5385
 
 
5386
    /* Now find and complain about end characters */
 
5387
    data_position = middle_end;
 
5388
    curr_char = s_FindNthDataChar (lirp, data_position);
 
5389
    while (curr_char != 0) {
 
5390
        if (strchr (sip->end_gap, curr_char) == NULL) {
 
5391
            /* Report error - found bad character in middle */
 
5392
            data_position = s_ReportRepeatedBadCharsInSequence (lirp, arsp->id,
 
5393
                                      "expect only end gap characters here",
 
5394
                                      report_error, report_error_userdata);
 
5395
            rval = eTrue;
 
5396
        } else {
 
5397
            *lirp->curr_line_pos = '-';
 
5398
            data_position++;
 
5399
        }
 
5400
        curr_char = s_FindNthDataChar (lirp, data_position);
 
5401
    }
 
5402
    s_LineInfoReaderFree (lirp);
 
5403
    s_LineInfoReaderFree (master_lirp);
 
5404
    return rval;
 
5405
}
 
5406
 
 
5407
 
 
5408
/* This function examines each sequence and replaces the special characters
 
5409
 * and reports bad characters in each one.  The function will return eTrue
 
5410
 * if any of the sequences contained bad characters or eFalse if no errors
 
5411
 * were seen.
 
5412
 */
 
5413
static EBool
 
5414
s_s_FindBadDataCharsInSequenceList
 
5415
(SAlignRawFilePtr afrp,
 
5416
 TSequenceInfoPtr sip)
 
5417
{
 
5418
    TAlignRawSeqPtr arsp;
 
5419
    EBool           rval = eFalse;
 
5420
 
 
5421
    if (afrp == NULL  ||  afrp->sequences == NULL) {
 
5422
        return eTrue;
 
5423
    }
 
5424
    for (arsp = afrp->sequences; arsp != NULL; arsp = arsp->next) {
 
5425
        if (s_FindBadDataCharsInSequence (arsp, afrp->sequences, sip,
 
5426
                                        afrp->num_segments,
 
5427
                                        afrp->report_error,
 
5428
                                        afrp->report_error_userdata)) {
 
5429
            rval = eTrue;
 
5430
        }
 
5431
    }
 
5432
    return rval;
 
5433
}
 
5434
 
 
5435
 
 
5436
/* This function examines the organisms listed for the alignment and determines
 
5437
 * whether any of the organism names (including the associated comments) are
 
5438
 * repeated.
 
5439
 */
 
5440
static EBool s_AreOrganismsUnique (SAlignRawFilePtr afrp)
 
5441
{
 
5442
    TLineInfoPtr    this_org, lip;
 
5443
    TAlignRawSeqPtr arsp;
 
5444
    EBool           are_unique;
 
5445
 
 
5446
    if (afrp == NULL  ||  afrp->num_organisms == 0
 
5447
        ||  afrp->organisms == NULL) {
 
5448
        return eFalse;
 
5449
    }
 
5450
    are_unique = eTrue;
 
5451
    for (this_org = afrp->organisms;
 
5452
         this_org != NULL;
 
5453
         this_org = this_org->next) {
 
5454
        lip = afrp->organisms;
 
5455
        arsp = afrp->sequences;
 
5456
        while (lip != NULL  &&  lip != this_org
 
5457
               &&  strcmp (lip->data, this_org->data) != 0  &&  arsp != NULL) {
 
5458
            lip = lip->next;
 
5459
            arsp = arsp->next;
 
5460
        }
 
5461
        if (lip != NULL  &&  lip != this_org) {
 
5462
            are_unique = eFalse;
 
5463
            s_ReportRepeatedOrganismName (arsp->id, this_org->line_num,
 
5464
                                        lip->line_num,
 
5465
                                        this_org->data,
 
5466
                                        afrp->report_error,
 
5467
                                        afrp->report_error_userdata);
 
5468
        }
 
5469
    }
 
5470
    return are_unique;
 
5471
}
 
5472
 
 
5473
 
 
5474
#if 0 /* this step was removed by indexer request */
 
5475
/* This function reports whether the definition lines are identical for
 
5476
 * each sequence or not.
 
5477
 */
 
5478
static EBool s_AreDeflinesIdentical (SAlignRawFilePtr afrp)
 
5479
{
 
5480
    TLineInfoPtr    lip;
 
5481
    TStringCountPtr list;
 
5482
    EBool           rval;
 
5483
 
 
5484
    if (afrp == NULL) {
 
5485
        return eFalse;
 
5486
    }
 
5487
 
 
5488
    list = NULL;
 
5489
    for (lip = afrp->deflines;  lip != NULL;  lip = lip->next) {
 
5490
        list = s_AddStringCount (lip->data, lip->line_num, list);
 
5491
    }
 
5492
    rval = eTrue;
 
5493
    if (list != NULL  &&  list->next != NULL) {
 
5494
        rval = eFalse; 
 
5495
        s_ReportDefinitionLineMismatch (afrp->report_error,
 
5496
                                      afrp->report_error_userdata);
 
5497
        s_ReportDefinitionLines (list, afrp->report_error,
 
5498
                               afrp->report_error_userdata);
 
5499
    }
 
5500
    s_StringCountFree (list);
 
5501
    return rval;
 
5502
}
 
5503
#endif
 
5504
 
 
5505
 
 
5506
/* This function uses the contents of an SAlignRawFileData structure to
 
5507
 * create an SAlignmentFile structure with the appropriate information.
 
5508
 */
 
5509
static TAlignmentFilePtr
 
5510
s_ConvertDataToOutput 
 
5511
(SAlignRawFilePtr afrp,
 
5512
 TSequenceInfoPtr sip)
 
5513
{
 
5514
    TAlignRawSeqPtr   arsp;
 
5515
    int               index;
 
5516
    TSizeInfoPtr    * lengths;
 
5517
    int             * best_length;
 
5518
    TAlignmentFilePtr afp;
 
5519
    TLineInfoPtr      lip;
 
5520
    int               curr_seg;
 
5521
 
 
5522
    if (afrp == NULL  ||  sip == NULL  ||  afrp->sequences == NULL) {
 
5523
        return NULL;
 
5524
    }
 
5525
    afp = AlignmentFileNew ();
 
5526
    if (afp == NULL) {
 
5527
        return NULL;
 
5528
    }
 
5529
 
 
5530
    afp->num_organisms = afrp->num_organisms;
 
5531
    afp->num_deflines = afrp->num_deflines;
 
5532
    afp->num_segments = afrp->num_segments;
 
5533
    afp->num_sequences = 0;
 
5534
    lengths = NULL;
 
5535
 
 
5536
    for (arsp = afrp->sequences;  arsp != NULL;  arsp = arsp->next) {
 
5537
        afp->num_sequences++;
 
5538
    }
 
5539
 
 
5540
    if (afp->num_sequences != afrp->num_organisms
 
5541
        && afp->num_sequences / afp->num_segments != afrp->num_organisms) {
 
5542
        s_ReportMissingOrganismInfo (afrp->report_error,
 
5543
                                   afrp->report_error_userdata);
 
5544
    } else {
 
5545
        s_AreOrganismsUnique (afrp);
 
5546
    }
 
5547
 
 
5548
    afp->sequences = (char **)malloc (afp->num_sequences 
 
5549
                                           * sizeof (char *));
 
5550
    if (afp->sequences == NULL) {
 
5551
        AlignmentFileFree (afp);
 
5552
        return NULL;
 
5553
    }
 
5554
    afp->ids = (char **)malloc (afp->num_sequences * sizeof (char *));
 
5555
    if (afp->ids == NULL) {
 
5556
        AlignmentFileFree (afp);
 
5557
        return NULL;
 
5558
    }
 
5559
    if (afp->num_organisms > 0) {
 
5560
        afp->organisms = (char **) malloc (afp->num_organisms
 
5561
                                                * sizeof (char *));
 
5562
        if (afp->organisms == NULL) {
 
5563
            AlignmentFileFree (afp);
 
5564
            return NULL;
 
5565
        }
 
5566
    }
 
5567
    if (afp->num_deflines > 0) {
 
5568
        afp->deflines = (char **)malloc (afp->num_deflines
 
5569
                                              * sizeof (char *));
 
5570
        if (afp->deflines == NULL) {
 
5571
            AlignmentFileFree (afp);
 
5572
            return NULL;
 
5573
        }
 
5574
    }
 
5575
 
 
5576
    /* copy in deflines */
 
5577
    for (lip = afrp->deflines, index = 0;
 
5578
         lip != NULL  &&  index < afp->num_deflines;
 
5579
         lip = lip->next, index++) {
 
5580
        if (lip->data == NULL) {
 
5581
            afp->deflines [index] = NULL;
 
5582
        } else {
 
5583
            afp->deflines [index] = strdup (lip->data);
 
5584
        }
 
5585
    }
 
5586
    while (index < afp->num_deflines) {
 
5587
        afp->deflines [index ++] = NULL;
 
5588
    }
 
5589
 
 
5590
    /* copy in organism information */
 
5591
    for (lip = afrp->organisms, index = 0;
 
5592
         lip != NULL  &&  index < afp->num_organisms;
 
5593
         lip = lip->next, index++) {
 
5594
        afp->organisms [index] = strdup (lip->data);
 
5595
    }
 
5596
  
 
5597
    /* we need to store length information about different segments separately */
 
5598
    lengths = (TSizeInfoPtr *) malloc (sizeof (TSizeInfoPtr) * afrp->num_segments);
 
5599
    if (lengths == NULL) {
 
5600
        AlignmentFileFree (afp);
 
5601
        return NULL;
 
5602
    }
 
5603
    best_length = (int *) malloc (sizeof (int) * afrp->num_segments);
 
5604
    if (best_length == NULL) {
 
5605
        free (lengths);
 
5606
        AlignmentFileFree (afp);
 
5607
        return NULL;
 
5608
    }
 
5609
    for (curr_seg = 0; curr_seg < afrp->num_segments; curr_seg ++) {
 
5610
        lengths [curr_seg] = NULL;
 
5611
        best_length [curr_seg] = 0;
 
5612
    }
 
5613
    
 
5614
    /* copy in sequence data */
 
5615
    curr_seg = 0;
 
5616
    for (arsp = afrp->sequences, index = 0;
 
5617
         arsp != NULL  &&  index < afp->num_sequences;
 
5618
         arsp = arsp->next, index++) {
 
5619
        afp->sequences [index] = 
 
5620
                    s_LineInfoMergeAndStripSpaces (arsp->sequence_data);
 
5621
 
 
5622
        if (afp->sequences [index] != NULL) {
 
5623
            lengths [curr_seg] = s_AddSizeInfo (lengths [curr_seg], strlen (afp->sequences [index]));
 
5624
        }
 
5625
        afp->ids [index] = strdup (arsp->id);
 
5626
        curr_seg ++;
 
5627
        if (curr_seg >= afrp->num_segments) {
 
5628
                curr_seg = 0;
 
5629
        }
 
5630
    }
 
5631
    for (curr_seg = 0; curr_seg < afrp->num_segments; curr_seg ++)
 
5632
    {
 
5633
        best_length [curr_seg] = s_GetMostPopularSize (lengths [curr_seg]);
 
5634
        if (best_length [curr_seg] == 0  &&  lengths [curr_seg] != NULL) {
 
5635
            best_length [curr_seg] = lengths [curr_seg]->size_value;
 
5636
        }   
 
5637
    }
 
5638
 
 
5639
    curr_seg = 0;
 
5640
    for (index = 0;  index < afp->num_sequences;  index++) {
 
5641
        if (afp->sequences [index] == NULL) {
 
5642
            s_ReportMissingSequenceData (afp->ids [index],
 
5643
                                       afrp->report_error,
 
5644
                                       afrp->report_error_userdata);
 
5645
        } else if ((int) strlen (afp->sequences [index]) != best_length [curr_seg]) {
 
5646
            s_ReportBadSequenceLength (afp->ids [index], best_length [curr_seg],
 
5647
                                     strlen (afp->sequences [index]),
 
5648
                                     afrp->report_error,
 
5649
                                     afrp->report_error_userdata);
 
5650
        }
 
5651
        curr_seg ++;
 
5652
        if (curr_seg >= afrp->num_segments) {
 
5653
                curr_seg = 0;
 
5654
        }
 
5655
    }
 
5656
 
 
5657
    if (afrp->expected_num_sequence > 0
 
5658
      &&  afrp->expected_num_sequence != afp->num_sequences)
 
5659
    {
 
5660
        s_ReportIncorrectNumberOfSequences (afrp->expected_num_sequence,
 
5661
                                          afp->num_sequences,
 
5662
                                          afrp->report_error,
 
5663
                                          afrp->report_error_userdata);
 
5664
    }
 
5665
    if (afrp->expected_sequence_len > 0
 
5666
      &&  afrp->expected_sequence_len != best_length [0])
 
5667
    {
 
5668
        s_ReportIncorrectSequenceLength (afrp->expected_sequence_len,
 
5669
                                       best_length [0],
 
5670
                                       afrp->report_error,
 
5671
                                       afrp->report_error_userdata);
 
5672
    }
 
5673
    
 
5674
    free (best_length);
 
5675
    for (curr_seg = 0; curr_seg < afrp->num_segments; curr_seg ++)
 
5676
    {
 
5677
        s_SizeInfoFree (lengths [curr_seg]);
 
5678
    }
 
5679
    free (lengths);
 
5680
    
 
5681
    return afp;
 
5682
}
 
5683
 
 
5684
 
 
5685
/* This is the function called by the calling program to read an alignment
 
5686
 * file.  The readfunc argument is a function pointer supplied by the 
 
5687
 * calling program which this library will use to read in data from the
 
5688
 * file one line at a time.  The fileuserdata argument is a pointer to 
 
5689
 * data used by the calling program's readfunc function and will be passed
 
5690
 * back with each call to readfunc.
 
5691
 * The errfunc argument is a function pointer supplied by the calling
 
5692
 * program for reporting errors.  The erroruserdata argument is a pointer
 
5693
 * to data used by the calling program's errfunc function and will be
 
5694
 * passed back with each call to readfunc.
 
5695
 * The sequence_info argument contains the sequence alphabet and missing,
 
5696
 * match, and gap characters to use in interpreting the sequence data.
 
5697
 */
 
5698
extern TAlignmentFilePtr 
 
5699
ReadAlignmentFile 
 
5700
(FReadLineFunction readfunc,
 
5701
 void * fileuserdata,
 
5702
 FReportErrorFunction errfunc,
 
5703
 void * erroruserdata,
 
5704
 TSequenceInfoPtr sequence_info)
 
5705
{
 
5706
    SAlignRawFilePtr afrp;
 
5707
    TAlignmentFilePtr afp;
 
5708
 
 
5709
    if (sequence_info == NULL  ||  sequence_info->alphabet == NULL) {
 
5710
        return NULL;
 
5711
    }
 
5712
    afrp = s_ReadAlignFileRaw ( readfunc, fileuserdata, sequence_info,
 
5713
                              errfunc, erroruserdata);
 
5714
    if (afrp == NULL) {
 
5715
        return NULL;
 
5716
    }
 
5717
 
 
5718
    if (afrp->block_size > 1) {
 
5719
        s_ProcessAlignRawFileByBlockOffsets (afrp);
 
5720
    } else if (afrp->marked_ids) {
 
5721
        s_ProcessAlignFileRawForMarkedIDs (afrp);
 
5722
    } else {
 
5723
        s_ProcessAlignFileRawByLengthPattern (afrp);
 
5724
    }
 
5725
 
 
5726
    s_ReprocessIds (afrp);
 
5727
 
 
5728
#if 0 /* this step was removed by indexer request */
 
5729
    /* Note - have to check deflines after reprocessing IDs */
 
5730
    s_AreDeflinesIdentical (afrp);
 
5731
#endif
 
5732
 
 
5733
    if (s_s_FindBadDataCharsInSequenceList (afrp, sequence_info)) {
 
5734
        s_AlignFileRawFree (afrp);
 
5735
        return NULL;
 
5736
    }
 
5737
 
 
5738
    afp = s_ConvertDataToOutput (afrp, sequence_info);
 
5739
    s_AlignFileRawFree (afrp);
 
5740
  
 
5741
    return afp;
 
5742
}
 
5743
 
 
5744
/*
 
5745
 * ===========================================================================
 
5746
 * $Log: alnread.c,v $
 
5747
 * Revision 1.12  2004/09/17 12:21:48  bollin
 
5748
 * allow all-gap segments in segmented alignments
 
5749
 *
 
5750
 * Revision 1.11  2004/08/11 15:23:07  vakatov
 
5751
 * Compilation warning fix (unused static func)
 
5752
 *
 
5753
 * Revision 1.10  2004/05/20 19:40:24  bollin
 
5754
 * Made chnages to allow reading of alignments of segmented sets.
 
5755
 * Also added warnings for when organism lines may be present but improperly
 
5756
 * formatted.
 
5757
 *
 
5758
 * Revision 1.9  2004/03/16 21:05:15  bollin
 
5759
 * Added some improvements to the portion of the alignment reader that deals
 
5760
 * with contiguous alignments that do not have a '>' at the beginning of each
 
5761
 * ID.
 
5762
 *
 
5763
 * Revision 1.8  2004/03/16 16:25:38  bollin
 
5764
 * Added function to recognize a file as ASN.1 and reject immediately
 
5765
 *
 
5766
 * Revision 1.7  2004/03/09 21:27:39  bollin
 
5767
 * in s_InsertNewOffsets, if the list ends while searching for the next pattern, exit immediately (prevents NULL pointer access)
 
5768
 *
 
5769
 * Revision 1.6  2004/03/04 19:15:07  bollin
 
5770
 * file reading now skips over multi-line bracketed comments
 
5771
 *
 
5772
 * Revision 1.5  2004/03/04 16:29:32  bollin
 
5773
 * added skip of taxa comment for PAUP format alignment files
 
5774
 *
 
5775
 * Revision 1.4  2004/02/10 16:15:13  bollin
 
5776
 * now checks for unused lines when finding interleaved blocks, will reject and try other methods if unused lines found after first block found.
 
5777
 *
 
5778
 * Revision 1.3  2004/02/05 16:29:32  bollin
 
5779
 * smarter function for skipping NEXUS comment lines
 
5780
 *
 
5781
 * Revision 1.2  2004/02/04 19:49:11  bollin
 
5782
 * fixed infinite loop condition in s_AugmentOffsetList, properly skip over first non-space column when looking for interleaved block patterns in s_ReadAlignFileRaw
 
5783
 *
 
5784
 * Revision 1.1  2004/02/03 16:47:02  ucko
 
5785
 * Add Colleen Bollin's Toolkit-independent alignment reader.
 
5786
 *
 
5787
 * Revision 1.38  2004/01/30 22:46:08  bollin
 
5788
 * renamed defined variable, fixed typo in comment
 
5789
 *
 
5790
 * Revision 1.37  2004/01/30 21:48:14  bollin
 
5791
 * changes for compatibility with Windows
 
5792
 *
 
5793
 * Revision 1.36  2004/01/30 21:33:41  bollin
 
5794
 * replaced strncasecmp and strncase function calls
 
5795
 *
 
5796
 * Revision 1.35  2004/01/29 19:16:27  bollin
 
5797
 * use EBool for boolean values
 
5798
 *
 
5799
 * Revision 1.34  2004/01/29 17:58:11  bollin
 
5800
 * aligned assignment blocks in New functions
 
5801
 *
 
5802
 * Revision 1.33  2004/01/29 17:43:40  bollin
 
5803
 * added directory specification to alnread.h include line
 
5804
 *
 
5805
 * Revision 1.32  2004/01/29 17:41:29  bollin
 
5806
 * added comment block, id tags, log
 
5807
 * 
 
5808
 * ===========================================================================
 
5809
 */