str_util.c

fastDNAml is an attempt to solve the same problem as DNAML, but to do so faster and using less memo

#include  <stdlib.h>
#include  <stdio.h>
#include  <string.h>
#include  <math.h>
#include  "fastDNAml_types.h"
#include  "fastDNAml_funcs.h"
#include  "fastDNAml_globals.h"


/*=======================================================================*/
/*                        Read a tree from a string                      */
/*=======================================================================*/


int str_treeFinishCom (char **treestrp, char **strp)
                      /* treestrp -- tree string pointer */
                      /* strp -- comment string pointer */
  { /* str_treeFinishCom */
    int  ch;
    while ( (ch=*(*treestrp)++)!='\0' && ch!=']' ) {
      if (strp != NULL) *(*strp)++ = ch;    /* save character  */
      if (ch == '[') {                      /* nested comment; find its end */
        if ((ch=str_treeFinishCom(treestrp,strp)) == '\0')  break;
        if (strp != NULL) *(*strp)++ = ch;  /* save closing ]  */
        }
      }
    if (strp != NULL) **strp = '\0';        /* terminate string  */
    return  ch;
  } /* str_treeFinishCom */


int str_treeGetCh (char **treestrp)
    /* get next nonblank, noncomment character */
  { /* str_treeGetCh */
    int  ch;
    while ((ch=*(*treestrp)++) != '\0') {
      if (whitechar(ch)) ;
      else if (ch == '[') {                  /* comment; find its end */
        if ((ch = str_treeFinishCom(treestrp,(char**)NULL)) == '\0')  break;
        }
      else  break;
      }

    return  ch;
  } /* str_treeGetCh */


boolean  treeLabelEnd (int ch)
  { /* treeLabelEnd */
    switch (ch) {
        case EOF:  case '\0':  case '\t':  case '\n':  case ' ':
        case ':':  case ',':   case '(':   case ')':   case '[':
        case ';':
          return TRUE;
        default:
          break;
        }
    return FALSE;
  } /* treeLabelEnd */


boolean  str_treeGetLabel (char **treestrp, char *lblPtr, int maxlen)
  { /* str_treeGetLabel */
    int      ch;
    boolean  done, quoted, lblfound;


    if (--maxlen < 0)
      lblPtr = (char*)NULL;  /* reserves space for '\0' */
    else if(lblPtr == NULL)
      maxlen = 0;

    ch = *(*treestrp)++;
    done = treeLabelEnd(ch);

    lblfound = !done;
    quoted = (ch == '\'');
    if (quoted && ! done) {
      ch = *(*treestrp)++;
      done = (ch == '\0');
    }

    while(!done) {
      if (quoted) {
        if (ch == '\'') {
          ch = *(*treestrp)++;
          if (ch != '\'') break;
        }
      }
      else if (treeLabelEnd(ch))
        break;
      else if (ch == '_')
        ch = ' ';
      if (--maxlen >= 0) *lblPtr++ = ch;
      ch = *(*treestrp)++;
      if (ch == '\0') break;
    }

    (*treestrp)--;

    if (lblPtr != NULL) *lblPtr = '\0';

    return lblfound;
  } /* str_treeGetLabel */


boolean  str_treeFlushLabel (char **treestrp)
  { /* str_treeFlushLabel */
    return  str_treeGetLabel(treestrp, (char*)NULL, (int)0);
  } /* str_treeFlushLabel */


int  treeFindTipByLabel (char  *str, tree *tr)
                     /*  str -- label string pointer */
  { /* treeFindTipByLabel */
    nodeptr  q;
    char    *nameptr;
    int      ch, i, n;
    boolean  found;

    for (n = 1; n <= tr->mxtips; n++) {
      q = tr->nodep[n];
      if (! (q->back)) {          /*  Only consider unused tips */
        i = 0;
        nameptr = q->name;
        while ((found = (str[i++] == (ch = *nameptr++))) && ch) ;
        if (found) return n;
        }
      }

    printf("ERROR: Cannot find tree species: %s\n", str);

    return  0;
  } /* treeFindTipByLabel */


int  str_treeFindTipName (char **treestrp, tree *tr)         /*DKB-orig*/
/*int  str_treeFindTipName (char **treestrp, tree *tr, int ch)*/   /*DKB-change*/
  { /* str_treeFindTipName */
    nodeptr  q;
    char    *nameptr, str[nmlngth+2];
    int      i, n;

    if (tr->prelabeled) {
      if (str_treeGetLabel(treestrp, str, nmlngth+2)) {
        n = treeFindTipByLabel(str, tr);
      }
      else
        n = 0;
      }

    else if (tr->ntips < tr->mxtips) {
      n = tr->ntips + 1;
      nameptr = tr->nodep[n]->name;
      if (! str_treeGetLabel(treestrp, nameptr, nmlngth+1)) n = 0;
      }

    else {
      n = 0;
      }

    return  n;
  } /* str_treeFindTipName */


boolean str_treeProcessLength (char **treestrp, double *dptr)
  { /* str_treeProcessLength */
    int     used;

    if(!str_treeGetCh(treestrp))  return FALSE;    /*  Skip comments */
    (*treestrp)--;

    if (sscanf(*treestrp, "%lf%n", dptr, &used) != 1) {
      printf("ERROR: str_treeProcessLength: Problem reading branch length\n");
      printf("%40s\n", *treestrp);
      *dptr = 0.0;
      return FALSE;
      }
    else {
      *treestrp += used;
      }

    return  TRUE;
  } /* str_treeProcessLength */


boolean  str_treeFlushLen (char **treestrp)
  { /* str_treeFlushLen */
    int  ch;
    double  x;

    if ((ch = str_treeGetCh(treestrp)) == ':')
    /*return str_treeProcessLength(treestrp, (double*)NULL);*/   /*DKB-orig*/
      return str_treeProcessLength(treestrp, &x);              /*DKB-change*/
    else {
      (*treestrp)--;
      return TRUE;
      }
  } /* str_treeFlushLen */


boolean  str_treeNeedCh (char **treestrp, int c1, char *where)
  { /* str_treeNeedCh */
    int  c2, i;

    if ((c2 = str_treeGetCh(treestrp)) == c1)  return TRUE;

    printf("ERROR: Missing '%c' %s tree; ", c1, where);
    if (c2 == '\0') 
      printf("end-of-string");
    else {
      putchar('"');
      for (i = 24; i-- && (c2 != '\0'); c2 = *(*treestrp)++)  putchar(c2);
      putchar('"');
      }

    printf(" found instead\n");
    return FALSE;
  } /* str_treeNeedCh */


boolean str_processTreeCom(tree *tr, char **treestrp)
  { /* str_processTreeCom */
    char  *com, *com_end;
    int  text_started, functor_read, com_open;

    com = *treestrp;

    /* Comment must begin with either "phylip_tree" or "pseudoNewick".
     * If it is neither, return FALSE. */
    functor_read = text_started = 0;
    sscanf(com, " p%nhylip_tree(%n", &text_started, &functor_read);
    if (functor_read) {
      com += functor_read;
    }
    else if (text_started) {
      com += text_started;
      sscanf(com, "seudoNewick(%n", &functor_read);
      if (! functor_read) {
        printf("Start of tree 'p...' not understood.\n");
        return  FALSE;
      }
      else {
        com += functor_read;
      }
    }

    /* Find opening bracket of comment */
    com_open = 0;
    sscanf(com, " [%n", &com_open);
    com += com_open;

    /* Read comment. */
    if (com_open) {
      if (!(com_end = strchr(com, ']'))) {
        printf("Missing end of tree comment.\n");
        return  FALSE;
      }
      *com_end = 0;
      (void)readKeyValue(com,likelihood_key,"%lg",(void*)&(tr->likelihood));
      (void)readKeyValue(com,opt_level_key, "%d", (void*)&(tr->opt_level));
      (void)readKeyValue(com,smoothed_key,  "%d", (void*)&(tr->smoothed));
      *com_end = ']';
      com_end++;

      /* Remove trailing comma, and return addr of next char in treestp */
      if (functor_read) {
        text_started = 0;
        sscanf(com_end, " ,%n", & text_started);
        com_end += text_started;
      }
      *treestrp = com_end;
    }
    return (functor_read > 0);
  } /* str_processTreeCom */


boolean str_treeReadLen (char *treestr, tree *tr)
    /* read string with representation of tree */
  { /* str_treeReadLen */
    nodeptr  p;
    int  i;
    boolean  is_fact, found;

    for(i=1; i<=(tr->mxtips); i++) tr->nodep[i]->back = (node*)NULL;
    tr->start       = tr->nodep[tr->mxtips];
    tr->ntips       = 0;
    tr->nextnode    = tr->mxtips + 1;
    tr->opt_level   = 0;
    tr->log_f_valid = 0;
    tr->smoothed    = (myprogtype==DNAML_MASTER);
    tr->rooted      = FALSE;

    is_fact = str_processTreeCom(tr,&treestr);
    p = tr->nodep[(tr->nextnode)++];

    if(!str_treeNeedCh(&treestr, '(', "at start of"))       return FALSE;
    if(!str_addElementLen(&treestr, tr, p))                 return FALSE;
    if(!str_treeNeedCh(&treestr, ',', "in"))                return FALSE;
    if(!str_addElementLen(&treestr, tr, p->next))           return FALSE;
    if(!tr->rooted) {
      if(str_treeGetCh(&treestr) == ',') {        /*  An unrooted format */
        if(!str_addElementLen(&treestr,tr,p->next->next)) return FALSE;
      }
      else {                                       /*  A rooted format */
        p->next->next->back = (nodeptr) NULL;
        tr->rooted = TRUE;
        treestr--;
      }
    }
    if(!str_treeNeedCh(&treestr, ')', "in"))                 return FALSE;
  /*if(!str_treeFlushLabel(&treestr))                        return FALSE;*//*DKB-orig*/
    if(!str_treeFlushLen(&treestr))                          return FALSE;
    if(is_fact) {
      if(!str_treeNeedCh(& treestr, ')', "at end of"))       return FALSE;
      if(!str_treeNeedCh(& treestr, '.', "at end of"))       return FALSE;
    }
    else {
      if(!str_treeNeedCh(& treestr, ';', "at end of"))       return FALSE;
    }

    if(tr->rooted)  if (! uprootTree(tr, p->next->next))     return FALSE;
    tr->start = p->next->next->back;  /* This is start used by treeString */

    return  (initrav(tr,tr->start) && initrav(tr,tr->start->back));
  } /* str_treeReadLen */