CODEWITHSUNDEEP
javadata-structures
MysteryMoose
MysteryMoose

Reputation: 2363

Data Structure for Storing Multi-key and Value Pairs in Java

Good evening,

I am searching for an elegant solution to implement a transition table (Specifically, for a universal pushdown automaton) that uses several discrete values for a given transition. They say a picture is worth a thousand words so here is part of my table:

State    InputSymbol    StackSymbol   Move(NewState, Action)
------------------------------------------------------------
  0           a              Z0           (0, push)
  0           a              a            (0, push)
  0           a              b            (0, pop)
  0           b              Z0           (1, push)
  ...

Now, I have considered multi-dimensional arrays, ArrayLists of ArrayLists, and other solutions of the sort but all seem rather brutish. This is further complicated by the fact that every possible combination of my three symbols (a, b, and Z0) is not represented in the table.

I have been contemplating using a HashMap, but I am not entirely sure how to make this work with multiple key values. I was considering concatenating all three symbols together and using the resultant string as my key but that, too, seems less than elegant.

And, for the record, this is homework but actually giving an elegant solution is not strictly required. I just enjoy good code.

Thank you in advance for your assistance.

Upvotes: 3

Views: 3731

Answers (3)

AlexR
AlexR

Reputation: 115328

Take a look on MultiHashMap from Jakarta commons collections framework. http://commons.apache.org/collections/api-release/org/apache/commons/collections/MultiHashMap.html

Unfortunately jakarta collection framework is not parametrized, i.e. does not support generics, so you will have to cast you your specific type.

Other solution is to implement something similar your self. Create class Move that holds your data. Create class Table that encapsulate the logic. This class may contain a list (better LinkedList) of Moves and N maps: Map> stateIndex Map> inputSymbolIndex etc, etc.

implementation of add method is trivial. Implementation of get is more interesting:

public Move get(Integer state, Character inputSymbol, StackSymbol stackSymbol) {
    List<Move> stateList = stateIndex.get(state);
    List<Move> inputSymbolList = stateIndex.get(inputSymbol);
    List<Move> stackSymbolList = stateIndex.get(stackSymbol);

    Set<Move> result = new HashSet<Move>(stateList);
    result.retainAll(inputSymbolList);
    result.retainAll(stackSymbolList);

    if (result.size() > 1) {
        throw new IllegalStateException("Unique constraint violation");
    } 
    return  result.size() == 0 ? null : result.interator().next();
}

Upvotes: 0

Newbie
Newbie

Reputation: 7249

Encapsulate {State, InputSymbol, StackSymbol} in an object. Then, use the "hashcode()" of the object as the key for your hash table. For more information regarding hash codes see Doc.

Upvotes: 1

Emil
Emil

Reputation: 13789

Make a class like this: 

 class Key{
    int state;
    char inputSysmbol;
    String StackSymbol;
    }

Then use the map Map<Key,Move>.

Make a class for Move just like above and don't forget to override hashcode and equals method in both classes.

Upvotes: 4

Related Questions