suffixnodes.hpp

   1 #ifndef SUFFIXNODES_H
   2 #define SUFFIXNODES_H
   3
   4 /*
   5  *  SuffixNodes.h
   6  *
   7  *
   8  *  Created by Pat Schloss on 12/15/08.
   9  *  Copyright 2008 Patrick D. Schloss. All rights reserved.
  10  *
  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
  15  *      vector
  16  *
  17  */
  18
  19 #include "mothur.h"
  20
  21 using namespace std;
  22
  23 //********************************************************************************************************************
  24
  25 class SuffixNode {
  26
  27 public:
  28         SuffixNode(int, int, int);
  29         virtual void print(string, int) = 0;
  30         virtual void setChildren(char, int);
  31         virtual int getNumChildren();
  32         virtual void eraseChild(char);
  33         virtual void setSuffixNode(int);
  34         virtual int getSuffixNode();
  35         virtual int getChild(char);
  36         int getParentNode();
  37         void setParentNode(int);
  38         int getStartCharPos();
  39         void setStartCharPos(int start);
  40         int getEndCharPos();
  41
  42 protected:
  43         int parentNode;
  44         int startCharPosition;
  45         int endCharPosition;
  46 };
  47
  48 //********************************************************************************************************************
  49
  50 class SuffixLeaf : public SuffixNode {  //      most of the methods are already set in the parent class
  51
  52 public:
  53         SuffixLeaf(int, int, int);              //      we just need to define a constructor and
  54         void print(string, int);                //      print method
  55 };
  56
  57 //********************************************************************************************************************
  58
  59 class SuffixBranch : public SuffixNode {
  60
  61 public:
  62         SuffixBranch(int, int, int);
  63         void print(string, int);                //      need a special method for printing the node because there are children
  64         void eraseChild(char);                  //      need a special method for erasing the children
  65         void setChildren(char, int);    //      need a special method for setting children
  66         void setSuffixNode(int);                //      need a special method for setting the suffix node
  67         int getSuffixNode();                    //      need a special method for returning the suffix node
  68         int getChild(char);                             //      need a special method for return children
  69
  70 private:
  71         vector<int> childNodes;                 //      a suffix branch is unique because it has children and a suffixNode.  The
  72         int suffixNode;                                 //      are stored in a vector for super-fast lookup.  If the alphabet were bigger, this
  73 };                                                                      //      might not be practical.  Since we only have 5 possible letters, it makes sense
  74
  75 //********************************************************************************************************************
  76
  77 #endif