src/newick.c

   1 /* newick.c    2012-02-09 */
   2
   3 /* Copyright 2007-2008 Vincent Lefort */
   4
   5 /* This file is part of the R-package `ape'. */
   6 /* See the file ../COPYING for licensing issues. */
   7
   8 #include "me.h"
   9
  10 int nodeCount;
  11 int edgeCount;
  12
  13 int whiteSpace(char c)
  14 {
  15   if ((' ' == c) || ('\t' == c) || ('\n' == c))
  16     return(1);
  17   else return(0);
  18 }
  19
  20 int leaf(node *v)
  21 {
  22   int count = 0;
  23   if (NULL != v->parentEdge)
  24     count++;
  25   if (NULL != v->leftEdge)
  26     count++;
  27   if (NULL != v->rightEdge)
  28     count++;
  29   if (NULL != v->middleEdge)
  30     count++;
  31   if (count > 1)
  32     return(0);
  33   return(1);
  34 }
  35
  36 /*decodeNewickSubtree is used to turn a string of the form
  37   "(v1:d1,v2:d2,(subtree) v3:d3....vk:dk) subroot:d," into a subtree
  38   rooted at subrooted, with corresponding subtrees and leaves at v1
  39   through vk.  It is called recursively on subtrees*/
  40
  41 node *decodeNewickSubtree(char *treeString, tree *T, int *uCount)
  42 {
  43   node *thisNode;
  44   node *centerNode;
  45   double thisWeight;
  46   edge *thisEdge;
  47 //  char label[MAX_LABEL_LENGTH];
  48   char stringWeight[MAX_LABEL_LENGTH];
  49   int state;
  50   int i = 0;
  51   int j;
  52   int left,right;
  53   int parcount;
  54 //  snprintf(label,14,"Default_Label\0");
  55   left = right = 0;
  56   parcount = 0;
  57   state = ReadOpenParenthesis;
  58   if('(' == treeString[0])
  59     parcount++;
  60   //centerNode = makeNode(label,NULL,nodeCount++);
  61   centerNode = makeNode("",NULL,nodeCount++);
  62   T->size++;
  63   while(parcount > 0)
  64     {
  65       while(whiteSpace(treeString[i]))
  66         i++;
  67       switch(state)
  68         {
  69         case(ReadOpenParenthesis):
  70           if('(' != treeString[0])
  71             {
  72               error("error reading subtree");
  73             }
  74           i++;
  75           state = ReadSubTree;
  76           break;
  77         case(ReadSubTree):
  78           if('(' == treeString[i])  /*if treeString[i] is a left parenthesis,
  79                                       we scan down the string until we find its partner.
  80                                       the relative number of '('s vs. ')'s is counted
  81                                       by the variable parcount*/
  82             {
  83               left = i++;
  84               parcount++;
  85               while(parcount > 1)
  86                 {
  87                   while (('(' != treeString[i]) && (')' != treeString[i]))
  88                     i++;  /*skip over characters which are not parentheses*/
  89                   if('(' == treeString[i])
  90                     parcount++;
  91                   else if (')' == treeString[i])
  92                     parcount--;
  93                   i++;
  94                 }  /*end while */
  95               right = i;  /*at this point, the subtree string goes from
  96                             treeString[left] to treeString[right - 1]*/
  97               thisNode = decodeNewickSubtree(treeString + left,T,uCount);  /*note that this
  98                                                                       step will put
  99                                                                       thisNode in T*/
 100               i = right;  /*having created the node for the subtree, we move
 101                             to assigning the label for the new node.
 102                             treeString[right] will be the start of this label */
 103             } /* end if ('(' == treeString[i]) condition */
 104           else
 105             {
 106               //thisNode = makeNode(label,NULL,nodeCount++);
 107               thisNode = makeNode("",NULL,nodeCount++);
 108               T->size++;
 109             }
 110           state = ReadLabel;
 111           break;
 112         case(ReadLabel):
 113           left = i;  /*recall "left" is the left marker for the substring, "right" the right*/
 114           if (':' == treeString[i])   /*this means an internal node?*/
 115             {
 116               //sprintf(thisNode->label,"I%d",(*uCount)++);
 117               //snprintf(thisNode->label,MAX_LABEL_LENGTH,"I%d",(*uCount)++);
 118               (*uCount)++;
 119               right = i;
 120             }
 121           else
 122             {
 123               while((':' != treeString[i]) && (',' != treeString[i]) && (')' != treeString[i]))
 124                 i++;
 125               right = i;
 126               j = 0;
 127               for(i = left; i < right;i++)
 128                 if(!(whiteSpace(treeString[i])))
 129                   thisNode->label[j++] = treeString[i];
 130               thisNode->label[j] = '\0';
 131             }
 132           if(':' == treeString[right])
 133             state = ReadWeight;
 134           else
 135             {
 136               state = AddEdge;
 137               thisWeight = 0.0;
 138             }
 139           i = right + 1;
 140           break;
 141         case(ReadWeight):
 142           left = i;
 143           while
 144             ((',' != treeString[i]) && (')' != treeString[i]))
 145             i++;
 146           right = i;
 147           j = 0;
 148           for(i = left; i < right; i++)
 149             stringWeight[j++] = treeString[i];
 150           stringWeight[j] = '\0';
 151           thisWeight = atof(stringWeight);
 152           state=AddEdge;
 153           break;
 154         case(AddEdge):
 155           //thisEdge = makeEdge(label,centerNode,thisNode,thisWeight);
 156           thisEdge = makeEdge("",centerNode,thisNode,thisWeight);
 157           thisNode->parentEdge = thisEdge;
 158           if (NULL == centerNode->leftEdge)
 159             centerNode->leftEdge = thisEdge;
 160           else if (NULL == centerNode->rightEdge)
 161             centerNode->rightEdge = thisEdge;
 162           else if (NULL == centerNode->middleEdge)
 163             centerNode->middleEdge = thisEdge;
 164           else
 165             {
 166               error("node %s has too many (>3) children.", centerNode->label);
 167             }
 168           //sprintf(thisEdge->label,"E%d",edgeCount++);
 169           //snprintf(thisEdge->label,MAX_LABEL_LENGTH,"E%d",edgeCount++);
 170           edgeCount++;
 171           i = right + 1;
 172           if (',' == treeString[right])
 173             state = ReadSubTree;
 174           else
 175             parcount--;
 176           break;
 177         }
 178     }
 179   return(centerNode);
 180 }
 181
 182 tree *readNewickString (char *str, int numLeaves)
 183 {
 184   tree *T;
 185   node *centerNode;
 186   int i = 0;
 187   int j = 0;
 188   int inputLength;
 189   int uCount = 0;
 190   int parCount = 0;
 191   char rootLabel[MAX_LABEL_LENGTH];
 192   nodeCount = edgeCount = 0;
 193
 194   T = newTree();
 195
 196   if ('(' != str[0])
 197     {
 198       error("generated tree does not start with '('");
 199     }
 200   inputLength = strlen (str)+1;
 201   for(i = 0; i < inputLength; i++)
 202     {
 203       if ('(' == str[i])
 204         parCount++;
 205       else if (')' == str[i])
 206         parCount--;
 207       if (parCount > 0)
 208         ;
 209       else if (0 == parCount)
 210         {
 211           i++;
 212 /*        if(';' == str[i])
 213             sprintf(rootLabel,"URoot");
 214           else
 215             {*/
 216               while(';' != str[i])
 217                 if (!(whiteSpace (str[i++])))
 218                   rootLabel[j++] = str[i-1];  /*be careful here */
 219                 rootLabel[j] = '\0';
 220 //          }
 221           i = inputLength;
 222         }
 223       else if (parCount < 0)
 224         {
 225           error("generated tree has too many right parentheses");
 226         }
 227     }
 228   centerNode = decodeNewickSubtree (str, T, &uCount);
 229   snprintf (centerNode->label, MAX_LABEL_LENGTH, "%s", rootLabel); /* added "%s" following Jos Kafer's suggestion (2010-11-23) */
 230   T->root = centerNode;
 231   return(T);
 232 }