suffixnodes.cpp

   1 /*
   2  *  SuffixNodes.cpp
   3  *
   4  *
   5  *  Created by Pat Schloss on 12/15/08.
   6  *  Copyright 2008 Patrick D. Schloss. All rights reserved.
   7  *
   8  *      There are two types of nodes in a suffix tree as I have implemented it.  First, there are the internal nodes that
   9  *      have children, these are the SuffixBranch objects.  There are also the terminal nodes, which are the suffixBranches.
  10  *  I divided them into two groups to save on memory.  A SuffixTree object will be a vector of SuffixNodes; therefore,
  11  *      the values of parentNode, children nodes, and suffix nodes are stored as ints that correspond to indices in the
  12  *      vector
  13  *
  14  */
  15
  16 #include "suffixnodes.hpp"
  17
  18
  19 //********************************************************************************************************************
  20
  21 inline char deCodeSequence(char code){
  22
  23         if(code == '0')                 {       return 'a';     }       //      this method allows us to go from the int string to a char string;
  24         else if(code == '1')    {       return 'c';     }       //      it's only really useful if we want to print out the tree
  25         else if(code == '2')    {       return 'g';     }
  26         else if(code == '3')    {       return 't';     }
  27         else if(code == '4')    {       return 'n';     }
  28         else                                    {       return '$';     }
  29
  30 }
  31
  32 //********************************************************************************************************************
  33
  34 SuffixNode::SuffixNode(int parent, int start, int end) :
  35                 parentNode(parent),                     //      we store the parent node as an int
  36                 startCharPosition(start),       //      the suffix tree class will hold the sequence that the startCharPosition and
  37                 endCharPosition(end)            //      endCharPosition indices correspond to
  38                 {       /*      do nothing      */              m = MothurOut::getInstance();   }
  39
  40
  41 void SuffixNode::setChildren(char, int)                 {       /*      do nothing      */                      }       //      there's no children in a leaf
  42 int SuffixNode::getNumChildren()                                {       return 0;                                       }       //      ditto
  43 void SuffixNode::eraseChild(char)                               {       /*      do nothing      */                      }       //      ditto
  44 int SuffixNode::getChild(char)                                  {       return -1;                                      }       //      ditto
  45 void SuffixNode::setSuffixNode(int)                             {       /*      do nothing      */                      }       //      there's no suffix node in a leaf
  46 int SuffixNode::getSuffixNode()                                 {       return -1;                                      }       //      ditto
  47 int SuffixNode::getParentNode()                                 {       return parentNode;                      }
  48 void SuffixNode::setParentNode(int number)              {       parentNode = number;            }
  49 int SuffixNode::getStartCharPos()                               {       return startCharPosition;       }
  50 void SuffixNode::setStartCharPos(int start)             {       startCharPosition = start;      }
  51 int SuffixNode::getEndCharPos()                                 {       return endCharPosition;         }
  52
  53 //********************************************************************************************************************
  54
  55 SuffixLeaf::SuffixLeaf(int parent, int start, int end) : SuffixNode(parent, start, end) {       /*      do nothing      */      }
  56
  57
  58 void SuffixLeaf::print(string sequence, int nodeNumber){
  59
  60         m->mothurOut(toString(this) + "\t" + toString(parentNode) + "\t" + toString(nodeNumber) + "\t" +
  61         toString(-1) + "\t" + toString(startCharPosition) + "\t" + toString(endCharPosition) + "\t");
  62
  63         m->mothurOut("/");
  64         for(int i=startCharPosition;i<=endCharPosition;i++){
  65                 m->mothurOut(toString(deCodeSequence(sequence[i])));
  66         }
  67         m->mothurOut("/");  m->mothurOutEndLine();
  68 }
  69
  70 //********************************************************************************************************************
  71
  72 SuffixBranch::SuffixBranch(int parent, int start, int end) : SuffixNode(parent, start, end), suffixNode(-1){
  73                 childNodes.assign(6, -1);
  74 }
  75
  76 void SuffixBranch::print(string sequence, int nodeNumber){                                              //      this method is different that than
  77         m->mothurOut(toString(this) + "\t" + toString(parentNode) + "\t" + toString(nodeNumber) + "\t" +                //      of a leaf because it prints out a
  78         toString(suffixNode) + "\t" + toString(startCharPosition) + "\t" + toString(endCharPosition) + "\t");  //       value for the suffix node
  79
  80         m->mothurOut("/");
  81         for(int i=startCharPosition;i<=endCharPosition;i++){
  82                 m->mothurOut(toString(deCodeSequence(sequence[i])));
  83         }
  84         m->mothurOut("/");  m->mothurOutEndLine();
  85 }
  86
  87 //      we can access the children by subtracting '0' from the the char value from the string, the difference is an int
  88 //      value and the index we need to access.
  89 void SuffixBranch::eraseChild(char base)        {       childNodes[base - '0'] = -1;    }       //to erase set the child index to -1
  90 void SuffixBranch::setChildren(char base, int nodeIndex){       childNodes[base - '0'] = nodeIndex;     }
  91 void SuffixBranch::setSuffixNode(int nodeIndex){        suffixNode = nodeIndex;         }
  92 int SuffixBranch::getSuffixNode()                       {       return suffixNode;                              }
  93 int SuffixBranch::getChild(char base)           {       return childNodes[base - '0'];  }
  94
  95 //********************************************************************************************************************