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 #include "mothurout.h"
  21
  22 //********************************************************************************************************************
  23
  24 class SuffixNode {
  25
  26 public:
  27         SuffixNode(int, int, int);
  28         virtual ~SuffixNode() {}
  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         MothurOut* m;
  47 };
  48
  49 //********************************************************************************************************************
  50
  51 class SuffixLeaf : public SuffixNode {  //      most of the methods are already set in the parent class
  52
  53 public:
  54         SuffixLeaf(int, int, int);              //      we just need to define a constructor and
  55         ~SuffixLeaf() {}
  56         void print(string, int);                //      print method
  57 };
  58
  59 //********************************************************************************************************************
  60
  61 class SuffixBranch : public SuffixNode {
  62
  63 public:
  64         SuffixBranch(int, int, int);
  65         ~SuffixBranch() {}
  66         void print(string, int);                //      need a special method for printing the node because there are children
  67         void eraseChild(char);                  //      need a special method for erasing the children
  68         void setChildren(char, int);    //      need a special method for setting children
  69         void setSuffixNode(int);                //      need a special method for setting the suffix node
  70         int getSuffixNode();                    //      need a special method for returning the suffix node
  71         int getChild(char);                             //      need a special method for return children
  72
  73 private:
  74         vector<int> childNodes;                 //      a suffix branch is unique because it has children and a suffixNode.  The
  75         int suffixNode;                                 //      are stored in a vector for super-fast lookup.  If the alphabet were bigger, this
  76 };                                                                      //      might not be practical.  Since we only have 5 possible letters, it makes sense
  77
  78 //********************************************************************************************************************
  79
  80 #endif