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