remorhaz /
php-unilex
| Conditions | 27 |
| Paths | > 20000 |
| Total Lines | 128 |
| Code Lines | 91 |
| Lines | 0 |
| Ratio | 0 % |
| Changes | 0 | ||
Small methods make your code easier to understand, in particular if combined with a good name. Besides, if your method is small, finding a good name is usually much easier.
For example, if you find yourself adding comments to a method's body, this is usually a good sign to extract the commented part to a new method, and use the comment as a starting point when coming up with a good name for this new method.
Commonly applied refactorings include:
If many parameters/temporary variables are present:
| 1 | <?php |
||
| 35 | public static function fromNfa(Nfa $nfa): Dfa |
||
| 36 | { |
||
| 37 | $dfa = new Dfa(); |
||
| 38 | (new self($dfa, $nfa))->run(); |
||
| 39 | |||
| 40 | $stateQuery = []; |
||
| 41 | $nonEquivalentStates = []; |
||
| 42 | $dfaStates = $dfa->getStateMap()->getStateList(); |
||
| 43 | $devilState = max($dfaStates) + 1; |
||
| 44 | $dfaStates[] = $devilState; |
||
| 45 | |||
| 46 | $transitionMap = []; |
||
| 47 | |||
| 48 | foreach ($dfaStates as $stateA) { |
||
| 49 | foreach ($dfaStates as $stateB) { |
||
| 50 | $marked = $nonEquivalentStates[$stateA][$stateB] ?? false; |
||
| 51 | if ($marked) { |
||
| 52 | continue; |
||
| 53 | } |
||
| 54 | $isFinishStateA = $stateA == $devilState |
||
| 55 | ? false |
||
| 56 | : $dfa->getStateMap()->isFinishState($stateA); |
||
| 57 | $isFinishStateB = $stateB == $devilState |
||
| 58 | ? false |
||
| 59 | : $dfa->getStateMap()->isFinishState($stateB); |
||
| 60 | if ($isFinishStateA == $isFinishStateB) { |
||
| 61 | continue; |
||
| 62 | } |
||
| 63 | $nonEquivalentStates[$stateA][$stateB] = true; |
||
| 64 | $nonEquivalentStates[$stateB][$stateA] = true; |
||
| 65 | $stateQuery[] = [$stateA, $stateB]; |
||
| 66 | } |
||
| 67 | $transitionMap[$stateA][$devilState] = $dfa->getSymbolTable()->getSymbolList(); |
||
| 68 | } |
||
| 69 | |||
| 70 | foreach ($dfa->getTransitionMap()->getTransitionList() as $sourceState => $transitions) { |
||
| 71 | $devilStateSymbols = $dfa->getSymbolTable()->getSymbolList(); |
||
| 72 | foreach ($transitions as $targetState => $symbols) { |
||
| 73 | $devilStateSymbols = array_diff($devilStateSymbols, $symbols); |
||
| 74 | $transitionMap[$sourceState][$targetState] = $symbols; |
||
| 75 | } |
||
| 76 | $transitionMap[$sourceState][$devilState] = $devilStateSymbols; |
||
| 77 | } |
||
| 78 | |||
| 79 | while (!empty($stateQuery)) { |
||
| 80 | [$firstTargetState, $secondTargetState] = array_pop($stateQuery); |
||
| 81 | |||
| 82 | foreach ($dfaStates as $stateA) { |
||
| 83 | foreach ($dfaStates as $stateB) { |
||
| 84 | $isMarked = $nonEquivalentStates[$stateA][$stateB] ?? false; |
||
| 85 | if ($isMarked) { |
||
| 86 | continue; |
||
| 87 | } |
||
| 88 | $symbolsA = $transitionMap[$stateA][$firstTargetState] ?? []; |
||
| 89 | $symbolsB = $transitionMap[$stateB][$secondTargetState] ?? []; |
||
| 90 | $symbols = array_intersect($symbolsA, $symbolsB); |
||
| 91 | if (!empty($symbols)) { |
||
| 92 | $nonEquivalentStates[$stateA][$stateB] = true; |
||
| 93 | $nonEquivalentStates[$stateB][$stateA] = true; |
||
| 94 | $stateQuery[] = [$stateA, $stateB]; |
||
| 95 | } |
||
| 96 | } |
||
| 97 | } |
||
| 98 | } |
||
| 99 | |||
| 100 | $equivalentStates = []; |
||
| 101 | $nextClass = 1; |
||
| 102 | $classes = []; |
||
| 103 | foreach ($dfaStates as $stateA) { |
||
| 104 | if (!isset($classes[$stateA])) { |
||
| 105 | $class = $nextClass++; |
||
| 106 | foreach ($dfaStates as $stateB) { |
||
| 107 | $isMarked = $nonEquivalentStates[$stateA][$stateB] ?? false; |
||
| 108 | if (!$isMarked) { |
||
| 109 | $classes[$stateB] = $class; |
||
| 110 | if ($stateB != $devilState) { |
||
| 111 | $equivalentStates[$class][$stateB] = true; |
||
| 112 | } |
||
| 113 | } |
||
| 114 | } |
||
| 115 | } |
||
| 116 | } |
||
| 117 | |||
| 118 | $minimizedDfa = new Dfa(); |
||
| 119 | $minimizedDfa->setSymbolTable($dfa->getSymbolTable()); |
||
| 120 | $nfaStartStates = $nfa->getStateMap()->getStartStateList(); |
||
| 121 | $nfaFinishStates = $nfa->getStateMap()->getFinishStateList(); |
||
| 122 | $newDfaStates = []; |
||
| 123 | foreach ($equivalentStates as $newState => $dfaStates) { |
||
| 124 | $newValue = []; |
||
| 125 | foreach (array_keys($dfaStates) as $dfaState) { |
||
| 126 | $nfaStates = $dfa->getStateMap()->getStateValue($dfaState); |
||
| 127 | $newValue = array_merge($newValue, $nfaStates); |
||
| 128 | $newDfaStates[$dfaState] = $newState; |
||
| 129 | } |
||
| 130 | $newValue = array_unique($newValue); |
||
| 131 | sort($newValue); |
||
| 132 | $minimizedDfa->getStateMap()->createState($newValue); |
||
| 133 | $isStartState = !empty(array_intersect($nfaStartStates, $newValue)); |
||
| 134 | if ($isStartState) { |
||
| 135 | $minimizedDfa->getStateMap()->addStartState($newState); |
||
| 136 | } |
||
| 137 | $isFinishState = !empty(array_intersect($nfaFinishStates, $newValue)); |
||
| 138 | if ($isFinishState) { |
||
| 139 | $minimizedDfa->getStateMap()->addFinishState($newState); |
||
| 140 | } |
||
| 141 | } |
||
| 142 | $transitionMap = []; |
||
| 143 | foreach ($dfa->getTransitionMap()->getTransitionList() as $sourceState => $transitions) { |
||
| 144 | foreach ($transitions as $targetState => $symbols) { |
||
| 145 | $newSourceState = $newDfaStates[$sourceState]; |
||
| 146 | $newTargetState = $newDfaStates[$targetState]; |
||
| 147 | $transitionMap[$newSourceState][$newTargetState] = array_unique( |
||
| 148 | array_merge( |
||
| 149 | $transitionMap[$newSourceState][$newTargetState] ?? [], |
||
| 150 | $symbols |
||
| 151 | ) |
||
| 152 | ); |
||
| 153 | } |
||
| 154 | } |
||
| 155 | foreach ($transitionMap as $sourceState => $transitions) { |
||
| 156 | foreach ($transitions as $targetState => $symbols) { |
||
| 157 | sort($symbols); |
||
| 158 | $minimizedDfa->getTransitionMap()->addTransition($sourceState, $targetState, $symbols); |
||
| 159 | } |
||
| 160 | } |
||
| 161 | |||
| 162 | return $minimizedDfa; |
||
| 163 | } |
||
| 299 |
Loading history...