8 * Created by Pat Schloss on 12/15/08.
9 * Copyright 2008 Patrick D. Schloss. All rights reserved.
11 * There are two types of nodes in a suffix tree as I have implemented it. First, there are the internal nodes that
12 * have children, these are the SuffixBranch objects. There are also the terminal nodes, which are the suffixBranches.
13 * I divided them into two groups to save on memory. A SuffixTree object will be a vector of SuffixNodes; therefore,
14 * the values of parentNode, children nodes, and suffix nodes are stored as ints that correspond to indices in the
20 #include "mothurout.h"
22 //********************************************************************************************************************
27 SuffixNode(int, int, int);
28 SuffixNode(const SuffixNode& sn) : parentNode(sn.parentNode), startCharPosition(sn.startCharPosition), endCharPosition(sn.endCharPosition) {m = MothurOut::getInstance();}
29 virtual ~SuffixNode() {}
30 virtual void print(string, int) = 0;
31 virtual void setChildren(char, int);
32 virtual int getNumChildren();
33 virtual void eraseChild(char);
34 virtual void setSuffixNode(int);
35 virtual int getSuffixNode();
36 virtual int getChild(char);
38 void setParentNode(int);
39 int getStartCharPos();
40 void setStartCharPos(int start);
45 int startCharPosition;
50 //********************************************************************************************************************
52 class SuffixLeaf : public SuffixNode { // most of the methods are already set in the parent class
55 SuffixLeaf(int, int, int); // we just need to define a constructor and
57 void print(string, int); // print method
60 //********************************************************************************************************************
62 class SuffixBranch : public SuffixNode {
65 SuffixBranch(int, int, int);
66 SuffixBranch(const SuffixBranch& sb) : suffixNode(sb.suffixNode), childNodes(sb.childNodes), SuffixNode(sb.parentNode, sb.startCharPosition, sb.endCharPosition) {}
68 void print(string, int); // need a special method for printing the node because there are children
69 void eraseChild(char); // need a special method for erasing the children
70 void setChildren(char, int); // need a special method for setting children
71 void setSuffixNode(int); // need a special method for setting the suffix node
72 int getSuffixNode(); // need a special method for returning the suffix node
73 int getChild(char); // need a special method for return children
76 vector<int> childNodes; // a suffix branch is unique because it has children and a suffixNode. The
77 int suffixNode; // are stored in a vector for super-fast lookup. If the alphabet were bigger, this
78 }; // might not be practical. Since we only have 5 possible letters, it makes sense
80 //********************************************************************************************************************