views:

217

answers:

1

I want to put State objects (which are HashMaps with Character as key and State as Value into an ArrayList named allStates. Should I override the equals and hashCode methods here? Why? How?

This code is for the Automaton and State classes I've built so far:

class State extends HashMap<Character, State>{

boolean isFinal;
boolean isInitial;
int stateId;

State () {
    isInitial=false;
    isFinal = false;
    }

public boolean equals (Object o){
    boolean isEqual = false;
    State compare = (State)o;

    if ((compare.stateId)==this.stateId)
    {
        return true;
    }
    return isEqual;
}

public int hashCode() {
    int theHashCode = stateId%7;

    return theHashCode;
}


}

  class Automaton{
     List <State> allStates;
    //private List<State> finalStates;
     int  theInitialStateIntIndex;
     State actualState;
      char [] alphabet;

    Automaton() {
        allStates = new ArrayList<State>();
    }

    public void setAllStates (int numberOfStates)  {
        for (int i =0; i <numberOfStates; i++) {
            State newState = new State();
            newState.stateId = i;
            allStates.add(newState);
         }
    }


    public void setAlphabet (String alphabetLine){
        alphabet = alphabetLine.toCharArray();
    }

    public void markFinalStates (String [] finalStates){
        for (int index =0; index<finalStates.length; index++) {
            int aFinalStateId = Integer.parseInt(finalStates[index]);

            State aFinalState = allStates.get(aFinalStateId);
            aFinalState.isFinal = true;
            allStates.add(aFinalStateId, aFinalState);

            /*DEBUG*/
            aFinalState = allStates.get(aFinalStateId);
            if ((aFinalState.isFinal)==true)
            System.out.println("THE STATE " + aFinalStateId + " IS MARKED AS FINAL");
        }
    }

    public void markInitialState (int initialStateId) {
            State theInitialState = allStates.get(initialStateId);
            theInitialState.isInitial=true;
            allStates.add(initialStateId, theInitialState);

            theInitialStateIntIndex = initialStateId;

            /*DEBUG*/

            System.out.println("THE INITIAL STATE ID IS " + initialStateId);

            theInitialState = allStates.get(initialStateId);
            if ((theInitialState.isInitial)==true)
            System.out.println("THE STATE " + initialStateId + " IS MARKED AS INITIAL");
    }


    public void setTransitions(int stateId, String transitionsLine){
            State theOneToChange = allStates.get(stateId);

            String [] statesToReachStringSplitted = transitionsLine.split(" ");

            for (int symbolIndex=0; symbolIndex<statesToReachStringSplitted.length;symbolIndex++){
                int reachedState= Integer.parseInt(statesToReachStringSplitted[symbolIndex]);
                theOneToChange.put(alphabet[symbolIndex],allStates.get(reachedState));

                System.out.println("THE STATE " + stateId + " REACHES THE STATE " + reachedState + " WITH THE SYMBOL " + alphabet[symbolIndex]);
            }

            allStates.add(stateId, theOneToChange);
    }


    public int findInitialState(){
        int index =0;

       cycle: for (; index<allStates.size(); index++){
            State s = allStates.get(index);

            if (s.isInitial==true) {
                break cycle;
           }
        } return index;
}

    public void processString (String string)
    {
        StringBuilder stepString= new StringBuilder (string);

        int actualStateIntIndex;
        System.out.println("THE FOUND INITIAL ONE IS "+ theInitialStateIntIndex);
        State firstState = allStates.get(theInitialStateIntIndex);
        actualState = firstState;

        while (stepString.length()>0){
           Character characterToProcess = stepString.charAt(0);
           stepString.deleteCharAt(0);

           State nextState;
           nextState = ((State)actualState.get(characterToProcess)); // pasa al siguiente State
           actualState = nextState;

           actualStateIntIndex=allStates.indexOf(actualState);

           System.out.println("the actual state for " + stepString + " is " + actualStateIntIndex);
           if ((actualState.isFinal==true) && (stepString.length()==0))
              {
                  System.out.println("THE STRING " + string + " IS ACCEPTED AT STATE " + actualStateIntIndex );
              }
           else if (stepString.length()==0 && (actualState.isFinal==false)){
                  System.out.println("THE STRING " + string + " IS REJECTED AT STATE " + actualStateIntIndex);
              }

           }
       }
    }
A: 
  1. If the automaton is a DFA, then one can use the Accessing String to ID the field.
    An accessing String is any string that could be used to reach the state from the start state. One will have to build the string while building the DFA, however, it won't add more time complexity. (Yes, one then needs to hashcode/equal the string)

  2. Or actually, ID the states by an increasing serial number/string should work for all automaton. Then hashcode/equal based on the ID.

Go for the 2nd one, easier and works better than 1, unless you want to take care of the duplicated states.

Yes, you need the hashcode and equals for a user defined type to work with hash.

Dr. Xray