16 #include "../base/array.h" 17 #include "../base/vector.h" 23 template <
int NUM_SYMBOLS=128,
typename STOP_TYPE=u
int8_t>
29 tDFA(
size_t num_states=0) : transitions(num_states), is_stop(num_states, 0) {
30 for (
auto & t : transitions) t.fill(-1);
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);
51 return transitions[from];
59 transitions[from][sym] = (int) to;
65 is_stop[state] = stop_val;
72 if (stop_val > is_stop[state]) is_stop[state] = stop_val;
76 stop_t GetStop(
int state)
const {
return (state == -1) ? 0 : is_stop[(size_t)state]; }
79 bool IsActive(
int state)
const {
return state != -1; }
82 bool IsStop(
int state)
const {
return (state == -1) ?
false : is_stop[(size_t)state]; }
86 bool IsActive(
size_t state)
const {
return true; }
87 bool IsStop(
size_t state)
const {
return is_stop[state]; }
90 int Next(
int state,
size_t sym)
const {
93 return (state < 0 || sym >= NUM_SYMBOLS) ? -1 : transitions[(size_t)state][sym];
97 int Next(
int state, std::string sym_set)
const {
98 for (
char x : sym_set) state =
Next(state, (
size_t) x);
104 int out =
Next(0, str);
109 void Print(std::ostream & os=std::cout) {
111 for (
size_t i = 0; i <
GetSize(); i++)
if(
IsStop(i)) os <<
" " << i;
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];
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
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'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