alnread.c

ncbi源码

 * The new structure will be placed at the end of list if list is not NULL.
 * The function will return a pointer to the new structure.
 */
static TIntLinkPtr 
s_IntLinkNew 
(int         ival, 
 TIntLinkPtr list)
{
    TIntLinkPtr ilp, last;

    ilp = (TIntLinkPtr) malloc (sizeof (SIntLink));
    if (ilp == NULL) {
        return NULL;
    }
    ilp->ival = ival;
    ilp->next = NULL;
    last = list;
    while (last != NULL && last->next != NULL) {
        last = last->next;
    }
    if (last != NULL) {
        last->next = ilp;
    }
    return ilp;
}


/* This function recursively frees memory associated with a linked list
 * of SIntLink structures.
 */
static void s_IntLinkFree (TIntLinkPtr ilp)
{
    if (ilp == NULL) {
        return;
    }
    s_IntLinkFree (ilp->next);
    free (ilp);
}


/* These functions are used to accumulate and retrieve information on 
 * how often a size of data (number of lines or number of characters) occurs.
 */

/* This function allocates space for a new SSizeInfo structure and 
 * initializes its member variables.  If list is not NULL, the new structure
 * is added to the end of the list.
 * The function returns a pointer to the newly allocated structure.
 */
static TSizeInfoPtr s_SizeInfoNew (TSizeInfoPtr list)
{
    TSizeInfoPtr sip, last;

    sip = (TSizeInfoPtr) malloc (sizeof (SSizeInfo));
    if (sip == NULL) {
        return NULL;
    }

    sip->size_value      = 0;
    sip->num_appearances = 0;
    sip->next            = NULL;
    last = list;
    while (last != NULL && last->next != NULL) {
        last = last->next;
    }
    if (last != NULL) {
        last->next = sip;
    }
    return sip;
}


/* This function recursively frees the memory associated with a linked list
 * of SSizeInfo structures.
 */
static void s_SizeInfoFree (TSizeInfoPtr list)
{
    if (list == NULL) {
        return;
    }
    s_SizeInfoFree (list->next);
    list->next = NULL;
    free (list);
}


/* This function returns eTrue if the two SSizeInfo structures have
 * the same size_value and number of appearances, eFalse otherwise.
 */
static EBool 
s_SizeInfoIsEqual 
(TSizeInfoPtr s1,
 TSizeInfoPtr s2)
{
    if (s1 == NULL
      ||  s2 == NULL
      ||  s1->size_value != s2->size_value
      ||  s1->num_appearances != s2->num_appearances) {
        return eFalse;
    }
    return eTrue;
}


/* This function searches list for a SSizeInfo structure with the
 * same size_value as size_value.  If it finds such a structure, it
 * adds the value of num_appearances to the num_appearances for that
 * structure, otherwise the function creates a new structure at the end
 * of the list with the specified values of size_value and num_appearances.
 * The function returns a pointer to the list of SSizeInfo structures.
 */
static TSizeInfoPtr s_AddSizeInfoAppearances 
(TSizeInfoPtr list,
 int  size_value,
 int  num_appearances)
{
    TSizeInfoPtr p, last;

    last = NULL;
    for (p = list;  p != NULL  &&  p->size_value != size_value;  p = p->next) {
        last = p;
    }
    if (p == NULL) {
        p = (TSizeInfoPtr) malloc (sizeof (SSizeInfo));
        if (p == NULL) {
            return NULL;
        }
        p->size_value = size_value;
        p->num_appearances = num_appearances;
        p->next = 0;
        if (last == NULL) {
            list = p;
        } else {
            last->next = p;
        }
    } else {
        p->num_appearances += num_appearances;
    }
    return list;
}


/* This function searches list for a SSizeInfo structure with the
 * same size_value as size_value.  If it finds such a structure, it
 * adds one to the num_appearances for that structure, otherwise the 
 * function creates a new structure at the end of the list with the 
 * specified values of size_value and num_appearances.
 * The function returns a pointer to the list of SSizeInfo structures.
 */
static TSizeInfoPtr 
s_AddSizeInfo
(TSizeInfoPtr list,
 int  size_value)
{
    return s_AddSizeInfoAppearances (list, size_value, 1);
}


/* This function searches list for the SSizeInfo structure with the
 * highest value for num_appearances.  If more than one structure exists
 * with the highest value for num_appearances, the function chooses the
 * value with the highest value for size_value.  The function returns a
 * pointer to the structure selected based on the above criteria.
 */
static TSizeInfoPtr s_GetMostPopularSizeInfo (TSizeInfoPtr list)
{
    TSizeInfoPtr p, best;

    if (list == NULL) {
        return NULL;
    }

    best = list;
    for (p = list->next;  p != NULL;  p = p->next) {
      if (p->num_appearances > best->num_appearances
          ||  (p->num_appearances == best->num_appearances
            &&  p->size_value > best->size_value)) {
          best = p;
      }
    }
    return best;
}


/* This function uses s_GetMostPopularSizeInfo function to find the structure
 * in list that has the highest value for num_appearances and size_value.
 * If such a structure is found and has a num_appearances value greater than
 * one, the size_value for that structure will be returned, otherwise the
 * function returns 0.
 */
static int  s_GetMostPopularSize (TSizeInfoPtr list)
{
    TSizeInfoPtr best;

    best = s_GetMostPopularSizeInfo (list);
    if (best == NULL) {
        return 0;
    }
    if (best->num_appearances > 1) {
        return best->size_value; 
    } else {
        return 0;
    }
}


/* The following functions are used to keep track of patterns of line or
 * token lengths, which will be used to identify errors in formatting.
 */
static SLengthListPtr s_LengthListNew (SLengthListPtr list)
{
    SLengthListPtr llp, last;

    llp = (SLengthListPtr) malloc (sizeof (SLengthListData));
    if (llp == NULL) {
        return NULL;
    }

    llp->lengthrepeats   = NULL;
    llp->num_appearances = 0;
    llp->next            = NULL;

    last = list;
    while (last != NULL && last->next != NULL) {
        last = last->next;
    }
    if (last != NULL) {
        last->next = llp;
    }
    return llp;
}


/* This function recursively frees memory for a list of SLengthListData
 * structures and its member variables.
 */
static void s_LengthListFree (SLengthListPtr llp)
{
    if (llp == NULL) {
        return;
    }
    s_LengthListFree (llp->next);
    s_SizeInfoFree (llp->lengthrepeats);
    free (llp);
}


/* This function examines the last SSizeInfo structure in the 
 * lengthrepeats member variable of llp.  If the last structure 
 * in the list has the same size_value value as the function argument 
 * size_value, the value of num_appearances for that SizeInforData structure
 * will be incremented.  Otherwise a new SSizeInfo structure will be
 * appended to the end of the lengthrepeats list with the specified
 * size_value and a num_appearances value of 1.
 */
static void 
s_AddLengthRepeat
(SLengthListPtr llp,
 int  size_value)
{
    TSizeInfoPtr p, last;

    if (llp == NULL) {
        return;
    }

    last = NULL;
    for (p = llp->lengthrepeats;  p != NULL;  p = p->next) {
        last = p;
    }
    if (last == NULL  ||  last->size_value != size_value) {
        p = (TSizeInfoPtr) malloc (sizeof (SSizeInfo));
        if (p == NULL) {
            return;
        }
        p->size_value = size_value;
        p->num_appearances = 1;
        p->next = 0;
        if (last == NULL) {
            llp->lengthrepeats = p;
        } else {
            last->next = p;
        }
    } else {
        last->num_appearances ++;
    }
}


/* This function examines whether two SLengthListData structures "match" - 
 * the structures match if each SSizeInfo structure in llp1->lengthrepeats
 * has the same size_value and num_appearances values as the SSizeInfo
 * structure in the corresponding list position in llp2->lenghrepeats.
 * If the two structures match, the function returns eTrue, otherwise the
 * function returns eFalse.
 */
static EBool 
s_DoLengthPatternsMatch 
(SLengthListPtr llp1,
 SLengthListPtr llp2)
{
    TSizeInfoPtr sip1, sip2;

    if (llp1 == NULL  ||  llp2 == NULL
        ||  llp1->lengthrepeats == NULL
        ||  llp2->lengthrepeats == NULL) {
        return eFalse;
    }
    for (sip1 = llp1->lengthrepeats, sip2 = llp2->lengthrepeats;
         sip1 != NULL  &&  sip2 != NULL;
         sip1 = sip1->next, sip2 = sip2->next) {
        if ( ! s_SizeInfoIsEqual (sip1, sip2)
          ||  (sip1->next == NULL  &&  sip2->next != NULL)
          ||  (sip1->next != NULL  &&  sip2->next == NULL)) {
            return eFalse;
        }
    }
    return eTrue;
}


/* This function examines a list of SLengthListData structures to see if
 * one of them matches llp.  If so, the value of num_appearances in that
 * list is incremented by one and llp is freed, otherwise llp is added
 * to the end of the list.
 * The function returns a pointer to the list of LenghtListData structures.
 */
static SLengthListPtr
s_AddLengthList
(SLengthListPtr list,
 SLengthListPtr llp)
{
    SLengthListPtr prev_llp;

    if (list == NULL) {
        list = llp;
    } else {
        prev_llp = list;
        while ( prev_llp->next  &&  ! s_DoLengthPatternsMatch (prev_llp, llp)) {
            prev_llp = prev_llp->next;
        }
        if (s_DoLengthPatternsMatch (prev_llp, llp)) {
            prev_llp->num_appearances ++;
            s_LengthListFree (llp);
        } else {
            prev_llp->next = llp;
        }
    }
    return list;
}


/* This function examines the last SLengthListData structure in list to
 * see if it matches llp.  If so, the function increments the value of
 * num_appearances for the last SLengthListData structure in list and
 * frees llp, otherwise the function appends llp to the end of list.
 * The function returns a pointer to the list of SLengthListData structures.
 */
static SLengthListPtr
s_AddPatternRepeat
(SLengthListPtr list,
 SLengthListPtr llp)
{
    SLengthListPtr prev_llp;

    if (list == NULL) {
        list = llp;
    } else {
        prev_llp = list;
        while ( prev_llp->next != NULL ) {
             prev_llp = prev_llp->next;
        }
        if (s_DoLengthPatternsMatch (prev_llp, llp)) {
            prev_llp->num_appearances ++;
            s_LengthListFree (llp);
        } else {
            prev_llp->next = llp;
        }
    }
    return list;
}


/* This set of functions is used for storing and analyzing individual lines
 * or tokens from an alignment file.
 */

/* This function allocates memory for a new SLineInfo structure and
 * initializes the structure with a saved copy of string and the specified
 * values of line_num and line_offset.
 * The function returns a pointer to the new SLineInfo structure.
 */
static TLineInfoPtr
s_LineInfoNew
(char * string,
 int    line_num,
 int    line_offset)
{
    TLineInfoPtr lip;

    lip = (TLineInfoPtr) malloc (sizeof (SLineInfo));
    if (lip == NULL) {
        return NULL;
    }
    lip->data = strdup (string);
    lip->line_num = line_num;
    lip->line_offset = line_offset;
    lip->delete_me = eFalse;
    lip->next = NULL;
    return lip;
}


/* This function recursively frees the memory associated with the structures
 * and members of the structures in a linked list of SLineInfo structures.
 */
static void s_LineInfoFree (TLineInfoPtr lip)
{
    if (lip == NULL) {
        return;
    }
    s_LineInfoFree (lip->next);
    lip->next = NULL;
    free (lip->data);
    free (lip);
}


/* This function deletes from a linked list of SLineInfo structures
 * those structures for which the delete_me flag has been set.  The function
 * returns a pointer to the beginning of the new list.
 */
static TLineInfoPtr s_DeleteLineInfos (TLineInfoPtr list)
{
    TLineInfoPtr prev = NULL;
    TLineInfoPtr lip, nextlip;

    lip = list;
    while (lip != NULL) {
        nextlip = lip->next;
        if (lip->delete_me) {
            if (prev != NULL) {
                prev->next = lip->next;
            } else {
                list = lip->next;
            }
            lip->next = NULL;
            s_LineInfoFree (lip);
        } else {
            prev = lip;
        }
        lip = nextlip;
    }
    return list;
}
     
 
/* This function creates a new SLineInfo structure, populates it with
 * a copy of string and the specified line_num and line_offset values,
 * and appends it to the end of "list" if list is not NULL.
 * The function will return a pointer to the newly created structure
 * if list is NULL, otherwise the function will return list.
 */
static TLineInfoPtr 
s_AddLineInfo
(TLineInfoPtr list,
 char * string,
 int    line_num,
 int    line_offset)