29 #include "../base/vector.h" 36 template <
size_t S=128,
typename STOP_TYPE=u
int8_t>
46 Transition() : symbols() { }
49 std::map<size_t, Transition> trans;
50 std::set<size_t> free_to;
51 std::set<size_t> free_from;
52 State() : trans(), free_to(), free_from() { }
60 tNFA(
size_t num_states=1,
size_t start_state=0)
61 : states(num_states), start(start_state), is_stop(num_states, 0) {
62 if (num_states > start) states[start].free_to.
insert(start);
74 return states[start].free_to;
78 std::set<size_t>
GetNext(
size_t sym,
size_t from_id=0)
const {
79 std::set<size_t> to_set;
80 for (
auto & t : states[from_id].trans) {
81 if (t.second.symbols[sym]) {
82 to_set.insert(t.first);
83 insert(to_set, states[t.first].free_to);
90 std::set<size_t>
GetNext(
size_t sym,
const std::set<size_t> from_set)
const {
91 std::set<size_t> to_set;
92 for (
size_t from_id : from_set) {
93 for (
auto & t : states[from_id].trans) {
94 if (t.second.symbols[sym]) {
95 to_set.insert(t.first);
96 insert(to_set, states[t.first].free_to);
112 for (
size_t id : test_set) {
113 for (
const auto & t : states[
id].trans) {
114 options |= t.second.symbols;
123 is_stop.
resize(new_size, 0);
124 if (new_size > start) states[start].free_to.
insert(start);
135 states[from].trans[to].symbols[sym] =
true;
148 states[from].trans[to].symbols |= sym_set;
157 auto extend_to = states[to].free_to;
158 auto extend_from = states[from].free_from;
160 extend_from.insert(from);
163 for (
auto x : extend_from) {
164 for (
auto y : extend_to) {
165 states[x].free_to.
insert(y);
166 states[y].free_from.
insert(x);
173 template <
typename T=stop_t>
174 void SetStop(
size_t state, T stop_val=1) { is_stop[state] = (
stop_t) stop_val; }
180 bool IsStart(
size_t state)
const {
return state == start; }
183 bool IsStop(
size_t state)
const {
return is_stop[state]; }
190 const size_t offset =
GetSize();
191 const size_t new_start = offset + nfa2.
GetSize();
198 for (
size_t i = 0; i < nfa2.
GetSize(); i++) {
200 for (
const auto & t : nfa2.states[i].trans) {
203 for (
auto to : nfa2.states[i].free_to) {
206 SetStop(i+offset, nfa2.is_stop[i]);
213 for (
size_t i = 0; i < states.
size(); i++) {
214 std::cout <<
" state " << i <<
" - ";
215 for (
const auto & t : states[i].trans) {
217 for (
size_t s = 0; s <
NUM_SYMBOLS; s++)
if (t.second.symbols[s]) std::cout << ((char) s);
218 std::cout <<
"):" << t.first <<
" ";
220 if (states[i].free_to.
size()) {
221 std::cout <<
"free to:";
222 for (
auto f : states[i].free_to) std::cout <<
" " << f;
224 if (
IsStop(i)) std::cout <<
" STOP(" << (
int)
GetStop(i) <<
")";
231 for (
int i = 0; i < states.
size(); i++) {
232 std::cout <<
"Free from ( ";
233 for (
auto x : states[i].free_from) std::cout << x <<
" ";
235 std::cout <<
"Free from " << i <<
" to ( ";
236 for (
auto x : states[i].free_to) std::cout << x <<
" ";
243 template <
size_t NUM_SYMBOLS=128,
typename STOP_TYPE=u
int8_t>
247 std::set<size_t> state_set;
258 const std::set<size_t> &
GetStateSet()
const {
return state_set; }
265 for (
auto s : state_set)
if (nfa.
IsStop(s))
return true;
270 bool HasState(
size_t id) {
return state_set.count(
id); }
283 state_set = nfa.
GetNext(sym, state_set);
287 void Next(
const std::string & sym_set) {
288 for (
char x : sym_set) Next((
size_t) x);
293 std::cout <<
"cur states:";
294 for (
auto s : state_set) {
295 std::cout <<
" " << s;
void Reset()
Change current states to start + free transitions from start.
Definition: NFA.h:279
iterator insert(ARGS &&...args)
Definition: vector.h:201
void PrintFreeMoves()
Identify free moves in NFA (for debugging)
Definition: NFA.h:230
std::set< size_t > GetNext(size_t sym, const std::set< size_t > from_set) const
return the states reachable from the current set of states given the provided symbol.
Definition: NFA.h:90
bool IsEmpty(size_t state) const
Test if this state has only empty transitions from it, and not stop state.
Definition: NFA.h:186
~tNFA()
Definition: NFA.h:65
stop_t GetStop(size_t state) const
Get any stop value associated with the provided state.
Definition: NFA.h:177
bool IsStop(size_t state) const
Test if this state is a legal endpoint for the NFA.
Definition: NFA.h:183
A dynamic NFA class, for easily building non-determanistic finite automata.
Definition: NFA.h:37
void AddFreeTransition(size_t from, size_t to)
Create a free transition between 'from' and 'to'.
Definition: NFA.h:152
static const constexpr size_t NUM_SYMBOLS
Definition: NFA.h:39
void Merge(const tNFA< NUM_SYMBOLS, STOP_TYPE > &nfa2)
Merge another NFA into this one.
Definition: NFA.h:189
bool HasState(size_t id)
Is a particular NFA state currently included?
Definition: NFA.h:270
opts_t GetSymbolOptions(const std::set< size_t > &test_set) const
Return an emp::BitSet indicating the symbols available from the provided set of states.
Definition: NFA.h:110
void SetStateSet(const std::set< size_t > &in)
Set the current states.
Definition: NFA.h:276
void Print()
Print out current information about this NFA State (for debugging)
Definition: NFA.h:292
size_t GetSize() const
Return the current number of states.
Definition: NFA.h:69
void AddTransition(size_t from, size_t to, size_t sym)
Add a transition between states 'from' and 'to' that can be taken with the provided symbol...
Definition: NFA.h:131
STOP_TYPE stop_t
Definition: NFA.h:41
~tNFA_State()
Definition: NFA.h:252
size_t size() const
Definition: vector.h:151
void Next(size_t sym)
Update states given a new input symbol.
Definition: NFA.h:282
void Next(const std::string &sym_set)
Update states given a new series of input symbols (as a string)
Definition: NFA.h:287
Information about the current full state (i.e., set of legal states) of an NFA.
Definition: NFA.h:244
const std::set< size_t > & GetStart() const
Return start state and all others reachable through empty transitions.
Definition: NFA.h:72
static const PrintStr endl("<br>")
Pre-define emp::endl to insert a "<br>" and thus acting like a newline.
void Print() const
Print information about this NFA (for debugging)
Definition: NFA.h:211
tNFA(size_t num_states=1, size_t start_state=0)
Definition: NFA.h:60
size_t AddNewState()
Add a new state into the NFA and return its id.
Definition: NFA.h:128
A drop-in replacement for std::bitset, with additional bit magic features.
void insert(std::set< T > &s1, const std::set< T > &s2)
Insert the full contents of s2 into s1.
Definition: set_utils.h:24
void resize(size_t new_size)
Definition: vector.h:161
Tools to save and load data from classes.
tNFA_State(const tNFA< NUM_SYMBOLS, STOP_TYPE > &_nfa)
Definition: NFA.h:249
bool HasSymTransitions(size_t id) const
Does the provided state have symbol-transitions?
Definition: NFA.h:107
const tNFA< NUM_SYMBOLS, STOP_TYPE > & GetNFA() const
Get the NFA associated with this state.
Definition: NFA.h:255
std::set< size_t > GetNext(size_t sym, size_t from_id=0) const
Return the states reachable from the current state given the provided symbol.
Definition: NFA.h:78
bool IsStop() const
Can we legally stop in any of the current states?
Definition: NFA.h:264
If we are in emscripten, make sure to include the header.
Definition: array.h:37
tNFA< S, STOP_TYPE > & operator=(const tNFA< S, STOP_TYPE > &)=default
void AddTransition(size_t from, size_t to, const std::string &sym_set)
Add a transition between states 'from' and 'to' that can be taken with the provided symbols...
Definition: NFA.h:139
void SetStop(size_t state, T stop_val=1)
Set the specified state to be a stop state (with an optional stop value.)
Definition: NFA.h:174
#define emp_assert(...)
Definition: assert.h:199
bool HasFreeTransitions(size_t id) const
Does the provided state have free transitions?
Definition: NFA.h:104
bool IsStart(size_t state) const
Test if NFA begins at provided state (may have free transitions to other states)
Definition: NFA.h:180
const std::set< size_t > & GetStateSet() const
Get a set of states that are currently active.
Definition: NFA.h:258
void Resize(size_t new_size)
Change the number of available states.
Definition: NFA.h:121
bool IsActive() const
Are there currently any legal NFA states?
Definition: NFA.h:261
void AddTransition(size_t from, size_t to, const BitSet< NUM_SYMBOLS > &sym_set)
Add a transition between states 'from' and 'to' that can be taken with the provided symbols...
Definition: NFA.h:144
size_t GetSize()
How many states are currently included?
Definition: NFA.h:273