Empirical
NFA.h
Go to the documentation of this file.
1 
23 #ifndef EMP_NFA_H
24 #define EMP_NFA_H
25 
26 #include <map>
27 #include <set>
28 
29 #include "../base/vector.h"
30 #include "BitSet.h"
31 #include "set_utils.h"
32 
33 namespace emp {
34 
36  template <size_t S=128, typename STOP_TYPE=uint8_t>
37  class tNFA {
38  public:
39  static const constexpr size_t NUM_SYMBOLS = S;
41  using stop_t = STOP_TYPE;
42 
43  private:
44  struct Transition {
45  opts_t symbols;
46  Transition() : symbols() { }
47  };
48  struct State {
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() { }
53  };
54 
55  emp::vector<State> states;
56  size_t start;
57  emp::vector< STOP_TYPE > is_stop;
58 
59  public:
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);
63  }
64  tNFA(const tNFA<S,STOP_TYPE> &) = default;
65  ~tNFA() { ; }
66  tNFA<S,STOP_TYPE> & operator=(const tNFA<S,STOP_TYPE> &) = default;
67 
69  size_t GetSize() const { return states.size(); }
70 
72  const std::set<size_t> & GetStart() const {
73  emp_assert(start < states.size());
74  return states[start].free_to;
75  }
76 
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);
84  }
85  }
86  return to_set;
87  }
88 
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);
97  }
98  }
99  }
100  return to_set;
101  }
102 
104  bool HasFreeTransitions(size_t id) const { return states[id].free_to.size(); }
105 
107  bool HasSymTransitions(size_t id) const { return states[id].trans.size(); }
108 
110  opts_t GetSymbolOptions(const std::set<size_t> & test_set) const {
111  opts_t options;
112  for (size_t id : test_set) {
113  for (const auto & t : states[id].trans) {
114  options |= t.second.symbols;
115  }
116  }
117  return options;
118  }
119 
121  void Resize(size_t new_size) {
122  states.resize(new_size);
123  is_stop.resize(new_size, 0);
124  if (new_size > start) states[start].free_to.insert(start);
125  }
126 
128  size_t AddNewState() { size_t new_state = GetSize(); Resize(new_state+1); return new_state; }
129 
131  void AddTransition(size_t from, size_t to, size_t sym) {
132  emp_assert(from < states.size(), from, states.size());
133  emp_assert(to < states.size(), to, states.size());
134 
135  states[from].trans[to].symbols[sym] = true;
136  }
137 
139  void AddTransition(size_t from, size_t to, const std::string & sym_set) {
140  for (char x : sym_set) AddTransition(from, to, (size_t) x);
141  }
142 
144  void AddTransition(size_t from, size_t to, const BitSet<NUM_SYMBOLS> & sym_set) {
145  emp_assert(from < states.size(), from, states.size());
146  emp_assert(to < states.size(), to, states.size());
147 
148  states[from].trans[to].symbols |= sym_set;
149  }
150 
152  void AddFreeTransition(size_t from, size_t to) {
153  emp_assert(from < states.size(), from, states.size());
154  emp_assert(to < states.size(), to, states.size());
155 
156  // Keep track of where free transitions could have come from and can continue to.
157  auto extend_to = states[to].free_to;
158  auto extend_from = states[from].free_from;
159  extend_to.insert(to);
160  extend_from.insert(from);
161 
162  // Insert all combinations of where new moves can be coming from or going to.
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);
167  }
168  }
169 
170  }
171 
173  template <typename T=stop_t>
174  void SetStop(size_t state, T stop_val=1) { is_stop[state] = (stop_t) stop_val; }
175 
177  stop_t GetStop(size_t state) const { return is_stop[state]; }
178 
180  bool IsStart(size_t state) const { return state == start; }
181 
183  bool IsStop(size_t state) const { return is_stop[state]; }
184 
186  bool IsEmpty(size_t state) const { return !HasSymTransitions(state) && !IsStop(state); }
187 
189  void Merge(const tNFA<NUM_SYMBOLS,STOP_TYPE> & nfa2) {
190  const size_t offset = GetSize(); // How far should we offset new NFA states?
191  const size_t new_start = offset + nfa2.GetSize(); // Locate the new start node.
192  Resize(offset + nfa2.GetSize() + 1); // Make room for new NFA states + new start.
193  AddFreeTransition(new_start, start); // Free transition from new start to
194  AddFreeTransition(new_start, nfa2.start+offset); // starts of both original NFAs.
195  start = new_start; // Set the new start node.
196 
197  // Loop through new states and add them in.
198  for (size_t i = 0; i < nfa2.GetSize(); i++) {
199  // Move transitions.
200  for (const auto & t : nfa2.states[i].trans) {
201  AddTransition(i+offset, t.first+offset, t.second.symbols);
202  }
203  for (auto to : nfa2.states[i].free_to) {
204  AddFreeTransition(i+offset, to+offset);
205  }
206  SetStop(i+offset, nfa2.is_stop[i]); // Maintain the stop value for this state.
207  }
208  }
209 
211  void Print() const {
212  std::cout << states.size() << " States:" << std::endl;
213  for (size_t i = 0; i < states.size(); i++) {
214  std::cout << " state " << i << " - ";
215  for (const auto & t : states[i].trans) {
216  std::cout << "(";
217  for (size_t s = 0; s < NUM_SYMBOLS; s++) if (t.second.symbols[s]) std::cout << ((char) s);
218  std::cout << "):" << t.first << " ";
219  }
220  if (states[i].free_to.size()) {
221  std::cout << "free to:";
222  for (auto f : states[i].free_to) std::cout << " " << f;
223  }
224  if (IsStop(i)) std::cout << " STOP(" << (int) GetStop(i) << ")";
225  std::cout << std::endl;
226  }
227  }
228 
230  void PrintFreeMoves() {
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 << " ";
234  std::cout << ") to " << i << std::endl;
235  std::cout << "Free from " << i << " to ( ";
236  for (auto x : states[i].free_to) std::cout << x << " ";
237  std::cout << ")" << std::endl;
238  }
239  }
240  };
241 
243  template <size_t NUM_SYMBOLS=128, typename STOP_TYPE=uint8_t>
244  class tNFA_State {
245  private:
246  const tNFA<NUM_SYMBOLS,STOP_TYPE> & nfa;
247  std::set<size_t> state_set;
248  public:
249  tNFA_State(const tNFA<NUM_SYMBOLS,STOP_TYPE> & _nfa) : nfa(_nfa), state_set() {
250  state_set = nfa.GetStart();
251  }
252  ~tNFA_State() { ; }
253 
255  const tNFA<NUM_SYMBOLS,STOP_TYPE> & GetNFA() const { return nfa; }
256 
258  const std::set<size_t> & GetStateSet() const { return state_set; }
259 
261  bool IsActive() const { return state_set.size(); }
262 
264  bool IsStop() const {
265  for (auto s : state_set) if (nfa.IsStop(s)) return true;
266  return false;
267  }
268 
270  bool HasState(size_t id) { return state_set.count(id); }
271 
273  size_t GetSize() { return state_set.size(); }
274 
276  void SetStateSet(const std::set<size_t> & in) { state_set = in; }
277 
279  void Reset() { state_set = nfa.GetStart(); }
280 
282  void Next(size_t sym) {
283  state_set = nfa.GetNext(sym, state_set);
284  }
285 
287  void Next(const std::string & sym_set) {
288  for (char x : sym_set) Next((size_t) x);
289  }
290 
292  void Print() {
293  std::cout << "cur states:";
294  for (auto s : state_set) {
295  std::cout << " " << s;
296  }
297  std::cout << std::endl;
298  }
299  };
300 
303 
306 }
307 
308 #endif
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 &#39;from&#39; and &#39;to&#39;.
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 &#39;from&#39; and &#39;to&#39; 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 &#39;from&#39; and &#39;to&#39; 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 &#39;from&#39; and &#39;to&#39; 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