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         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);
  37         int getParentNode();
  38         void setParentNode(int);
  39         int getStartCharPos();
  40         void setStartCharPos(int start);
  41         int getEndCharPos();
  42
  43 protected:
  44         int parentNode;
  45         int startCharPosition;
  46         int endCharPosition;
  47         MothurOut* m;
  48 };
  49
  50 //********************************************************************************************************************
  51
  52 class SuffixLeaf : public SuffixNode {  //      most of the methods are already set in the parent class
  53
  54 public:
  55         SuffixLeaf(int, int, int);              //      we just need to define a constructor and
  56         ~SuffixLeaf() {}
  57         void print(string, int);                //      print method
  58 };
  59
  60 //********************************************************************************************************************
  61
  62 class SuffixBranch : public SuffixNode {
  63
  64 public:
  65         SuffixBranch(int, int, int);
  66         SuffixBranch(const SuffixBranch& sb) : suffixNode(sb.suffixNode), childNodes(sb.childNodes), SuffixNode(sb.parentNode, sb.startCharPosition, sb.endCharPosition) {}
  67         ~SuffixBranch() {}
  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
  74
  75 private:
  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
  79
  80 //********************************************************************************************************************
  81
  82 #endif