00001
00002
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef TREE_H_
00027 #define TREE_H_
00028
00029 #include "common.h"
00030
00031 using namespace std;
00032
00033 typedef list<element> elements;
00034 typedef vector<short> nid;
00035
00037
00043 struct Node
00044 {
00045 elements data;
00046 Node *left;
00047 Node *right;
00048 Node *parent;
00049 nid id;
00050 };
00051
00053
00061 struct SuperNode
00062 {
00063 int taxa;
00064 SuperNode *left;
00065 SuperNode *right;
00066 SuperNode *parent;
00067 bool internal;
00068 nid id;
00069 };
00070
00072
00073 void display_node(Node * curr);
00075
00076 void display_SuperNode(SuperNode * curr);
00077
00079
00081 class Tree
00082 {
00083 public:
00085
00087 Tree();
00088
00090
00096 Tree(Node*,int);
00097
00099 ~Tree();
00101
00105 void insert(const elements&,int);
00107
00109 void remove(Node*);
00111
00114 Tree(const Tree &);
00116
00119 elements value() const;
00121
00124 nid Id() const;
00125
00127 void left();
00128 void right();
00129 void parent();
00130 void reset();
00131
00132
00133 void SetCurrent(Node*);
00134
00136 Node* pointer_left() const;
00137 Node* pointer_right() const;
00138 Node* pointer_parent() const;
00139 Node* pointer_current() const;
00140 Node * root() const;
00141
00143 elements peek_left() const;
00144 elements peek_right() const;
00145 elements peek_parent() const;
00146
00148 void DisplayInorder(Node*) const;
00149 void DisplayPreorder(Node*) const;
00150 void DisplayPostorder(Node*) const;
00151
00153 void clear();
00154
00156 bool IsEmpty() const;
00157 bool IsFull() const;
00158
00159 private:
00160 Node* current;
00161 Node* main_root;
00162 Node* CopyTree(Node*,Node*) const;
00163 bool subtree;
00164 };
00165
00167
00169 class SuperTree
00170 {
00171 public:
00172
00174
00176 SuperTree();
00178
00183 SuperTree(SuperNode*,int);
00185
00186 ~SuperTree();
00188
00195 void insert(int, int, nid, bool);
00197
00202 void insert(SuperTree &, SuperTree &);
00204
00208 void remove(SuperNode*);
00210
00211 int value() const;
00213
00214 nid Id() const;
00215
00217 void left();
00218 void right();
00219 void parent();
00220 void reset();
00221
00222
00223 void SetCurrent(SuperNode*);
00225
00228 SuperTree(const SuperTree &);
00229
00231 SuperNode* pointer_left() const;
00232 SuperNode* pointer_right() const;
00233 SuperNode* pointer_parent() const;
00234 SuperNode* pointer_current() const;
00235 SuperNode* root() const;
00236
00238 int peek_left() const;
00239 int peek_right() const;
00240 int peek_parent() const;
00241
00243 void DisplayInorder(SuperNode*) const;
00244 void DisplayPreorder(SuperNode*) const;
00245 void DisplayPostorder(SuperNode*) const;
00246
00247
00251 void Newick(list<string> &, SuperNode*);
00252
00254 void clear();
00255
00256 bool IsEmpty() const;
00257 bool IsFull() const;
00258 bool IsInternal() const;
00259
00260 private:
00261 SuperNode* current;
00262 SuperNode* main_root;
00263 SuperNode* CopyTree(SuperNode*,SuperNode*) const;
00264 SuperNode* CopyTree(SuperNode *, SuperNode *, int) const;
00265 bool subtree;
00266 };
00267
00269
00270 Tree::Tree()
00271 {
00272
00273 main_root = NULL;
00274 current = NULL;
00275 subtree = false;
00276 }
00277
00279
00280 SuperTree::SuperTree()
00281 {
00282
00283 main_root = NULL;
00284 current = NULL;
00285 subtree = false;
00286 }
00287
00289
00299 Tree::Tree(Node* root, int op)
00300 {
00301 if(op == 0)
00302 {
00303 main_root = root;
00304 current = root;
00305 subtree = true;
00306 }
00307 else
00308 {
00309 main_root = CopyTree(root,NULL);
00310 current = main_root;
00311 subtree = false;
00312 }
00313 }
00314
00316
00326 SuperTree::SuperTree(SuperNode* root, int op)
00327 {
00328 if(op == 0)
00329 {
00330 main_root = root;
00331 current = root;
00332 subtree = true;
00333 }
00334 else
00335 {
00336 main_root = CopyTree(root,NULL);
00337 current = main_root;
00338 subtree = false;
00339 }
00340 }
00341
00342 Node* Tree::root() const {
00343 return main_root;
00344 }
00345
00346 Tree::Tree(const Tree & tr) {
00347 main_root = CopyTree(tr.root(), NULL);
00348 }
00349
00350 SuperNode* SuperTree::root() const {
00351 return main_root;
00352 }
00353
00354 SuperTree::SuperTree(const SuperTree & tr) {
00355 main_root = CopyTree(tr.root(), NULL);
00356 }
00357
00359
00366 Node* Tree::CopyTree(Node *root, Node *parent) const
00367 {
00368 if(root == NULL)
00369 return NULL;
00370 Node* tmp = new Node;
00371 tmp->data = root->data;
00372 tmp->parent = parent;
00373 tmp->left = CopyTree(root->left,tmp);
00374 tmp->right = CopyTree(root->right,tmp);
00375 tmp->id = root->id;
00376 return tmp;
00377 }
00378
00380
00387 SuperNode* SuperTree::CopyTree(SuperNode *root, SuperNode *parent) const
00388 {
00389 if(root == NULL)
00390 return NULL;
00391 SuperNode* temp = new SuperNode;
00392 temp->taxa = root->taxa;
00393 temp->parent = parent;
00394 temp->left = CopyTree(root->left,temp);
00395 temp->right = CopyTree(root->right,temp);
00396 temp->id = root->id;
00397 temp->internal = root->internal;
00398 return temp;
00399 }
00400
00402
00409 SuperNode* SuperTree::CopyTree(SuperNode *root, SuperNode *parent, int dummy) const
00410 {
00411 if(root == NULL)
00412 return NULL;
00413 SuperNode* temp = new SuperNode;
00414 temp->taxa = root->taxa;
00415 temp->parent = parent;
00416 temp->left = CopyTree(root->left,temp);
00417 temp->right = CopyTree(root->right,temp);
00418 temp->id.push_back(-1);
00419 temp->internal = root->internal;
00420 return temp;
00421 }
00422
00424
00425 Tree::~Tree()
00426 {
00427 if(!subtree)
00428 clear();
00429 }
00431
00432 SuperTree::~SuperTree()
00433 {
00434 if(!subtree)
00435 clear();
00436 }
00437
00439
00443 void Tree::insert(const elements &item,int pos)
00444 {
00445 assert(!IsFull());
00447 if(main_root == NULL)
00448 {
00449 main_root = new Node;
00450 main_root->data = item;
00451 main_root->left = NULL;
00452 main_root->right = NULL;
00453 main_root->parent = NULL;
00454 main_root->id.push_back(0);
00455 current = main_root;
00456 return;
00457 }
00458
00459 if(pos == 0)
00460 {
00461 if(current->left != NULL)
00462 (current->left)->data = item;
00463 else
00464 {
00465 current->left = new Node;
00466 current->left->data = item;
00467 current->left->left = NULL;
00468 current->left->right = NULL;
00469 current->left->id = current->id;
00470 current->left->id.push_back(1);
00471 current->left->parent = current;
00472 }
00473 }
00474 else
00475 {
00476 if(current->right != NULL)
00477 (current->right)->data = item;
00478 else
00479 {
00480 current->right = new Node;
00481 current->right->data = item;
00482 current->right->left = NULL;
00483 current->right->right = NULL;
00484 current->right->id = current->id;
00485 short temp = current->right->id.back();
00486 temp++;
00487 current->right->id.pop_back();
00488 current->right->id.push_back(temp);
00489 current->right->parent = current;
00490 }
00491 }
00492 }
00493
00495
00501 void SuperTree::insert(int tax, int pos, nid id_, bool is_internal)
00502 {
00503 assert(!IsFull());
00505 if(main_root == NULL)
00506 {
00507 main_root = new SuperNode;
00508 main_root->taxa = 0;
00509 main_root->left = NULL;
00510 main_root->right = NULL;
00511 main_root->parent = NULL;
00512 main_root->id = id_;
00513 main_root->internal = 1;
00514 current = main_root;
00515 return;
00516 }
00517
00518 if(pos == 0)
00519 {
00520 if(current->left != NULL) {
00521 (current->left)->taxa = tax;
00522 cout << "we shouldn't get in here!!!" << endl;
00523 }
00524 else
00525 {
00526 current->left = new SuperNode;
00527 current->left->taxa = tax;
00528 current->left->left = NULL;
00529 current->left->right = NULL;
00530 current->left->id.push_back(-1);
00531 current->left->parent = current;
00532 current->left->internal = is_internal;
00533 }
00534 }
00535 else if(pos == 1)
00536 {
00537 if(current->right != NULL) {
00538 (current->right)->taxa = tax;
00539 cout << "we shouldn't get in here, either!" << endl;
00540 }
00541 else
00542 {
00543 current->right = new SuperNode;
00544 current->right->taxa = tax;
00545 current->right->left = NULL;
00546 current->right->right = NULL;
00547 current->right->id.push_back(-1);
00548 current->right->parent = current;
00549 current->right->internal = is_internal;
00550 }
00551 }
00552 else {
00553 SuperNode * temp_left = current->parent->left;
00554 SuperNode * temp_right = current->parent->right;
00555 current->parent = new SuperNode;
00556 current->parent->taxa = 0;
00557 current->parent->internal = 1;
00558 current->parent->left = temp_left;
00559 current->parent->right = temp_right;
00560 current->parent->internal = is_internal;
00561 current->parent->id = id_;
00562 current->parent->id.pop_back();
00563 current = current;
00564 }
00565 }
00566
00568
00573 void SuperTree::insert(SuperTree & left, SuperTree & right)
00574 {
00575 vector<short> id_ = left.root()->id;
00576 assert(!IsFull());
00578 if(main_root == NULL)
00579 {
00580 main_root = new SuperNode;
00581 main_root->taxa = 0;
00582 main_root->left = CopyTree(left.root(), main_root, 0);
00583 main_root->right = CopyTree(right.root(), main_root, 0);
00584 main_root->parent = NULL;
00585 main_root->id = id_;
00586 main_root->internal = 1;
00587 main_root->left->id.clear();
00588 main_root->left->id.push_back(-1);
00589 main_root->right->id.clear();
00590 main_root->right->id.push_back(-1);
00591 current = main_root;
00592 return;
00593 }
00594 }
00595
00597
00598 elements Tree::value() const
00599 {
00600 return current->data;
00601 }
00602
00604
00605 int SuperTree::value() const
00606 {
00607 return current->taxa;
00608 }
00609
00611
00612 nid Tree::Id() const
00613 {
00614 return current->id;
00615 }
00616
00618
00619 nid SuperTree::Id() const
00620 {
00621 return current->id;
00622 }
00623
00625
00626 void Tree::left()
00627 {
00628 current = current->left;
00629 }
00630
00631 void Tree::right()
00632 {
00633 current = current->right;
00634 }
00635
00636 void Tree::parent()
00637 {
00638 current = current->parent;
00639 }
00640
00641 void Tree::reset()
00642 {
00643 current = main_root;
00644 }
00645
00646 void Tree::SetCurrent(Node* root)
00647 {
00648 current = root;
00649 }
00650
00652 void SuperTree::left()
00653 {
00654 current = current->left;
00655 }
00656
00657 void SuperTree::right()
00658 {
00659 current = current->right;
00660 }
00661
00662 void SuperTree::parent()
00663 {
00664 current = current->parent;
00665 }
00666
00667 void SuperTree::reset()
00668 {
00669 current = main_root;
00670 }
00671
00672 void SuperTree::SetCurrent(SuperNode* root)
00673 {
00674 current = root;
00675 }
00676
00678
00679 Node* Tree::pointer_left() const
00680 {
00681 return current->left;
00682 }
00683
00684 Node* Tree::pointer_right() const
00685 {
00686 return current->right;
00687 }
00688
00689 Node* Tree::pointer_parent() const
00690 {
00691 return current->parent;
00692 }
00693
00694 Node* Tree::pointer_current() const
00695 {
00696 return current;
00697 }
00698
00700 SuperNode* SuperTree::pointer_left() const
00701 {
00702 return current->left;
00703 }
00704
00705 SuperNode* SuperTree::pointer_right() const
00706 {
00707 return current->right;
00708 }
00709
00710 SuperNode* SuperTree::pointer_parent() const
00711 {
00712 return current->parent;
00713 }
00714
00715 SuperNode* SuperTree::pointer_current() const
00716 {
00717 return current;
00718 }
00719
00720
00722
00723 elements Tree::peek_left() const
00724 {
00725 assert(current->left != NULL);
00726 return current->left->data;
00727 }
00728
00729 elements Tree::peek_right() const
00730 {
00731 assert(current->right != NULL);
00732 return current->right->data;
00733 }
00734
00735 elements Tree::peek_parent() const
00736 {
00737 assert(current->parent != NULL);
00738 return current->parent->data;
00739 }
00740
00742
00743 int SuperTree::peek_left() const
00744 {
00745 assert(current->left != NULL);
00746 return current->left->taxa;
00747 }
00748
00749 int SuperTree::peek_right() const
00750 {
00751 assert(current->right != NULL);
00752 return current->right->taxa;
00753 }
00754
00755 int SuperTree::peek_parent() const
00756 {
00757 assert(current->parent != NULL);
00758 return current->parent->taxa;
00759 }
00760
00762
00763 void Tree::DisplayInorder(Node* root) const
00764 {
00765 if (root == NULL)
00766 return;
00767
00768 DisplayInorder(root->left);
00769 display_node(root);
00770 DisplayInorder(root->right);
00771 }
00772
00773 void Tree::DisplayPreorder(Node* root) const
00774 {
00775 if (root == NULL)
00776 return;
00777
00778 display_node(root);
00779 DisplayPreorder(root->left);
00780 DisplayPreorder(root->right);
00781 }
00782
00783 void Tree::DisplayPostorder(Node* root) const
00784 {
00785 if (root == NULL)
00786 return;
00787
00788 DisplayPostorder(root->left);
00789 DisplayPostorder(root->right);
00790 display_node(root);
00791 }
00792
00794 void SuperTree::DisplayInorder(SuperNode* root) const
00795 {
00796 if (root == NULL)
00797 return;
00798
00799 DisplayInorder(root->left);
00800 display_SuperNode(root);
00801 DisplayInorder(root->right);
00802 }
00803
00804 void SuperTree::DisplayPreorder(SuperNode* root) const
00805 {
00806 if (root == NULL)
00807 return;
00808
00809 display_SuperNode(root);
00810 DisplayPreorder(root->left);
00811 DisplayPreorder(root->right);
00812 }
00813
00814 void SuperTree::DisplayPostorder(SuperNode* root) const
00815 {
00816 if (root == NULL )
00817 return;
00818
00819 DisplayPostorder(root->left);
00820 DisplayPostorder(root->right);
00821 display_SuperNode(root);
00822 }
00823
00825 void SuperTree::Newick(list<string> & newick_, SuperNode * curr ) {
00826
00827 if ( curr == NULL )
00828 return;
00829
00830 if ( curr->internal == 0 ) {
00831 int temp = curr->taxa;
00832 stringstream ss1;
00833 string temp_taxa;
00834 ss1 << temp;
00835 ss1 >> temp_taxa;
00836 newick_.push_back(temp_taxa);
00837 }
00838 else {
00839 newick_.push_back("(");
00840 Newick(newick_, curr->left);
00841 newick_.push_back(",");
00842 Newick(newick_, curr->right);
00843 newick_.push_back(")");
00844 }
00845
00846
00847 }
00848
00850 void Tree::clear()
00851 {
00852 remove(main_root);
00853 main_root = NULL;
00854 current = NULL;
00855 }
00856
00857 void Tree::remove(Node* root)
00858 {
00859 if(root == NULL)
00860 return;
00861 remove(root->left);
00862 remove(root->right);
00863 if(root->parent == NULL)
00864 main_root = NULL;
00865 else
00866 {
00867 if(root->parent->left == root)
00868 root->parent->left = NULL;
00869 else
00870 root->parent->right = NULL;
00871 }
00872 current = root->parent;
00873 delete root;
00874 }
00875
00877 void SuperTree::clear()
00878 {
00879 remove(main_root);
00880 main_root = NULL;
00881 current = NULL;
00882 }
00883
00884 void SuperTree::remove(SuperNode* root)
00885 {
00886 if(root == NULL)
00887 return;
00888 remove(root->left);
00889 remove(root->right);
00890 if(root->parent == NULL)
00891 main_root = NULL;
00892 else
00893 {
00894 if(root->parent->left == root)
00895 root->parent->left = NULL;
00896 else
00897 root->parent->right = NULL;
00898 }
00899 current = root->parent;
00900 delete root;
00901 }
00902
00904 bool Tree::IsEmpty() const
00905 {
00906 return (main_root == NULL);
00907 }
00908
00910 bool SuperTree::IsEmpty() const
00911 {
00912 return (main_root == NULL);
00913 }
00914
00916 bool Tree::IsFull() const
00917 {
00918 Node *tmp = new Node;
00919 if(tmp == NULL)
00920 return true;
00921 else
00922 {
00923 delete tmp;
00924 return false;
00925 }
00926 }
00927
00929 void display_node(Node * curr) {
00930 cout << "outputting node... " << endl;
00931 cout << "tree id: |";
00932 nid temp = curr->id;
00933 for (unsigned int i = 0; i < temp.size(); ++i)
00934 cout << temp[i] << " | ";
00935 cout << endl;
00936 elements temp_data = curr->data;
00937 cout << "clustered elements: " << endl;
00938 elements::iterator te_itr = temp_data.begin();
00939 while ( te_itr != temp_data.end() ) {
00940 cout << (*te_itr).get_taxa() << endl;
00941 ++te_itr;
00942 }
00943 }
00944
00946 bool SuperTree::IsFull() const
00947 {
00948 SuperNode *tmp = new SuperNode;
00949 if(tmp == NULL)
00950 return true;
00951 else
00952 {
00953 delete tmp;
00954 return false;
00955 }
00956 }
00957
00959 void display_SuperNode(SuperNode * curr) {
00960 cout << "outputting super node... " << endl;
00961 cout << "tree id: |";
00962 nid temp = curr->id;
00963 for (unsigned int i = 0; i < temp.size(); ++i)
00964 cout << temp[i] << " | ";
00965 cout << endl;
00966 if ( curr->internal == 1 ) {
00967 cout << "internal node" << endl;
00968 }
00969 else {
00970 cout << "taxa " << curr->taxa << endl;
00971 }
00972 cout << endl;
00973 }
00974
00976
00979 void show_leaves(Node * curr) {
00980 if ( curr->left != NULL ) {
00981 show_leaves(curr->left);
00982 if ( curr->right != NULL )
00983 show_leaves(curr->right);
00984
00985 }
00986 else {
00987 display_node(curr);
00988
00989 if ( curr->right != NULL )
00990 show_leaves(curr->right);
00991 }
00992 }
00993
00995
00998 void find_leaves(list<Node *> & leaves, Node * curr) {
00999 if ( curr->left != NULL ) {
01000 find_leaves(leaves, curr->left);
01001 if ( curr->right != NULL )
01002 find_leaves(leaves, curr->right);
01003
01004 }
01005 else {
01006 leaves.push_back(curr);
01007 if ( curr->right != NULL )
01008 find_leaves(leaves, curr->right);
01009 }
01010 }
01011
01013
01016 void merge_trees(list<SuperTree> & many_trees) {
01017 if ( many_trees.size() == 1 )
01018 return;
01019 SuperTree left = many_trees.front();
01020 many_trees.pop_front();
01021 SuperTree right = many_trees.front();
01022 many_trees.pop_front();
01023
01025 SuperTree new_tree;
01026 new_tree.insert(left, right);
01027 if ( DISPLAY ) {
01028 cout << "displaying the NEWLY CREATED TREE." << endl;
01029 new_tree.DisplayInorder(new_tree.root());
01030 }
01031 many_trees.push_front(new_tree);
01032 if ( many_trees.size() > 1 )
01033 merge_trees(many_trees);
01034 else
01035 return;
01036 }
01037
01039 int LeafCount(Node* root)
01040 {
01041 if(root == NULL)
01042 return 0;
01043 if((root->left == NULL) && (root->right == NULL))
01044 return 1;
01045 return LeafCount(root->left) + LeafCount(root->right);
01046 }
01047
01049 int NodeCount(Node* root)
01050 {
01051 if(root == NULL)
01052 return 0;
01053 else
01054 return 1 + NodeCount(root->left) + NodeCount(root->right);
01055 }
01056
01057 #endif