Which data struture to use for this situation

Question

I have a list of input strings of the form "code-marks"

For example,

Expected output:

If the values are repeated (like 1001) the latest is used and also need to be sorted.

My first bet was to use TreeMap but it would pose a problem of sorting based on values which is impossible.

Scanner in = new Scanner(System.in);
        SortedMap<Integer, Integer> map = new TreeMap<Integer, Integer>(new Comparator<Integer>() {
            public int compare(Integer i, Integer j) {
                return(j.compareTo(i));
            }
        });

        int i=0;
        while(i<5)
        {
            String[] s = in.next().split("\\-");
            map.put(Integer.parseInt(s[0]),Integer.parseInt(s[1]));
            i++;
        }
        // Get a set of the entries
        Set set = map.entrySet();
        // Get an iterator
        Iterator itr = set.iterator();
        // Display elements
        while(itr.hasNext()) {
            Map.Entry me = (Map.Entry)itr.next();
            System.out.print(me.getKey() + ": ");
            System.out.println(me.getValue());
        }

What is the best approach to this situation?

Can you explain what you mean by "If the values are repeated (like 1001) the latest is used and also need to be sorted"? Also, how should the example input be sorted? — orangepips, Jun 29 '12 at 18:06
Maybe [this](http://stackoverflow.com/a/2864923/1393766) or [this](http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java) will help a little — Pshemo, Jun 29 '12 at 18:16
I think the second link Pshemo posted is what you are looking for. Use a SortedMap and use a custom comparator to sort by value instead of key. — Chris911, Jun 29 '12 at 18:21
Do you want to maintain all of the input values? For example, do you want to remember you had `1001-40` after you read `1001-45`, or is storing `1001-45` enough since that is the only one you are printing? — Windle, Jun 29 '12 at 18:32

score 0 · Answer 1 · answered Jun 29 '12 at 18:21

0

I would simply use a HashMap<Code, CodeMark> to eliminate duplicate codes, then put all the values inside a List<CodeMark>, and sort this list by mark in descending order.

answered Jun 29 '12 at 18:21

JB Nizet

678,734
91
1,224
1,255

I'm trying to get values from map. `ArrayList codemarks = (ArrayList)map.values();` But it is throwing cannot cast exception. – John Eipe Jun 30 '12 at 11:03
maps.values() returns a Collection type and since its a super class. how do we use it for any purposes without casting? – John Eipe Jun 30 '12 at 11:09
You don't cast it. You copy its elements to a new list: `new ArrayList(map.values());` – JB Nizet Jun 30 '12 at 11:10

score 0 · Answer 2 · answered Jun 29 '12 at 18:26

You can use HashMap<Integer,Integer> simply and then sort that according to their values:

public LinkedHashMap<Integer,Integer> sortHashMapByValues(HashMap<Integer,Integer> passedMap) {
   List<Integer> mapKeys = new ArrayList<Integer>(passedMap.keySet());
   List<Integer> mapValues = new ArrayList<Integer>(passedMap.values());
   Collections.sort(mapValues);
   Collections.sort(mapKeys);

   LinkedHashMap<Integer,Integer> sortedMap = 
       new LinkedHashMap<Integer,Integer>();

   Iterator valueIt = mapValues.iterator();
   while (valueIt.hasNext()) {
       Object val = valueIt.next();
    Iterator keyIt = mapKeys.iterator();

    while (keyIt.hasNext()) {
        int key = (Integer)keyIt.next();
        int comp1 = (Integer)passedMap.get(key);
        int comp2 = (Integer)val;

        if (comp1 == comp2){
            passedMap.remove(key);
            mapKeys.remove(key);
            sortedMap.put(key,(Integer) val);
            break;
        }

    }

}
return sortedMap;
}

score 0 · Accepted Answer · edited May 23 '17 at 12:20

I stole code from the link @Pshemo posted and then setup your data as part of the main along with a simulated unit test. Code first then output.

Code

import java.util.Comparator;
import java.util.HashMap;
import java.util.TreeMap;

/**
 * Group of code marks
 */
public class CodeMarks {
    /**
     * Keep track of the most recently added suffix (value) by prefix (key)
     */
    HashMap<Integer, Integer> codeMarks = new HashMap<Integer, Integer>();

    /**
     * Add a code mark (i.e. ####-##) to the group.
     * If same prefix already exists overwrite.
     *
     * @param codeMark
     */
    public void add(String codeMark) {
        // add some validation here
        String[] pieces = codeMark.split("\\-");
        Integer prefix = Integer.parseInt(pieces[0]);
        Integer suffix = Integer.parseInt(pieces[1]);
        codeMarks.put(prefix, suffix);
    }

    /**
     * Sort code marks in descending suffix order.
     */
    Comparator<Integer> comparator = new Comparator<Integer>() {
        @Override
        public int compare(Integer prefixA, Integer prefixB) {
            Integer suffixA = codeMarks.get(prefixA);
            Integer suffixB = codeMarks.get(prefixB);
            if (suffixB.equals(suffixA))
                return prefixB.compareTo(prefixA);
            else
                return suffixB.compareTo(suffixA);
        }
    };

    /**
     * Output all code marks in descending suffix order
     */
    public String toString() {
        TreeMap<Integer,Integer> sorted_map  = new TreeMap<Integer,Integer>(comparator);
        sorted_map.putAll(codeMarks);
        StringBuffer output = new StringBuffer();
        for (Integer prefix : sorted_map.keySet()) {
            Integer suffix = sorted_map.get(prefix);
            output.append(prefix + "-" + suffix + "\n");
        }
        return output.toString();
    }

    public static void main(String args[]) {
        CodeMarks cm = new CodeMarks(){{
            add("1001-40");
            add("1002-54");
            add("1003-23");
            add("1001-45");
            add("1004-60");
        }};
        String expected =
                "1004-60\n" +
                "1002-54\n" +
                "1001-45\n" +
                "1003-23\n";
        String actual = cm.toString();
        System.out.println(actual);
        System.out.println("actual.equals(expected): " + actual.equals(expected));
    }
}

Output

1004-60
1002-54
1001-45
1003-23

actual.equals(expected): true

could you add comments. `Object a, Object b` refers to any 2 entries within treemap. But what happens here - `codeMarks.get(a)` — John Eipe, Jun 30 '12 at 03:27
@John updated answer, which should make clearer what's going on. To answer your question, the comparator receives the code mark prefix, which it uses to retrieve code mark suffixes and compare suffixes in descending order. — orangepips, Jun 30 '12 at 04:01

Which data struture to use for this situation

3 Answers3