Class: ActionDispatch::Journey::NFA::TransitionTable
- Includes:
- Dot
- Defined in:
- actionpack/lib/action_dispatch/journey/nfa/transition_table.rb
Overview
:nodoc:
Instance Attribute Summary collapse
-
#accepting ⇒ Object
Returns the value of attribute accepting.
-
#memos ⇒ Object
readonly
Returns the value of attribute memos.
Instance Method Summary collapse
- #[]=(i, f, s) ⇒ Object
- #accepting?(state) ⇒ Boolean
- #accepting_states ⇒ Object
- #add_memo(idx, memo) ⇒ Object
- #alphabet ⇒ Object
-
#eclosure(t) ⇒ Object
Returns a set of NFA states reachable from some NFA state
s
in sett
on nil-transitions alone. -
#following_states(t, a) ⇒ Object
Returns set of NFA states to which there is a transition on ast symbol
a
from some states
int
. -
#initialize ⇒ TransitionTable
constructor
A new instance of TransitionTable.
- #memo(idx) ⇒ Object
- #merge(left, right) ⇒ Object
-
#move(t, a) ⇒ Object
Returns set of NFA states to which there is a transition on ast symbol
a
from some states
int
. - #states ⇒ Object
- #transitions ⇒ Object
Methods included from Dot
Constructor Details
#initialize ⇒ TransitionTable
Returns a new instance of TransitionTable.
14 15 16 17 18 19 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 14 def initialize @table = Hash.new { |h, f| h[f] = {} } @memos = {} @accepting = nil @inverted = nil end |
Instance Attribute Details
#accepting ⇒ Object
Returns the value of attribute accepting
11 12 13 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 11 def accepting @accepting end |
#memos ⇒ Object (readonly)
Returns the value of attribute memos
12 13 14 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 12 def memos @memos end |
Instance Method Details
#[]=(i, f, s) ⇒ Object
37 38 39 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 37 def []=(i, f, s) @table[f][i] = s end |
#accepting?(state) ⇒ Boolean
21 22 23 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 21 def accepting?(state) accepting == state end |
#accepting_states ⇒ Object
25 26 27 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 25 def accepting_states [accepting] end |
#add_memo(idx, memo) ⇒ Object
29 30 31 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 29 def add_memo(idx, memo) @memos[idx] = memo end |
#alphabet ⇒ Object
66 67 68 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 66 def alphabet inverted.values.flat_map(&:keys).compact.uniq.sort_by(&:to_s) end |
#eclosure(t) ⇒ Object
Returns a set of NFA states reachable from some NFA state s
in set t
on nil-transitions alone.
72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 72 def eclosure(t) stack = Array(t) seen = {} children = [] until stack.empty? s = stack.pop next if seen[s] seen[s] = true children << s stack.concat(inverted[s][nil]) end children.uniq end |
#following_states(t, a) ⇒ Object
Returns set of NFA states to which there is a transition on ast symbol a
from some state s
in t
.
52 53 54 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 52 def following_states(t, a) Array(t).flat_map { |s| inverted[s][a] }.uniq end |
#memo(idx) ⇒ Object
33 34 35 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 33 def memo(idx) @memos[idx] end |
#merge(left, right) ⇒ Object
41 42 43 44 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 41 def merge(left, right) @memos[right] = @memos.delete(left) @table[right] = @table.delete(left) end |
#move(t, a) ⇒ Object
Returns set of NFA states to which there is a transition on ast symbol a
from some state s
in t
.
58 59 60 61 62 63 64 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 58 def move(t, a) Array(t).map { |s| inverted[s].keys.compact.find_all { |sym| sym === a }.map { |sym| inverted[s][sym] } }.flatten.uniq end |
#states ⇒ Object
46 47 48 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 46 def states (@table.keys + @table.values.flat_map(&:keys)).uniq end |
#transitions ⇒ Object
90 91 92 93 94 |
# File 'actionpack/lib/action_dispatch/journey/nfa/transition_table.rb', line 90 def transitions @table.flat_map { |to, hash| hash.map { |from, sym| [from, sym, to] } } end |