| 4419 | } |
| 4420 | |
| 4421 | void Pattern::gen_min(std::set<DFA::State*>& states) |
| 4422 | { |
| 4423 | // find min between 0 and Const::BITS |
| 4424 | min_ = Const::BITS; |
| 4425 | std::set<DFA::State*> prev, next(states); |
| 4426 | for (uint16_t level = 0; level < min_; ++level) |
| 4427 | { |
| 4428 | bool none = true; |
| 4429 | prev.clear(); |
| 4430 | prev.swap(next); |
| 4431 | for (std::set<DFA::State*>::iterator from = prev.begin(); from != prev.end(); ++from) |
| 4432 | { |
| 4433 | DFA::MetaEdgesClosure edge(*from); |
| 4434 | for (; !edge.done() && !edge.accepting(); ++edge) |
| 4435 | { |
| 4436 | DFA::State *next_state = edge.state(); |
| 4437 | // ignore edges from a state to a state with breadth-first depth <= cut |
| 4438 | if (lbk_ > 0 && next_state->first > 0 && next_state->first <= cut_) |
| 4439 | continue; |
| 4440 | none = false; |
| 4441 | if (min_ == level + 1) |
| 4442 | continue; |
| 4443 | if (edge.next_accepting()) |
| 4444 | min_ = level + 1; |
| 4445 | else |
| 4446 | next.insert(next_state); |
| 4447 | } |
| 4448 | // is this state accepting through one or more meta edges in the closure? |
| 4449 | if (edge.accepting()) |
| 4450 | { |
| 4451 | none = true; |
| 4452 | break; |
| 4453 | } |
| 4454 | } |
| 4455 | if (none) |
| 4456 | min_ = level; |
| 4457 | } |
| 4458 | } |
| 4459 | |
| 4460 | void Pattern::gen_predict_match(std::set<DFA::State*>& states) |
| 4461 | { |