Which data struture to use for this situation

Question

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

For example,

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

Expected output:

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

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?

Answer 1

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