List
models a numbered sequence of elements where the client
can control the ordering of the elements.
Set
models a group of unique elements (no duplicates) where
the client has no control over the ordering of the elements.
Map
models a group of elements that are accessed by unique
keys.
LinkedHashMap
is a map that stores its
keys in order in which keys were inserted into the map.
Map<String, Integer> daysInMonth = new LinkedHashMap<String, Integer>(); daysInMonth.put("Jan", 31); daysInMonth.put("Feb", 28); daysInMonth.put("Mar", 31); daysInMonth.put("Apr", 30); daysInMonth.put("May", 31); daysInMonth.put("Jun", 30); daysInMonth.put("Jul", 31); daysInMonth.put("Aug", 31); daysInMonth.put("Sep", 30); daysInMonth.put("Oct", 31); daysInMonth.put("Nov", 30); daysInMonth.put("Dec", 31); for (String month : daysInMonth.keySet()) { output.printf("%s : %d%n", month, daysInMonth.get(month)); }
The previous code fragment prints:
Jan : 31 Feb : 28 Mar : 31 Apr : 30 May : 31 Jun : 30 Jul : 31 Aug : 31 Sep : 30 Oct : 31 Nov : 30 Dec : 31
Notice that the output has the months in the
correct chronological order because the entries
are kept in insertion order (change the map
to HashMap
or TreeMap
and see what happens).
Suppose you want to sort the entries by value
(number of days); neither Map
nor
Collections
provide this kind of
functionality.
It is (trivially) easy to get a sorted set of the number of days:
1. ask the map for its Collection of values 2. create a TreeSet from the values
Set<Integer> days = new TreeSet<Integer>(daysInMonth.values()); for (Integer day : days) { output.printf("%d%n", day); }
The previous code fragment prints:
28 30 31
which is the set of number of days in sorted order.
We can now use double nested traversal to print the months sorted by the number of days:
for each day d for each month m if m has d days print m and d end if end for end for
for (Integer day : days) { for (String month : daysInMonth.keySet()) { if (daysInMonth.get(month).equals(day)) { output.printf("%s : %d%n", month, day); } } }
The previous code fragment prints:
Feb : 28 --- Apr : 30 Jun : 30 Sep : 30 Nov : 30 --- Jan : 31 Mar : 31 May : 31 Jul : 31 Aug : 31 Oct : 31 Dec : 31
Notice that we have what is called a stable sort; all of the months with the same number of days are still in chronological order.
Download the program here: DayMonth.java
Some applications of maps arise where a key maps to a collection of values:
Maps with multiple values are sometimes called multimaps.
You can create your own multimap by creating a map of lists (or sets or maps depending on the application).
Map<String, List<Double>> grades = new HashMap<String, List<Double>>(); grades.put("cse00001", new ArrayList<Double>());
Account "cse00001"
maps to an empty list of
marks.
ePost stores marks for each assignment/test in a file that looks like:
cse00050 8 cse00003 6 cse00100 7.5
The accounts are not sorted, and accounts might be missing from a file (if the assignment/test was not submitted).
Write a program that merges an arbitrary number of ePost files into a format that can easily be imported into spreadsheet software.
Let's attempt a simpler problem: assume every student submits every assignment/test and that no student drops the course.
When you read in an account and a grade you add the grade to the end of the list associated with the account.
String acct; Double grade; // read in acct and grade here List<Double> acctGrades = grades.get(acct); if (acctGrades == null) { acctGrades = new ArrayList<Double>(); } acctGrades.add(grade); grades.put(acct, acctGrades);
Download the program here: MergeReport.java
Download the data files here: epost1.txt epost2.txt epost3.txt
You should attempt to solve the original problem where each epost file might be missing accounts.
When using multimaps, sometimes you will want to sort the entries by one or more of the values:
In these cases, it becomes more difficult to sort using the technique we saw earlier.
The basic idea is that you want to sort the key-value entries based on some aspect of the values.
Java provides a mechanism for sorting collections of objects based on specific criteria. The idea is to use an object that can compare entries to sort the collection.
Such an object needs to implement the
Comparator
interface.