tree.cpp

   1 /*
   2  *  tree.cpp
   3  *  Mothur
   4  *
   5  *  Created by Sarah Westcott on 1/22/09.
   6  *  Copyright 2009 Schloss Lab UMASS Amherst. All rights reserved.
   7  *
   8  */
   9
  10 #include "tree.h"
  11
  12
  13 /*****************************************************************/
  14 Tree::Tree() {
  15         try {
  16                 globaldata = GlobalData::getInstance();
  17
  18                 if (globaldata->runParse == true) {  parseTreeFile();  globaldata->runParse = false;  }
  19 //for(int i = 0; i <    globaldata->Treenames.size(); i++) { cout << i << '\t' << globaldata->Treenames[i] << endl;  }
  20                 numLeaves = globaldata->Treenames.size();
  21                 numNodes = 2*numLeaves - 1;
  22
  23                 tree.resize(numNodes);
  24
  25                 //initialize tree with correct number of nodes, name and group info.
  26                 for (int i = 0; i < numNodes; i++) {
  27                         //initialize leaf nodes
  28                         if (i <= (numLeaves-1)) {
  29                                 tree[i].setName(globaldata->Treenames[i]);
  30                                 tree[i].setGroup(globaldata->gTreemap->getGroup(globaldata->Treenames[i]));
  31                                 //set pcount and pGroup for groupname to 1.
  32                                 tree[i].pcount[globaldata->gTreemap->getGroup(globaldata->Treenames[i])] = 1;
  33                                 tree[i].pGroups[globaldata->gTreemap->getGroup(globaldata->Treenames[i])] = 1;
  34                                 //Treemap knows name, group and index to speed up search
  35                                 globaldata->gTreemap->setIndex(globaldata->Treenames[i], i);
  36
  37                         //intialize non leaf nodes
  38                         }else if (i > (numLeaves-1)) {
  39                                 tree[i].setName("");
  40                                 tree[i].setGroup("");
  41                         }
  42                 }
  43         }
  44         catch(exception& e) {
  45                 errorOut(e, "Tree", "Tree");
  46                 exit(1);
  47         }
  48 }
  49
  50 /*****************************************************************/
  51 Tree::~Tree() {}
  52 /*****************************************************************/
  53 void Tree::addNamesToCounts() {
  54         try {
  55                 //ex. seq1      seq2,seq3,se4
  56                 //              seq1 = pasture
  57                 //              seq2 = forest
  58                 //              seq4 = pasture
  59                 //              seq3 = ocean
  60
  61                 //before this function seq1.pcount = pasture -> 1
  62                 //after                            seq1.pcount = pasture -> 2, forest -> 1, ocean -> 1
  63
  64                 //before this function seq1.pgroups = pasture -> 1
  65                 //after                            seq1.pgroups = pasture -> 1 since that is the dominant group
  66
  67
  68                 //go through each leaf and update its pcounts and pgroups
  69                 for (int i = 0; i < numLeaves; i++) {
  70                         string name = tree[i].getName();
  71
  72                         map<string, string>::iterator itNames = globaldata->names.find(name);
  73
  74                         if (itNames == globaldata->names.end()) { mothurOut(name + " is not in your name file, please correct."); mothurOutEndLine(); exit(1);  }
  75                         else {
  76                                 vector<string> dupNames;
  77                                 splitAtComma(globaldata->names[name], dupNames);
  78
  79                                 map<string, int>::iterator itCounts;
  80                                 int maxPars = 1;
  81                                 for (int j = 0; j < dupNames.size(); j++) {
  82
  83                                         if (dupNames[j] != name) {//you already added yourself in the constructor
  84                                                 string group = globaldata->gTreemap->getGroup(dupNames[j]);
  85
  86                                                 //update pcounts
  87                                                 itCounts = tree[i].pcount.find(group);
  88                                                 if (itCounts == tree[i].pcount.end()) { //new group, add it
  89                                                         tree[i].pcount[group] = 1;
  90                                                 }else {
  91                                                         tree[i].pcount[group]++;
  92                                                 }
  93
  94                                                 //update pgroups
  95                                                 itCounts = tree[i].pGroups.find(group);
  96                                                 if (itCounts == tree[i].pGroups.end()) { //new group, add it
  97                                                         tree[i].pGroups[group] = 1;
  98                                                 }else {
  99                                                         tree[i].pGroups[group]++;
 100                                                 }
 101
 102                                                 //keep highest group
 103                                                 if(tree[i].pGroups[group] > maxPars){
 104                                                         maxPars = tree[i].pGroups[group];
 105                                                 }
 106                                         }//end if
 107                                 }//end for
 108
 109                                 if (maxPars > 1) { //then we have some more dominant groups
 110                                         //erase all the groups that are less than maxPars because you found a more dominant group.
 111                                         for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();){
 112                                                 if(it->second < maxPars){
 113                                                         tree[i].pGroups.erase(it++);
 114                                                 }else { it++; }
 115                                         }
 116                                         //set one remaining groups to 1
 117                                         for(it=tree[i].pGroups.begin();it!=tree[i].pGroups.end();it++){
 118                                                 tree[i].pGroups[it->first] = 1;
 119                                         }
 120                                 }//end if
 121
 122                         }//end else
 123                 }//end for
 124
 125         }
 126         catch(exception& e) {
 127                 errorOut(e, "Tree", "addNamesToCounts");
 128                 exit(1);
 129         }
 130 }
 131 /*****************************************************************/
 132 int Tree::getIndex(string searchName) {
 133         try {
 134                 //Treemap knows name, group and index to speed up search
 135                 // getIndex function will return the vector index or -1 if seq is not found.
 136                 int index = globaldata->gTreemap->getIndex(searchName);
 137                 return index;
 138
 139         }
 140         catch(exception& e) {
 141                 errorOut(e, "Tree", "getIndex");
 142                 exit(1);
 143         }
 144 }
 145 /*****************************************************************/
 146
 147 void Tree::setIndex(string searchName, int index) {
 148         try {
 149                 //set index in treemap
 150                 globaldata->gTreemap->setIndex(searchName, index);
 151         }
 152         catch(exception& e) {
 153                 errorOut(e, "Tree", "setIndex");
 154                 exit(1);
 155         }
 156 }
 157 /*****************************************************************/
 158 void Tree::assembleTree() {
 159         try {
 160
 161                 //if user has given a names file we want to include that info in the pgroups and pcount info.
 162                 if(globaldata->names.size() != 0) {  addNamesToCounts();  }
 163
 164                 //build the pGroups in non leaf nodes to be used in the parsimony calcs.
 165                 for (int i = numLeaves; i < numNodes; i++) {
 166                         tree[i].pGroups = (mergeGroups(i));
 167                         tree[i].pcount = (mergeGcounts(i));
 168                 }
 169         }
 170         catch(exception& e) {
 171                 errorOut(e, "Tree", "assembleTree");
 172                 exit(1);
 173         }
 174 }
 175 /*****************************************************************/
 176 void Tree::getCopy(Tree* copy) {
 177         try {
 178
 179                 //for each node in the tree copy its info
 180                 for (int i = 0; i < numNodes; i++) {
 181                         //copy name
 182                         tree[i].setName(copy->tree[i].getName());
 183
 184                         //copy group
 185                         tree[i].setGroup(copy->tree[i].getGroup());
 186
 187                         //copy branch length
 188                         tree[i].setBranchLength(copy->tree[i].getBranchLength());
 189
 190                         //copy parent
 191                         tree[i].setParent(copy->tree[i].getParent());
 192
 193                         //copy children
 194                         tree[i].setChildren(copy->tree[i].getLChild(), copy->tree[i].getRChild());
 195
 196                         //copy index in node and tmap
 197                         tree[i].setIndex(copy->tree[i].getIndex());
 198                         setIndex(copy->tree[i].getName(), getIndex(copy->tree[i].getName()));
 199
 200                         //copy pGroups
 201                         tree[i].pGroups = copy->tree[i].pGroups;
 202
 203                         //copy pcount
 204                         tree[i].pcount = copy->tree[i].pcount;
 205                 }
 206
 207         }
 208         catch(exception& e) {
 209                 errorOut(e, "Tree", "getCopy");
 210                 exit(1);
 211         }
 212 }
 213 /*****************************************************************/
 214 //returns a map with a groupname and the number of times that group was seen in the children
 215 //for instance if your children are white and black then it would return a map with 2 entries
 216 // p[white] = 1 and p[black] = 1.  Now go up a level and merge that with a node who has p[white] = 1
 217 //and you get p[white] = 2, p[black] = 1, but you erase the p[black] because you have a p value higher than 1.
 218
 219 map<string, int> Tree::mergeGroups(int i) {
 220         try {
 221                 int lc = tree[i].getLChild();
 222                 int rc = tree[i].getRChild();
 223
 224                 //set parsimony groups to left child
 225                 map<string,int> parsimony = tree[lc].pGroups;
 226
 227                 int maxPars = 1;
 228
 229                 //look at right child groups and update maxPars if right child has something higher for that group.
 230                 for(it=tree[rc].pGroups.begin();it!=tree[rc].pGroups.end();it++){
 231                         it2 = parsimony.find(it->first);
 232                         if (it2 != parsimony.end()) {
 233                                 parsimony[it->first]++;
 234                         }else {
 235                                 parsimony[it->first] = 1;
 236                         }
 237
 238                         if(parsimony[it->first] > maxPars){
 239                                 maxPars = parsimony[it->first];
 240                         }
 241                 }
 242
 243                 // this is true if right child had a greater parsimony for a certain group
 244                 if(maxPars > 1){
 245                         //erase all the groups that are only 1 because you found something with 2.
 246                         for(it=parsimony.begin();it!=parsimony.end();){
 247                                 if(it->second == 1){
 248                                         parsimony.erase(it++);
 249                                 }else { it++; }
 250                         }
 251                         //set one remaining groups to 1
 252                         //so with our above example p[white] = 2 would be left and it would become p[white] = 1
 253                         for(it=parsimony.begin();it!=parsimony.end();it++){
 254                                 parsimony[it->first] = 1;
 255                         }
 256
 257                 }
 258
 259                 return parsimony;
 260         }
 261         catch(exception& e) {
 262                 errorOut(e, "Tree", "mergeGroups");
 263                 exit(1);
 264         }
 265 }
 266 /*****************************************************************/
 267 //returns a map with a groupname and the number of times that group was seen in the children
 268 //for instance if your children are white and black then it would return a map with 2 entries
 269 // p[white] = 1 and p[black] = 1.  Now go up a level and merge that with a node who has p[white] = 1
 270 //and you get p[white] = 2, p[black] = 1, but you erase the p[black] because you have a p value higher than 1.
 271
 272 map<string, int> Tree::mergeUserGroups(int i, vector<string> g) {
 273         try {
 274
 275                 int lc = tree[i].getLChild();
 276                 int rc = tree[i].getRChild();
 277
 278                 //loop through nodes groups removing the ones the user doesn't want
 279                 for(it=tree[lc].pGroups.begin();it!=tree[lc].pGroups.end();){
 280                                 if (inUsersGroups(it->first, g) != true) {
 281                                         tree[lc].pGroups.erase(it++);
 282                                 }else { it++; }
 283                 }
 284
 285                 //loop through nodes groups removing the ones the user doesn't want
 286                 for(it=tree[rc].pGroups.begin();it!=tree[rc].pGroups.end();){
 287                                 if (inUsersGroups(it->first, g) != true) {
 288                                         tree[rc].pGroups.erase(it++);
 289                                 }else { it++; }
 290                 }
 291
 292                 //set parsimony groups to left child
 293                 map<string,int> parsimony = tree[lc].pGroups;
 294
 295                 int maxPars = 1;
 296
 297                 //look at right child groups and update maxPars if right child has something higher for that group.
 298                 for(it=tree[rc].pGroups.begin();it!=tree[rc].pGroups.end();it++){
 299                         it2 = parsimony.find(it->first);
 300                         if (it2 != parsimony.end()) {
 301                                 parsimony[it->first]++;
 302                         }else {
 303                                 parsimony[it->first] = 1;
 304                         }
 305
 306                         if(parsimony[it->first] > maxPars){
 307                                 maxPars = parsimony[it->first];
 308                         }
 309                 }
 310
 311                 // this is true if right child had a greater parsimony for a certain group
 312                 if(maxPars > 1){
 313                         //erase all the groups that are only 1 because you found something with 2.
 314                         for(it=parsimony.begin();it!=parsimony.end();){
 315                                 if(it->second == 1){
 316                                         parsimony.erase(it++);
 317                                 }else { it++; }
 318                         }
 319
 320                         for(it=parsimony.begin();it!=parsimony.end();it++){
 321                                 parsimony[it->first] = 1;
 322                         }
 323                 }
 324
 325                 return parsimony;
 326         }
 327         catch(exception& e) {
 328                 errorOut(e, "Tree", "mergeUserGroups");
 329                 exit(1);
 330         }
 331 }
 332
 333
 334 /**************************************************************************************************/
 335
 336 map<string,int> Tree::mergeGcounts(int position) {
 337         try{
 338                 map<string,int>::iterator pos;
 339
 340                 int lc = tree[position].getLChild();
 341                 int rc = tree[position].getRChild();
 342
 343                 map<string,int> sum = tree[lc].pcount;
 344
 345                 for(it=tree[rc].pcount.begin();it!=tree[rc].pcount.end();it++){
 346                         sum[it->first] += it->second;
 347                 }
 348                 return sum;
 349         }
 350         catch(exception& e) {
 351                 errorOut(e, "Tree", "mergeGcounts");
 352                 exit(1);
 353         }
 354 }
 355 /**************************************************************************************************/
 356
 357 void Tree::randomLabels(vector<string> g) {
 358         try {
 359
 360                 for(int i = 0; i < numLeaves; i++){
 361                         int z;
 362                         //get random index to switch with
 363                         z = int((float)(i+1) * (float)(rand()) / ((float)RAND_MAX+1.0));
 364
 365                         //you only want to randomize the nodes that are from a group the user wants analyzed, so
 366                         //if either of the leaf nodes you are about to switch are not in the users groups then you don't want to switch them.
 367                         bool treez, treei;
 368
 369                         treez = inUsersGroups(tree[z].getGroup(), g);
 370                         treei = inUsersGroups(tree[i].getGroup(), g);
 371
 372                         if ((treez == true) && (treei == true)) {
 373                                 //switches node i and node z's info.
 374                                 map<string,int> lib_hold = tree[z].pGroups;
 375                                 tree[z].pGroups = (tree[i].pGroups);
 376                                 tree[i].pGroups = (lib_hold);
 377
 378                                 string zgroup = tree[z].getGroup();
 379                                 tree[z].setGroup(tree[i].getGroup());
 380                                 tree[i].setGroup(zgroup);
 381
 382                                 string zname = tree[z].getName();
 383                                 tree[z].setName(tree[i].getName());
 384                                 tree[i].setName(zname);
 385
 386                                 map<string,int> gcount_hold = tree[z].pcount;
 387                                 tree[z].pcount = (tree[i].pcount);
 388                                 tree[i].pcount = (gcount_hold);
 389                         }
 390                 }
 391         }
 392         catch(exception& e) {
 393                 errorOut(e, "Tree", "randomLabels");
 394                 exit(1);
 395         }
 396 }
 397 /**************************************************************************************************/
 398
 399 void Tree::randomLabels(string groupA, string groupB) {
 400         try {
 401                 int numSeqsA = globaldata->gTreemap->seqsPerGroup[groupA];
 402                 int numSeqsB = globaldata->gTreemap->seqsPerGroup[groupB];
 403
 404                 vector<string> randomGroups(numSeqsA+numSeqsB, groupA);
 405                 for(int i=numSeqsA;i<randomGroups.size();i++){
 406                         randomGroups[i] = groupB;
 407                 }
 408                 random_shuffle(randomGroups.begin(), randomGroups.end());
 409
 410                 int randomCounter = 0;
 411                 for(int i=0;i<numLeaves;i++){
 412                         if(tree[i].getGroup() == groupA || tree[i].getGroup() == groupB){
 413                                 tree[i].setGroup(randomGroups[randomCounter]);
 414                                 tree[i].pcount.clear();
 415                                 tree[i].pcount[randomGroups[randomCounter]] = 1;
 416                                 tree[i].pGroups.clear();
 417                                 tree[i].pGroups[randomGroups[randomCounter]] = 1;
 418                                 randomCounter++;
 419                         }
 420                 }
 421         }
 422         catch(exception& e) {
 423                 errorOut(e, "Tree", "randomLabels");
 424                 exit(1);
 425         }
 426 }
 427 /**************************************************************************************************/
 428 void Tree::randomBlengths()  {
 429         try {
 430                 for(int i=numNodes-1;i>=0;i--){
 431                         int z = int((float)(i+1) * (float)(rand()) / ((float)RAND_MAX+1.0));
 432
 433                         float bl_hold = tree[z].getBranchLength();
 434                         tree[z].setBranchLength(tree[i].getBranchLength());
 435                         tree[i].setBranchLength(bl_hold);
 436                 }
 437         }
 438         catch(exception& e) {
 439                 errorOut(e, "Tree", "randomBlengths");
 440                 exit(1);
 441         }
 442 }
 443 /*************************************************************************************************/
 444 void Tree::assembleRandomUnifracTree(vector<string> g) {
 445         randomLabels(g);
 446         assembleTree();
 447 }
 448 /*************************************************************************************************/
 449 void Tree::assembleRandomUnifracTree(string groupA, string groupB) {
 450         randomLabels(groupA, groupB);
 451         assembleTree();
 452 }
 453
 454 /*************************************************************************************************/
 455 //for now it's just random topology but may become random labels as well later that why this is such a simple function now...
 456 void Tree::assembleRandomTree() {
 457         randomTopology();
 458         assembleTree();
 459 }
 460 /**************************************************************************************************/
 461
 462 void Tree::randomTopology() {
 463         try {
 464                 for(int i=0;i<numNodes;i++){
 465                         tree[i].setParent(-1);
 466                 }
 467                 for(int i=numLeaves;i<numNodes;i++){
 468                         tree[i].setChildren(-1, -1);
 469                 }
 470
 471                 for(int i=numLeaves;i<numNodes;i++){
 472                         int escape =0;
 473                         int rnd_index1, rnd_index2;
 474                         while(escape == 0){
 475                                 rnd_index1 = (int)(((double)rand() / (double) RAND_MAX)*i);
 476                                 if(tree[rnd_index1].getParent() == -1){escape = 1;}
 477                         }
 478
 479                         escape = 0;
 480                         while(escape == 0){
 481                                 rnd_index2 = (int)(((double)rand() / (double) RAND_MAX)*i);
 482                                 if(rnd_index2 != rnd_index1 && tree[rnd_index2].getParent() == -1){
 483                                         escape = 1;
 484                                 }
 485                         }
 486
 487                         tree[i].setChildren(rnd_index1,rnd_index2);
 488                         tree[i].setParent(-1);
 489                         tree[rnd_index1].setParent(i);
 490                         tree[rnd_index2].setParent(i);
 491                 }
 492         }
 493         catch(exception& e) {
 494                 errorOut(e, "Tree", "randomTopology");
 495                 exit(1);
 496         }
 497 }
 498 /*****************************************************************/
 499 void Tree::print(ostream& out) {
 500         try {
 501                 int root = findRoot();
 502                 printBranch(root, out, "branch");
 503                 out << ";" << endl;
 504         }
 505         catch(exception& e) {
 506                 errorOut(e, "Tree", "print");
 507                 exit(1);
 508         }
 509 }
 510 /*****************************************************************/
 511 void Tree::printForBoot(ostream& out) {
 512         try {
 513                 int root = findRoot();
 514                 printBranch(root, out, "boot");
 515                 out << ";" << endl;
 516         }
 517         catch(exception& e) {
 518                 errorOut(e, "Tree", "printForBoot");
 519                 exit(1);
 520         }
 521 }
 522
 523 /*****************************************************************/
 524 // This prints out the tree in Newick form.
 525 void Tree::createNewickFile(string f) {
 526         try {
 527                 int root = findRoot();
 528                 //filename = getRootName(globaldata->getTreeFile()) + "newick";
 529                 filename = f;
 530
 531                 openOutputFile(filename, out);
 532
 533                 printBranch(root, out, "branch");
 534
 535                 // you are at the end of the tree
 536                 out << ";" << endl;
 537                 out.close();
 538         }
 539         catch(exception& e) {
 540                 errorOut(e, "Tree", "createNewickFile");
 541                 exit(1);
 542         }
 543 }
 544
 545 /*****************************************************************/
 546 //This function finds the index of the root node.
 547
 548 int Tree::findRoot() {
 549         try {
 550                 for (int i = 0; i < numNodes; i++) {
 551                         //you found the root
 552                         if (tree[i].getParent() == -1) { return i; }
 553                         //cout << "i = " << i << endl;
 554                         //cout << "i's parent = " << tree[i].getParent() << endl;
 555                 }
 556                 return -1;
 557         }
 558         catch(exception& e) {
 559                 errorOut(e, "Tree", "findRoot");
 560                 exit(1);
 561         }
 562 }
 563
 564 /*****************************************************************/
 565 void Tree::printBranch(int node, ostream& out, string mode) {
 566         try {
 567
 568                 // you are not a leaf
 569                 if (tree[node].getLChild() != -1) {
 570                         out << "(";
 571                         printBranch(tree[node].getLChild(), out, mode);
 572                         out << ",";
 573                         printBranch(tree[node].getRChild(), out, mode);
 574                         out << ")";
 575                         if (mode == "branch") {
 576                                 //if there is a branch length then print it
 577                                 if (tree[node].getBranchLength() != -1) {
 578                                         out << ":" << tree[node].getBranchLength();
 579                                 }
 580                         }else if (mode == "boot") {
 581                                 //if there is a label then print it
 582                                 if (tree[node].getLabel() != -1) {
 583                                         out << tree[node].getLabel();
 584                                 }
 585                         }
 586                 }else { //you are a leaf
 587                         out << tree[node].getGroup();
 588                         if (mode == "branch") {
 589                                 //if there is a branch length then print it
 590                                 if (tree[node].getBranchLength() != -1) {
 591                                         out << ":" << tree[node].getBranchLength();
 592                                 }
 593                         }else if (mode == "boot") {
 594                                 //if there is a label then print it
 595                                 if (tree[node].getLabel() != -1) {
 596                                         out << tree[node].getLabel();
 597                                 }
 598                         }
 599                 }
 600
 601         }
 602         catch(exception& e) {
 603                 errorOut(e, "Tree", "printBranch");
 604                 exit(1);
 605         }
 606 }
 607
 608 /*****************************************************************/
 609
 610 void Tree::printTree() {
 611
 612         for(int i=0;i<numNodes;i++){
 613                 cout << i << '\t';
 614                 tree[i].printNode();
 615         }
 616
 617 }
 618
 619 /*****************************************************************/
 620 //this code is a mess and should be rethought...-slw
 621 void Tree::parseTreeFile() {
 622
 623         //only takes names from the first tree and assumes that all trees use the same names.
 624         try {
 625                 string filename = globaldata->getTreeFile();
 626                 ifstream filehandle;
 627                 openInputFile(filename, filehandle);
 628                 int c, comment;
 629                 comment = 0;
 630                 int done = 1;
 631
 632                 //ifyou are not a nexus file
 633                 if((c = filehandle.peek()) != '#') {
 634                         while((c = filehandle.peek()) != ';') {
 635                                 while ((c = filehandle.peek()) != ';') {
 636                                         // get past comments
 637                                         if(c == '[') {
 638                                                 comment = 1;
 639                                         }
 640                                         if(c == ']'){
 641                                                 comment = 0;
 642                                         }
 643                                         if((c == '(') && (comment != 1)){ break; }
 644                                         filehandle.get();
 645                                 }
 646
 647                                 done = readTreeString(filehandle);
 648                                 if (done == 0) { break; }
 649                         }
 650                 //ifyou are a nexus file
 651                 }else if((c = filehandle.peek()) == '#') {
 652                         string holder = "";
 653
 654                         // get past comments
 655                         while(holder != "translate" && holder != "Translate"){
 656                                 if(holder == "[" || holder == "[!"){
 657                                         comment = 1;
 658                                 }
 659                                 if(holder == "]"){
 660                                         comment = 0;
 661                                 }
 662                                 filehandle >> holder;
 663
 664                                 //if there is no translate then you must read tree string otherwise use translate to get names
 665                                 if((holder == "tree") && (comment != 1)){
 666                                         //pass over the "tree rep.6878900 = "
 667                                         while (((c = filehandle.get()) != '(') && ((c = filehandle.peek()) != EOF)) {;}
 668
 669                                         if(c == EOF) { break; }
 670                                         filehandle.putback(c);  //put back first ( of tree.
 671                                         done = readTreeString(filehandle);
 672
 673                                         break;
 674                                 }
 675
 676                                 if (done == 0) { break;  }
 677                         }
 678
 679                         //use nexus translation rather than parsing tree to save time
 680                         if((holder == "translate") || (holder == "Translate")) {
 681
 682                                 string number, name, h;
 683                                 h = ""; // so it enters the loop the first time
 684                                 while((h != ";") && (number != ";")) {
 685                                         filehandle >> number;
 686                                         filehandle >> name;
 687
 688                                         //c = , until done with translation then c = ;
 689                                         h = name.substr(name.length()-1, name.length());
 690                                         name.erase(name.end()-1);  //erase the comma
 691                                         globaldata->Treenames.push_back(number);
 692                                 }
 693                                 if(number == ";") { globaldata->Treenames.pop_back(); }  //in case ';' from translation is on next line instead of next to last name
 694                         }
 695                 }
 696                 filehandle.close();
 697         }
 698         catch(exception& e) {
 699                 errorOut(e, "Tree", "parseTreeFile");
 700                 exit(1);
 701         }
 702 }
 703 /*******************************************************/
 704
 705 /*******************************************************/
 706 int Tree::readTreeString(ifstream& filehandle)  {
 707         try {
 708                 int c;
 709                 string name;  //, k
 710
 711                 while((c = filehandle.peek()) != ';') {
 712 //k = c;
 713 //cout << " at beginning of while " <<  k << endl;
 714                         if(c == ')')  {
 715                                 //to pass over labels in trees
 716                                 c=filehandle.get();
 717                                 while((c!=',') && (c != -1) && (c!= ':') && (c!=';')){ c=filehandle.get(); }
 718                                 filehandle.putback(c);
 719                         }
 720                         if(c == ';') { return 0; }
 721                         if(c == -1) { return 0; }
 722                         //if you are a name
 723                         if((c != '(') && (c != ')') && (c != ',') && (c != ':') && (c != '\n') && (c != '\t') && (c != 32)) { //32 is space
 724                                 name = "";
 725                                 c = filehandle.get();
 726                         //k = c;
 727 //cout << k << endl;
 728                                 while ((c != '(') && (c != ')') && (c != ',') && (c != ':') && (c != '\n') && (c != 32) && (c != '\t')) {
 729                                         name += c;
 730                                         c = filehandle.get();
 731                         //k = c;
 732 //cout << " in name while " << k << endl;
 733                                 }
 734
 735 //cout << "name = " << name << endl;
 736                                 globaldata->Treenames.push_back(name);
 737                                 filehandle.putback(c);
 738 //k = c;
 739 //cout << " after putback" <<  k << endl;
 740                         }
 741
 742                         if(c  == ':') { //read until you reach the end of the branch length
 743                                 while ((c != '(') && (c != ')') && (c != ',') && (c != ';') && (c != '\n') && (c != '\t') && (c != 32)) {
 744                                         c = filehandle.get();
 745         //k = c;
 746         //cout << " in branch while " << k << endl;
 747                                 }
 748                                 filehandle.putback(c);
 749                         }
 750
 751                         c = filehandle.get();
 752 //k = c;
 753         //cout << " here after get " << k << endl;
 754                         if(c == ';') { return 0; }
 755                         if(c == ')') { filehandle.putback(c); }
 756         //k = c;
 757 //cout << k << endl;
 758
 759                 }
 760                 return 0;
 761         }
 762         catch(exception& e) {
 763                 errorOut(e, "Tree", "readTreeString");
 764                 exit(1);
 765         }
 766 }
 767
 768 /*******************************************************/
 769
 770 /*******************************************************/
 771