Empirical
DFA.h
Go to the documentation of this file.
1 
11 #ifndef EMP_DFA_H
12 #define EMP_DFA_H
13 
14 #include <string>
15 
16 #include "../base/array.h"
17 #include "../base/vector.h"
18 
19 #include "string_utils.h"
20 
21 namespace emp {
22 
23  template <int NUM_SYMBOLS=128, typename STOP_TYPE=uint8_t>
24  class tDFA {
25  private:
27  emp::vector< STOP_TYPE > is_stop; // 0=not stop; other values for STOP return value.
28  public:
29  tDFA(size_t num_states=0) : transitions(num_states), is_stop(num_states, 0) {
30  for (auto & t : transitions) t.fill(-1);
31  }
32  tDFA(const tDFA<NUM_SYMBOLS, STOP_TYPE> &) = default;
33  ~tDFA() { ; }
35 
36  using stop_t = STOP_TYPE;
37 
39  size_t GetSize() const { return transitions.size(); }
40 
42  void Resize(size_t new_size) {
43  auto old_size = transitions.size();
44  transitions.resize(new_size);
45  is_stop.resize(new_size, 0);
46  for (auto i = old_size; i < transitions.size(); i++) transitions[i].fill(-1);
47  }
48 
50  const emp::array<int, NUM_SYMBOLS> & GetTransitions(size_t from) const {
51  return transitions[from];
52  }
53 
55  void SetTransition(size_t from, size_t to, size_t sym) {
56  emp_assert(from < transitions.size());
57  emp_assert(to < transitions.size());
58  emp_assert(sym < NUM_SYMBOLS);
59  transitions[from][sym] = (int) to;
60  }
61 
63  void SetStop(size_t state, stop_t stop_val=1) {
64  emp_assert(state < transitions.size());
65  is_stop[state] = stop_val;
66  }
67 
69  void AddStop(size_t state, stop_t stop_val=1) {
70  emp_assert(state < transitions.size());
71  // If we are given a stop value and its higher than our previous stop, use it!
72  if (stop_val > is_stop[state]) is_stop[state] = stop_val;
73  }
74 
76  stop_t GetStop(int state) const { return (state == -1) ? 0 : is_stop[(size_t)state]; }
77 
79  bool IsActive(int state) const { return state != -1; }
80 
82  bool IsStop(int state) const { return (state == -1) ? false : is_stop[(size_t)state]; }
83 
84  // If a size_t is passed in, it can't be -1...
85  stop_t GetStop(size_t state) const { return is_stop[state]; }
86  bool IsActive(size_t state) const { return true; }
87  bool IsStop(size_t state) const { return is_stop[state]; }
88 
90  int Next(int state, size_t sym) const {
91  emp_assert(state >= -1 && state < (int) transitions.size());
92  // emp_assert(sym >= 0 && sym < NUM_SYMBOLS, sym, (char) sym);
93  return (state < 0 || sym >= NUM_SYMBOLS) ? -1 : transitions[(size_t)state][sym];
94  }
95 
97  int Next(int state, std::string sym_set) const {
98  for (char x : sym_set) state = Next(state, (size_t) x);
99  return state;
100  }
101 
103  stop_t Test(const std::string & str) const {
104  int out = Next(0, str);
105  return GetStop(out);
106  }
107 
109  void Print(std::ostream & os=std::cout) {
110  os << "Num states = " << GetSize() << std::endl << "Stop IDs:";
111  for (size_t i = 0; i < GetSize(); i++) if(IsStop(i)) os << " " << i;
112  os << std::endl;
113 
114  for (size_t i = 0; i < transitions.size(); i++) {
115  os << " " << i << " ->";
116  for (size_t s = 0; s < NUM_SYMBOLS; s++) {
117  if (transitions[i][s] == -1) continue;
118  os << " " << to_literal((char) s) << ":" << transitions[i][s];
119  }
120  if (IsStop(i)) os << " [STOP=" << ((int) GetStop(i)) << "]";
121  os << std::endl;
122  }
123 
124  }
125 
126  };
127 
130 
131 }
132 
133 #endif
Definition: array.h:42
const emp::array< int, NUM_SYMBOLS > & GetTransitions(size_t from) const
Return an array of all transitions associated with a specified state.
Definition: DFA.h:50
stop_t GetStop(size_t state) const
Definition: DFA.h:85
stop_t Test(const std::string &str) const
Determine if an entire series of symbols is valid.
Definition: DFA.h:103
int Next(int state, size_t sym) const
Return the new state after a symbol occurs.
Definition: DFA.h:90
int Next(int state, std::string sym_set) const
Return the new state after a series of symbols.
Definition: DFA.h:97
Definition: DFA.h:24
void SetStop(size_t state, stop_t stop_val=1)
Set the stop value (no matter what it currently is)
Definition: DFA.h:63
void Print(std::ostream &os=std::cout)
Print details about this DFA.
Definition: DFA.h:109
bool IsStop(int state) const
Test if a state has a stop.
Definition: DFA.h:82
Simple functions to manipulate strings.
bool IsStop(size_t state) const
Definition: DFA.h:87
size_t size() const
Definition: vector.h:151
bool IsActive(int state) const
Test if a state is still valid.
Definition: DFA.h:79
static const PrintStr endl("<br>")
Pre-define emp::endl to insert a "<br>" and thus acting like a newline.
std::string to_literal(const LIT_TYPE &value)
Take a value and convert it to a C++-style literal.
Definition: string_utils.h:99
size_t GetSize() const
How many states is this DFA using?
Definition: DFA.h:39
uint8_t stop_t
Definition: DFA.h:36
void resize(size_t new_size)
Definition: vector.h:161
void Resize(size_t new_size)
Add Additional empty states.
Definition: DFA.h:42
If we are in emscripten, make sure to include the header.
Definition: array.h:37
void AddStop(size_t state, stop_t stop_val=1)
Set the stop value only if it&#39;s higher than the current stop value.
Definition: DFA.h:69
Build a debug wrapper emp::vector around std::vector.
Definition: vector.h:42
~tDFA()
Definition: DFA.h:33
#define emp_assert(...)
Definition: assert.h:199
bool IsActive(size_t state) const
Definition: DFA.h:86
void SetTransition(size_t from, size_t to, size_t sym)
Add a specific transition associated with an input symbol.
Definition: DFA.h:55
tDFA< NUM_SYMBOLS, STOP_TYPE > & operator=(const tDFA< NUM_SYMBOLS, STOP_TYPE > &)=default
tDFA(size_t num_states=0)
Definition: DFA.h:29
stop_t GetStop(int state) const
Get the stop value associated with a state.
Definition: DFA.h:76