I am trying to build an NFA with a special purpose of searching, which is totally different from regex. The State has following format
class State implements List{
//GLOBAL DATA
static int depth;
//STATE VALUES
String stateName;
ArrayList<String> label = new ArrayList<>(); //Label for states
//LINKS TO OTHER STATES
boolean finalState;
ArrayList<State> nextState ; // Link with multiple next states
State preState; // previous state
public State()
{
stateName = "";
finalState = true;
nextState = new ArrayList<>();
}
public void addlabel(String lbl)
{
if(!this.label.contains(lbl))
this.label.add(lbl);
}
public State(String state, String lbl)
{
this.stateName = state;
if(!this.label.contains(lbl))
this.label.add(lbl);
depth++;
}
public State(String state, String lbl, boolean fstate)
{
this.stateName = state;
this.label.add(lbl);
this.finalState = fstate;
this.nextState = new ArrayList<>();
}
void displayState()
{
System.out.print(this.stateName+" --> ");
for(Iterator<String> it = label.iterator(); it.hasNext();)
{
System.out.print(it.next()+" , ");
}
System.out.println("\nNo of States : "+State.depth);
}
Next, the NFA class is
public class NFA
{
static final String[] STATES= {"A","B","C","D","E","F","G","H","I","J","K","L","M"
,"N","O","P","Q","R","S","T","U","V","W","X","Y","Z"};
State startState;
State currentState;
static int level;
public NFA()
{
startState = new State();
startState = null;
currentState = new State();
currentState = null;
startState = currentState;
}
/**
*
* @param st
*/
NFA(State startstate)
{
startState = new State();
startState = startstate;
currentState = new State();
currentState = null;
currentState = startState ; // To show that their is only one element in NFA
}
boolean insertState(State newState)
{
newState.nextState = new ArrayList<>();
if(currentState == null && startState == null ) //if empty NFA
{
newState.preState = null;
startState = newState;
currentState = newState;
State.depth = 0;
return true;
}
else
{
if(!Exist(newState.stateName))//Exist is used to check for duplicates
{
newState.preState = currentState ;
currentState.nextState.add(newState);
currentState = newState;
State.depth++;
return true;
}
}
return false;
}
boolean insertState(State newState, String label)
{
newState.label.add(label);
newState.nextState = null;
newState.preState = null;
if(currentState == null && startState == null)
{
startState = newState;
currentState = newState;
State.depth = 0;
return true;
}
else
{
if(!Exist(newState.stateName))
{
newState.preState = currentState;
currentState.nextState.add(newState);
currentState = newState;
State.depth++;
return true;
}
else
{
///code goes here
}
}
return false;
}
void markFinal(State s)
{
s.finalState = true;
}
void unmarkFinal(State s)
{
s.finalState = false;
}
boolean Exist(String s)
{
State temp = startState;
if(startState.stateName.equals(s))
return true;
Iterator<State> it = temp.nextState.iterator();
while(it.hasNext())
{
Iterator<State> i = it ;//startState.nextState.iterator();
{
while(i.hasNext())
{
if(i.next().stateName.equals(s))
return true;
}
}
//else
// return false;
}
return false;
}
void displayNfa()
{
State st = startState;
if(startState == null && currentState == null)
{
System.out.println("The NFA is empty");
}
else
{
while(st != null)
{
if(!st.nextState.isEmpty())
{
Iterator<State> it = st.nextState.iterator();
do
{
st.displayState();
st = it.next();
}while(it.hasNext());
}
else
{
st = null;
}
}
}
System.out.println();
}
/**
* @param args the command line arguments
*/
/**
*
* @param args the command line arguments
*/
public static void main(String[] args)
{
// TODO code application logic here
NFA l = new NFA();
State s = new State("A11", "a",false);
NFA ll = new NFA(s);
s = new State("A111", "a",false);
ll.insertState(s);
ll.insertState(new State("A1","0"));
ll.insertState(new State("A1111","0"));
ll.displayNfa();
int j = 1;
for(int i = 0 ; i < 2 ; i++)
{
int rand = (int) (Math.random()* 10);
State st = new State(STATES[rand],String.valueOf(i), false);
if(l.insertState(st))
{
System.out.println(j+" : " + STATES[rand]+" and "+String.valueOf(i)+ " inserted");
j++;
}
}
l.displayNfa();
System.out.println("No of states inserted : "+ j--);
}
I want to do the following
This program always skip to display the last state i.e. if there are 10 states inserted, it will display only 9.
In exist() method , i used two iterator but i do not know why it is working
I have no idea how to perform searching for the existing class name, when dealing with iterators.
How should i keep track of current State, properly iterate through the nextState List, Label List in a depth first order.
How to insert unique States i.e. if State "A" is inserted once, it should not insert it again (The exist method is not working)
Best Regards
