src/algorithm.h

   1 #ifndef AHO_ALGORITHM_H\r
   2 #define AHO_ALGORITHM_H\r
   3 \r
   4 #include <iostream>\r
   5 #include <vector>\r
   6 #include <string>\r
   7 \r
   8 #include "typedef.h"\r
   9 #include "trie.h"\r
  10 \r
  11 /*\r
  12 At each step, the current node is extended by finding its daughter,\r
  13 and if that doesn't exist, finding its suffix's daughter, \r
  14 and if that doesn't work, finding its suffix's suffix's daughter,\r
  15 finally ending in the root node if nothing's seen before.\r
  16 */\r
  17 namespace aho {\r
  18         \r
  19 //      class result {\r
  20 //      private:\r
  21 //      protected:\r
  22 //      public:\r
  23 //              tstring rslt;\r
  24 //              int position;\r
  25 //      };\r
  26 \r
  27 class algorithm {\r
  28         private:\r
  29         protected:\r
  30                 class aho::trie * trie;\r
  31 \r
  32                 std::vector<tstring> patterns;\r
  33                 tstring subject;\r
  34                 tstring letters;\r
  35 \r
  36                 std::vector<class aho::trie *> list;\r
  37 \r
  38                 void add_patterns_to_trie();\r
  39 \r
  40                 /**\r
  41                  * Sets which nodes in trie, are the searched patterns.\r
  42                  */\r
  43                 void set_patterns_in_trie();\r
  44 \r
  45                 /**\r
  46                  * Sets node list.\r
  47                  */\r
  48                 void set_nodes_list();\r
  49 \r
  50                 /**\r
  51                  * Sets suffix links for each pattern in trie.\r
  52                  */\r
  53                 void set_suffix_link();\r
  54 \r
  55                 /**\r
  56                  * Checks if node is a searched pattern.\r
  57                  */\r
  58                 virtual bool is_pattern(class aho::trie * node) {\r
  59                         return node->is_pattern();\r
  60                 }\r
  61 \r
  62                 bool is_on_nodes_list(class aho::trie * node);\r
  63                 \r
  64                 /**\r
  65                  * Gets node by its value\r
  66                  */\r
  67                 class aho::trie * get_node(tstring value) {\r
  68                         return this->trie->get_child(value, true);\r
  69                 }\r
  70 \r
  71                 /**\r
  72                  * Saves search results\r
  73                  */\r
  74                 virtual void save_result(tstring search, uint position) {\r
  75                         printf("%s: %d\n", search.c_str(), position);\r
  76                 }\r
  77         public:\r
  78                 /**\r
  79                  * Algorithm constructor. Initializes variables.\r
  80                  */\r
  81                 algorithm() : trie(new aho::trie(TXT(""))) {\r
  82                 }\r
  83 \r
  84                 /**\r
  85                  * Algorithm destructor.\r
  86                  */\r
  87                 ~algorithm() {\r
  88                         if(this->trie != NULL) {\r
  89                                 delete this->trie;\r
  90                         }\r
  91                 }\r
  92                 void add_search_pattern(tstring pattern);\r
  93 \r
  94                 /**\r
  95                  * Sets subject text in which patterns will be searched.\r
  96                  */\r
  97                 void set_search_subject(tstring subject) {\r
  98                         this->subject = subject;\r
  99                 }\r
 100 \r
 101                 void generate_trie();\r
 102                 void parse();\r
 103         };\r
 104 };\r
 105 \r
 106 #endif