tree.h

00001 
00002 
00006 //(c) 2006 Suzanne Matthews
00007 /*
00008 This file is part of the RaqApproach software package.
00009 
00010     RaqApproach is free software; you can redistribute it and/or modify
00011     it under the terms of the GNU General Public License as published by
00012     the Free Software Foundation; either version 2 of the License, or
00013     (at your option) any later version.
00014 
00015     RaqApproach is distributed in the hope that it will be useful,
00016     but WITHOUT ANY WARRANTY; without even the implied warranty of
00017     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018     GNU General Public License for more details.
00019 
00020     You should have received a copy of the GNU General Public License
00021     along with RaqApproach; if not, write to the Free Software
00022     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00023 */
00024 
00025 //basic tree class based off of template found on library.thinkquest.org
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; //identification of the node
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*); //delete node and its subtree
00111 
00114    Tree(const Tree &);
00116 
00119    elements value() const;
00121 
00124    nid Id() const; //display level of the current node
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; //display level of the current node
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    //create a root node with no value
00273    main_root = NULL;
00274    current = NULL;
00275    subtree = false;
00276 }
00277 
00279 
00280 SuperTree::SuperTree()
00281 {
00282    //create a root node with no value
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) //insert as child of current 0=left 1=right. if item already exists, replace it
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; //<! output tree (optional)
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

Generated on Wed Jul 26 22:18:15 2006 for RaqApproach by  doxygen 1.4.7