5 * Created by Pat Schloss on 12/15/08.
6 * Copyright 2008 Patrick D. Schloss. All rights reserved.
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
16 #include "suffixnodes.hpp"
20 //********************************************************************************************************************
22 inline char deCodeSequence(char code){
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'; }
33 //********************************************************************************************************************
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
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; }
54 //********************************************************************************************************************
56 SuffixLeaf::SuffixLeaf(int parent, int start, int end) : SuffixNode(parent, start, end) { /* do nothing */ }
59 void SuffixLeaf::print(string sequence, int nodeNumber){
61 cout << this << '\t' << parentNode << '\t' << nodeNumber << '\t' <<
62 -1 << '\t' << startCharPosition << '\t' << endCharPosition << '\t';
65 for(int i=startCharPosition;i<=endCharPosition;i++){
66 cout << deCodeSequence(sequence[i]);
71 //********************************************************************************************************************
73 SuffixBranch::SuffixBranch(int parent, int start, int end) : SuffixNode(parent, start, end), suffixNode(-1){
74 childNodes.assign(6, -1);
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
82 for(int i=startCharPosition;i<=endCharPosition;i++){
83 cout << deCodeSequence(sequence[i]);
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']; }
96 //********************************************************************************************************************