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