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 using namespace std;
  19
  20 //********************************************************************************************************************
  21
  22 inline char deCodeSequence(char code){
  23
  24         if(code == '0')                 {       return 'a';     }       //      this method allows us to go from the int string to a char string;
  25         else if(code == '1')    {       return 'c';     }       //      it's only really useful if we want to print out the tree
  26         else if(code == '2')    {       return 'g';     }
  27         else if(code == '3')    {       return 't';     }
  28         else if(code == '4')    {       return 'n';     }
  29         else                                    {       return '$';     }
  30
  31 }
  32
  33 //********************************************************************************************************************
  34
  35 SuffixNode::SuffixNode(int parent, int start, int end) :
  36                 parentNode(parent),                     //      we store the parent node as an int
  37                 startCharPosition(start),       //      the suffix tree class will hold the sequence that the startCharPosition and
  38                 endCharPosition(end)            //      endCharPosition indices correspond to
  39                 {       /*      do nothing      */                      }
  40
  41
  42 void SuffixNode::setChildren(char, int)                 {       /*      do nothing      */                      }       //      there's no children in a leaf
  43 int SuffixNode::getNumChildren()                                {       return 0;                                       }       //      ditto
  44 void SuffixNode::eraseChild(char)                               {       /*      do nothing      */                      }       //      ditto
  45 int SuffixNode::getChild(char)                                  {       return -1;                                      }       //      ditto
  46 void SuffixNode::setSuffixNode(int)                             {       /*      do nothing      */                      }       //      there's no suffix node in a leaf
  47 int SuffixNode::getSuffixNode()                                 {       return -1;                                      }       //      ditto
  48 int SuffixNode::getParentNode()                                 {       return parentNode;                      }
  49 void SuffixNode::setParentNode(int number)              {       parentNode = number;            }
  50 int SuffixNode::getStartCharPos()                               {       return startCharPosition;       }
  51 void SuffixNode::setStartCharPos(int start)             {       startCharPosition = start;      }
  52 int SuffixNode::getEndCharPos()                                 {       return endCharPosition;         }
  53
  54 //********************************************************************************************************************
  55
  56 SuffixLeaf::SuffixLeaf(int parent, int start, int end) : SuffixNode(parent, start, end) {       /*      do nothing      */      }
  57
  58
  59 void SuffixLeaf::print(string sequence, int nodeNumber){
  60
  61         cout << this << '\t' << parentNode << '\t' << nodeNumber << '\t' <<
  62         -1 << '\t' << startCharPosition << '\t' << endCharPosition << '\t';
  63
  64         cout << '\'';
  65         for(int i=startCharPosition;i<=endCharPosition;i++){
  66                 cout << deCodeSequence(sequence[i]);
  67         }
  68         cout << '\'' << endl;
  69 }
  70
  71 //********************************************************************************************************************
  72
  73 SuffixBranch::SuffixBranch(int parent, int start, int end) : SuffixNode(parent, start, end), suffixNode(-1){
  74                 childNodes.assign(6, -1);
  75 }
  76
  77 void SuffixBranch::print(string sequence, int nodeNumber){                                              //      this method is different that than
  78         cout << this << '\t' << parentNode << '\t' << nodeNumber << '\t' <<                     //      of a leaf because it prints out a
  79         suffixNode << '\t' << startCharPosition << '\t' << endCharPosition << '\t';     //      value for the suffix node
  80
  81         cout << '\'';
  82         for(int i=startCharPosition;i<=endCharPosition;i++){
  83                 cout << deCodeSequence(sequence[i]);
  84         }
  85         cout << '\'' << endl;
  86 }
  87
  88 //      we can access the children by subtracting '0' from the the char value from the string, the difference is an int
  89 //      value and the index we need to access.
  90 void SuffixBranch::eraseChild(char base)        {       childNodes[base - '0'] = -1;    }       //to erase set the child index to -1
  91 void SuffixBranch::setChildren(char base, int nodeIndex){       childNodes[base - '0'] = nodeIndex;     }
  92 void SuffixBranch::setSuffixNode(int nodeIndex){        suffixNode = nodeIndex;         }
  93 int SuffixBranch::getSuffixNode()                       {       return suffixNode;                              }
  94 int SuffixBranch::getChild(char base)           {       return childNodes[base - '0'];  }
  95
  96 //********************************************************************************************************************