src/main/java/org/xerial/util/graph/DFA.java

   1 /*--------------------------------------------------------------------------\r
   2  *  Copyright 2007 Taro L. Saito\r
   3  *\r
   4  *  Licensed under the Apache License, Version 2.0 (the "License");\r
   5  *  you may not use this file except in compliance with the License.\r
   6  *  You may obtain a copy of the License at\r
   7  *\r
   8  *     http://www.apache.org/licenses/LICENSE-2.0\r
   9  *\r
  10  *  Unless required by applicable law or agreed to in writing, software\r
  11  *  distributed under the License is distributed on an "AS IS" BASIS,\r
  12  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  13  *  See the License for the specific language governing permissions and\r
  14  *  limitations under the License.\r
  15  *--------------------------------------------------------------------------*/\r
  16 //--------------------------------------\r
  17 // XerialJ Project\r
  18 //\r
  19 // DFA.java\r
  20 // Since: May 8, 2007\r
  21 //\r
  22 // $URL: http://www.xerial.org/svn/project/XerialJ/trunk/xerial-core/src/main/java/org/xerial/util/graph/DFA.java $ \r
  23 // $Author: leo $\r
  24 //--------------------------------------\r
  25 package org.xerial.util.graph;\r
  26 \r
  27 import java.util.HashMap;\r
  28 import java.util.HashSet;\r
  29 \r
  30 import org.xerial.util.CollectionUtil;\r
  31 \r
  32 \r
  33 \r
  34 /**\r
  35  * Deterministic finite automaton\r
  36  * @author leo\r
  37  *\r
  38  */\r
  39 public class DFA<State, Alphabet> \r
  40 {\r
  41         /**\r
  42          * if the current state is null, this DFS is in invalid sate (never reach any of terminal states) \r
  43          */\r
  44         private State _currentState;\r
  45         private HashSet<State> _stateSet = new HashSet<State>();\r
  46         private HashSet<State> _terminalStateSet = new HashSet<State>();\r
  47 \r
  48         class TransitionTargetTable extends HashMap<Alphabet, State>\r
  49         {\r
  50                 private static final long serialVersionUID = 1L;\r
  51 \r
  52                 public String toString()\r
  53                 {\r
  54                         return CollectionUtil.displayMap(this, "->", ", ");\r
  55                 }\r
  56         }\r
  57         \r
  58         class TransitionTable extends HashMap<State, TransitionTargetTable>\r
  59         {\r
  60                 private static final long serialVersionUID = 1L;\r
  61                 \r
  62                 public void addTransition(State from, Alphabet input, State to)\r
  63                 {\r
  64                         TransitionTargetTable targetTable = this.get(from);\r
  65                         if(targetTable == null)\r
  66                                 targetTable = this.put(from, new TransitionTargetTable());\r
  67 \r
  68                         targetTable.put(input, to);\r
  69                 }\r
  70                 \r
  71                 public State nextState(State currentState, Alphabet input)\r
  72                 {\r
  73                         TransitionTargetTable targetTable = this.get(currentState);\r
  74                         if(targetTable == null)\r
  75                                 return null;\r
  76                         \r
  77                         return targetTable.get(input);\r
  78                 }\r
  79                 \r
  80                 public String toString()\r
  81                 {\r
  82                         return CollectionUtil.displayMap(this, ":", "\n");\r
  83                 }\r
  84         };\r
  85         \r
  86         private TransitionTable _transitionTable = new TransitionTable();\r
  87         \r
  88         public DFA(State initialState)\r
  89         {\r
  90                 _currentState = initialState;\r
  91         }\r
  92         \r
  93         public void addState(State s)\r
  94         {\r
  95                 _stateSet.add(s);\r
  96         }\r
  97         public void addTerminalState(State s)\r
  98         {\r
  99                 _stateSet.add(s);\r
 100                 _terminalStateSet.add(s);\r
 101         }\r
 102         \r
 103         public void addTransition(State from, Alphabet input, State to)\r
 104         {\r
 105                 _stateSet.add(from);\r
 106                 _stateSet.add(to);\r
 107                 _transitionTable.addTransition(from, input, to);\r
 108         }\r
 109 \r
 110 \r
 111         public boolean isTerminated()\r
 112         {\r
 113                 if(_currentState == null)\r
 114                         return false;\r
 115                 return _terminalStateSet.contains(_currentState);\r
 116         }\r
 117         \r
 118         public State transit(Alphabet input)\r
 119         {\r
 120                 if(_currentState == null)\r
 121                         return null;    // null state cannot go anywhere\r
 122                 \r
 123                 State nextState = _transitionTable.nextState(_currentState, input);\r
 124                 _currentState = nextState;\r
 125                 return _currentState;\r
 126         }\r
 127         \r
 128         \r
 129         public String toString()\r
 130         {\r
 131                 return _transitionTable.toString();\r
 132         }\r
 133         \r
 134         \r
 135 }\r
 136 \r
 137 \r
 138 \r
 139 \r
 140 \r
 141 \r