Recap

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.

Days Per Month

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));
}

Days Per 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).

Sorting by Values

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);
}

Sorting by Values

The previous code fragment prints:

28
30
31

which is the set of number of days in sorted order.

Sorting by Values

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);
      }
   }
}

Sorting by Values

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

Maps with Multiple Values

Some applications of maps arise where a key maps to a collection of values:

• online shopping: item maps to price, ratings, manufacturer, etc.
• book index: index item maps to multiple page numbers
• registrar's database of students: student number maps to name, address, courses taken, grades, etc.
• CSE1020: CSE accounts maps to grades for each test

Maps with multiple values are sometimes called multimaps.

Maps with Multiple Values

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.

Maps with Multiple Values

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.

Maps with Multiple Values

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

Maps with Multiple Values

You should attempt to solve the original problem where each epost file might be missing accounts.

Sorting and Multiple Values

When using multimaps, sometimes you will want to sort the entries by one or more of the values:

• online shopping: item maps to price, ratings, manufacturer, etc.
  • sort by price, ratings, or manufacturer
  • sort by price, then ratings, then manufacturer

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.

Sorting and Multiple 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.