14 int whiteSpace(char c)
16 if ((' ' == c) || ('\t' == c) || ('\n' == c))
24 if (NULL != v->parentEdge)
26 if (NULL != v->leftEdge)
28 if (NULL != v->rightEdge)
30 if (NULL != v->middleEdge)
37 /*decodeNewickSubtree is used to turn a string of the form
38 "(v1:d1,v2:d2,(subtree) v3:d3....vk:dk) subroot:d," into a subtree
39 rooted at subrooted, with corresponding subtrees and leaves at v1
40 through vk. It is called recursively on subtrees*/
42 node *decodeNewickSubtree(char *treeString, tree *T, int *uCount)
48 // char label[MAX_LABEL_LENGTH];
49 char stringWeight[MAX_LABEL_LENGTH];
55 // snprintf(label,14,"Default_Label\0");
58 state = ReadOpenParenthesis;
59 if('(' == treeString[0])
61 //centerNode = makeNode(label,NULL,nodeCount++);
62 centerNode = makeNode("",NULL,nodeCount++);
66 while(whiteSpace(treeString[i]))
70 case(ReadOpenParenthesis):
71 if('(' != treeString[0])
73 Rprintf("Error reading subtree.\n");
80 if('(' == treeString[i]) /*if treeString[i] is a left parenthesis,
81 we scan down the string until we find its partner.
82 the relative number of '('s vs. ')'s is counted
83 by the variable parcount*/
89 while (('(' != treeString[i]) && (')' != treeString[i]))
90 i++; /*skip over characters which are not parentheses*/
91 if('(' == treeString[i])
93 else if (')' == treeString[i])
97 right = i; /*at this point, the subtree string goes from
98 treeString[left] to treeString[right - 1]*/
99 thisNode = decodeNewickSubtree(treeString + left,T,uCount); /*note that this
102 i = right; /*having created the node for the subtree, we move
103 to assigning the label for the new node.
104 treeString[right] will be the start of this label */
105 } /* end if ('(' == treeString[i]) condition */
108 //thisNode = makeNode(label,NULL,nodeCount++);
109 thisNode = makeNode("",NULL,nodeCount++);
115 left = i; /*recall "left" is the left marker for the substring, "right" the right*/
116 if (':' == treeString[i]) /*this means an internal node?*/
118 //sprintf(thisNode->label,"I%d",(*uCount)++);
119 //snprintf(thisNode->label,MAX_LABEL_LENGTH,"I%d",(*uCount)++);
125 while((':' != treeString[i]) && (',' != treeString[i]) && (')' != treeString[i]))
129 for(i = left; i < right;i++)
130 if(!(whiteSpace(treeString[i])))
131 thisNode->label[j++] = treeString[i];
132 thisNode->label[j] = '\0';
134 if(':' == treeString[right])
146 ((',' != treeString[i]) && (')' != treeString[i]))
150 for(i = left; i < right; i++)
151 stringWeight[j++] = treeString[i];
152 stringWeight[j] = '\0';
153 thisWeight = atof(stringWeight);
157 //thisEdge = makeEdge(label,centerNode,thisNode,thisWeight);
158 thisEdge = makeEdge("",centerNode,thisNode,thisWeight);
159 thisNode->parentEdge = thisEdge;
160 if (NULL == centerNode->leftEdge)
161 centerNode->leftEdge = thisEdge;
162 else if (NULL == centerNode->rightEdge)
163 centerNode->rightEdge = thisEdge;
164 else if (NULL == centerNode->middleEdge)
165 centerNode->middleEdge = thisEdge;
168 Rprintf("Error: node %s has too many (>3) children.\n",centerNode->label);
171 //sprintf(thisEdge->label,"E%d",edgeCount++);
172 //snprintf(thisEdge->label,MAX_LABEL_LENGTH,"E%d",edgeCount++);
175 if (',' == treeString[right])
185 tree *readNewickString (char *str, int numLeaves)
194 char rootLabel[MAX_LABEL_LENGTH];
195 nodeCount = edgeCount = 0;
201 Rprintf("Error reading generated tree - does not start with '('.\n");
204 inputLength = strlen (str)+1;
205 for(i = 0; i < inputLength; i++)
209 else if (')' == str[i])
213 else if (0 == parCount)
217 sprintf(rootLabel,"URoot");
221 if (!(whiteSpace (str[i++])))
222 rootLabel[j++] = str[i-1]; /*be careful here */
227 else if (parCount < 0)
229 Rprintf("Error reading generated tree. Too many right parentheses.\n");
233 centerNode = decodeNewickSubtree (str, T, &uCount);
234 snprintf (centerNode->label, MAX_LABEL_LENGTH, rootLabel);
235 T->root = centerNode;
239 tree *loadNewickTree(FILE *ifile, int numLeaves)
241 // char label[] = "EmptyEdge";
252 char rootLabel[MAX_LABEL_LENGTH];
253 nodeCount = edgeCount = 0;
255 nextString = (char *) malloc(numLeaves*INPUT_SIZE*sizeof(char));
256 if (NULL == nextString)
257 nextString = (char *) malloc(MAX_INPUT_SIZE*sizeof(char));
259 while(1 == fscanf(ifile,"%c",&c))
270 nextString[i++] = ' ';
272 else /*note that this else goes with if(whiteSpace(c))*/
278 if ('(' != nextString[0])
280 fprintf(stderr,"Error reading input file - does not start with '('.\n");
284 for(i = 0; i < inputLength;i++)
286 if ('(' == nextString[i])
288 else if (')' == nextString[i])
292 else if (0 == parCount)
295 /* if(';' == nextString[i])
296 sprintf(rootLabel,"URoot");
299 while(';' != nextString[i])
300 if(!(whiteSpace(nextString[i++])))
301 rootLabel[j++] = nextString[i-1]; /*be careful here */
306 else if (parCount < 0)
308 fprintf(stderr,"Error reading tree input file. Too many right parentheses.\n");
312 centerNode = decodeNewickSubtree(nextString,T,&uCount);
313 snprintf(centerNode->label, MAX_LABEL_LENGTH, rootLabel);
314 T->root = centerNode;
319 double GetSubTreeLength (tree *T, edge *e)
323 if ( (NULL != e) && (! leaf(e->head) )) {
324 ret += GetSubTreeLength (T, e->head->leftEdge);
325 ret += GetSubTreeLength (T, e->head->rightEdge);
331 void NewickPrintSubtree(tree *T, edge *e, char *str)
336 Rprintf("Error with Newick Printing routine.\n");
341 if (strlen (str) < MAX_INPUT_SIZE -2)
342 strncat (str, "(", 1);
343 NewickPrintSubtree(T,e->head->leftEdge,str);
344 if (strlen (str) < MAX_INPUT_SIZE -2)
345 strncat (str, ",", 1);
346 NewickPrintSubtree(T,e->head->rightEdge,str);
347 if (strlen (str) < MAX_INPUT_SIZE -2)
348 strncat (str, ")", 1);
350 if (strlen (str) < MAX_INPUT_SIZE - strlen (e->head->label) -1)
351 strncat (str, e->head->label, strlen (e->head->label));
353 if (strlen (str) < MAX_INPUT_SIZE - 2)
354 strncat (str, ":", 1);
356 tmp = (char *)R_alloc(INPUT_SIZE, sizeof(char));
359 strncpy(tmp, "", strlen(tmp));
361 snprintf (tmp, INPUT_SIZE, "%lf", e->distance);
362 if (strlen (str) < MAX_INPUT_SIZE - strlen (tmp) -1)
363 strncat (str, tmp, strlen (tmp));
369 double GetBinaryTreeLength (tree *T)
374 e = T->root->leftEdge;
377 f = rootchild->leftEdge;
379 ret += GetSubTreeLength (T, f);
380 f = rootchild->rightEdge;
382 ret += GetSubTreeLength (T, f);
387 void NewickPrintBinaryTree(tree *T, char *str)
392 e = T->root->leftEdge;
394 if (strlen (str) < MAX_INPUT_SIZE -2)
395 strncat (str, "(", 1);
396 f = rootchild->leftEdge;
399 NewickPrintSubtree(T,f,str);
400 if (strlen (str) < MAX_INPUT_SIZE -2)
401 strncat (str, ",", 1);
403 f = rootchild->rightEdge;
406 NewickPrintSubtree(T,f,str);
407 if (strlen (str) < MAX_INPUT_SIZE -2)
408 strncat (str, ",", 1);
410 if (strlen (str) < MAX_INPUT_SIZE - strlen (T->root->label) -1)
411 strncat (str, T->root->label, strlen (T->root->label));
413 if (strlen (str) < MAX_INPUT_SIZE - 2)
414 strncat (str, ":", 1);
416 tmp = (char *)R_alloc(INPUT_SIZE, sizeof(char));
419 strncpy(tmp, "", strlen(tmp));
421 snprintf (tmp, INPUT_SIZE, "%lf", e->distance);
422 if (strlen (str) < MAX_INPUT_SIZE - strlen (tmp) -1)
423 strncat (str, tmp, strlen (tmp));
425 if (strlen (str) < MAX_INPUT_SIZE - 2)
426 strncat (str, ")", 1);
428 if (NULL != rootchild->label)
429 if (strlen (str) < MAX_INPUT_SIZE - strlen (rootchild->label) -1)
430 strncat (str, T->root->label, strlen (rootchild->label));
432 if (strlen (str) < MAX_INPUT_SIZE - 3)
433 strncat (str, ";\n", 2);
439 double GetTrinaryTreeLength (tree *T)
443 f = T->root->leftEdge;
445 ret += GetSubTreeLength (T, f);
446 f = T->root->rightEdge;
448 ret += GetSubTreeLength (T, f);
449 f = T->root->middleEdge;
451 ret += GetSubTreeLength (T, f);
456 void NewickPrintTrinaryTree(tree *T, char *str)
459 f = T->root->leftEdge;
460 if (strlen (str) < MAX_INPUT_SIZE -2)
461 strncat (str, "(", 1);
464 NewickPrintSubtree(T,f,str);
465 if (strlen (str) < MAX_INPUT_SIZE -2)
466 strncat (str, ",", 1);
468 f = T->root->rightEdge;
471 NewickPrintSubtree(T,f,str);
472 if (strlen (str) < MAX_INPUT_SIZE -2)
473 strncat (str, ",", 1);
475 f = T->root->middleEdge;
478 NewickPrintSubtree(T,f,str);
479 if (strlen (str) < MAX_INPUT_SIZE -2)
480 strncat (str, ")", 1);
482 if (NULL != T->root->label)
483 if (strlen (str) < MAX_INPUT_SIZE - strlen (T->root->label) -1)
484 strncat (str, T->root->label, strlen (T->root->label));
485 if (strlen (str) < MAX_INPUT_SIZE - 3)
486 strncat (str, ";\n", 2);
490 void NewickPrintTreeStr(tree *T, char *str)
493 NewickPrintBinaryTree(T,str);
495 NewickPrintTrinaryTree(T,str);
498 double GetTreeLength (tree *T)
502 ret = GetBinaryTreeLength (T);
504 ret = GetTrinaryTreeLength (T);
508 void NewickPrintTree(tree *T, FILE *ofile)
511 NewickPrintBinaryTree(T,ofile);
513 NewickPrintTrinaryTree(T,ofile);
516 //edge *depthFirstTraverse(tree *T, edge *e);