Java:Language - Collections - Exercises

From Juneday education
Jump to: navigation, search

Common classes

We need something to work, so let's create a simple class representing a Contact.

Expand using link if you want a class to copy.

package se.juneday.domain;

import java.io.Serializable;

public final class Contact implements Serializable, Comparable<Contact>{

  private final String name;
  private final String email;
  private final String phone;
  
  public Contact(String name, String email, String phone){
    this.name = name;
    this.email = email;
    this.phone = phone;
  }

  public String name() { return name; }

  public String email(){ return email; }

  public String phone(){ return phone; }
  
  @Override
  public String toString(){
    return name + " " + email + " " + phone; 
  }
  
  @Override
  public int compareTo(Contact other){
    return this.name.compareTo(other.name);
  }
  
  @Override
  public boolean equals(Object other){
    if (other==null) {
      throw new NullPointerException("can't do equal on null");
    }
    if ( ! (other instanceof Contact) ) {
      throw new IllegalArgumentException("Can't only invoke equal on Contact instances");
    }
    Contact otherContact = (Contact) other;
    return name.equals(otherContact.name);
  }

  @Override
  public int hashCode(){
    return name.hashCode();
  }
}

You can download this file here: Contact.java

We need a class that can create Contact instances for us. You can use this class (or write your own):

Expand using link if you want a class to copy.

package se.juneday.util;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

import se.juneday.domain.Contact;

public final class Kreator {

  private static Random rand;
  static {
    initialise();
  }
  
  private static void initialise() {
    givenNames = Arrays.asList(
                               "Maria" ,
                               "Anna" ,
                               "Margareta" ,
                               "Elisabeth" ,
                               "Eva" ,
                               "Birgitta" ,
                               "Kristina" ,
                               "Karin" ,
                               "Elisabet" ,
                               "Marie" ,
                               "Ingrid" ,
                               "Christina" ,
                               "Linnéa" ,
                               "Marianne" ,
                               "Sofia" ,
                               "Kerstin" ,
                               "Lena" ,
                               "Helena", 
                               "Erik" ,
                               "Lars" ,
                               "Karl" ,
                               "Anders" ,
                               "Johan" ,
                               "Per" ,
                               "Nils" ,
                               "Jan" ,
                               "Carl" ,
                               "Mikael" ,
                               "Lennart" );
    familyNames = Arrays.asList(
                                "Johansson" ,
                                "Andersson" ,
                                "Karlsson" ,
                                "Nilsson" ,
                                "Eriksson" ,
                                "Larsson" ,
                                "Olsson" ,
                                "Persson" ,
                                "Svensson" ,
                                "Gustafsson" ,
                                "Pettersson" ,
                                "Jonsson" ,
                                "Jansson" ,
                                "Hansson" );
    rand = new Random();
  }

  private static List<String> givenNames;
  private static List<String> familyNames;

  public static Contact createContact() {
    String givenName = givenNames.get(rand.nextInt(givenNames.size()));
    String familyName = familyNames.get(rand.nextInt(familyNames.size()));
    
    return new Contact(givenName + " " + familyName,
                       givenName.toLowerCase() + "@" + familyName.toLowerCase() + ".com",
                      "" + rand.nextInt(1000000));
  }
  
}

You can download this file here: Kreator.java

Map exercises

We have two data files we need to join

Let's say we have data about books in two files, authors.csv and titles.csv. Both files contain comma separated values (CSV).

This is the authors.csv:

$ cat authors.csv 
Eva Holmquist,9789144117775
Lars Wiktorin,9789144120973
Lars Ahlin,9789144126531
Jonas Flodén,9789144130286

This is titles.csv:

$ cat titles.csv
Praktisk mjukvarutestning,9789144117775
Utveckling av IT-system,9789144120973
Principles of Wireless Communications,9789144126531
Essentials of Information Systems,9789144130286

Our job is to parse the files in Java and create a List<Book> where the book class looks like this:

class Book {
  private String isbn;
  private String title;
  private String author;

  public Book(String isbn, String title, String author) {
    this.isbn = isbn;
    this.title = title;
    this.author = author;
  }

  public String toString() {
    return new StringBuilder(title)
      .append(" by ")
      .append(author)
      .append(" with isbn: ")
      .append(isbn)
      .toString();
  }
}

Now, authors.txt only contain information about author and isbn (exactly one author per isbn, luckily for us). And titles.csv only contains information about titles and isbn (exactly one title per isbn, luckily for us).

So in order for us to create Books, we need to combine both files, since a Book has the following fields:

  • isbn
  • title
  • author

Your job is to read both files, and create Books with the combined data. You need to pair the lines in both files, by joining them on the isbn!

For instance, in authors.csv, we have:

Eva Holmquist,9789144117775

And in titles.csv, we have:

Praktisk mjukvarutestning,9789144117775

Since the isbn is the same for both lines, they represent a Book when combined:

Praktisk mjukvarutestning
Eva Holmquist
9789144117775

We'll give you some hints below.

To parse a CSV file with two values separated by comma on each line, you can use the following:

import java.nio.file.*;
...
...
for (String line : Files.readAllLines(Paths.get("fileName.csv")) ) {
  // First value:
  String first = line.split(",")[0];
  // Second value:
  String second = line.split(",")[1];
}

To store the data read from both files, we suggest that you use a java.util.Map<String, String> for each data. We suggest the following names for the two maps:

  • isbnToTile (contains isbn as keys, and titles as values)
  • isbnToAuthor (contains isbn as keys, and authors as values)

Now you can look up both title and author from an isbn!

To create a List<Book> you need the following for the constructor:

  • String isbn
  • String title
  • String author

Well, if you have two maps that go from isbn to either title or author, all you need to do to create the list of books is:

  • loop over the keys of one of the maps
    • use the keySet() method and a for-each-loop
  • for each key (which is an isbn), create a new Book
    • use the isbn loop variable as the first argument to the constructor
    • use the maps to look up title and author respectively for the second and third arguments to the constructor

Expand using link to the right to see a suggested solution.

import java.nio.file.*;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

public class BookJoin {
  static String authorsFile = "authors.csv";
  static String titlesFile = "titles.csv";
  public static void main(String[] args) {

    Map<String, String> isbnToAuthor = new HashMap<>();
    Map<String, String> isbnToTitle = new HashMap<>();

    try {
      for (String line : Files.readAllLines(Paths.get(authorsFile)) ) {
        isbnToAuthor.put(line.split(",")[1], line.split(",")[0]);
      }
    } catch (Exception e) {
      System.err.println("Error reading data: " + e.getMessage());
    }

    try {
      for (String line : Files.readAllLines(Paths.get(titlesFile)) ) {
        isbnToTitle.put(line.split(",")[1], line.split(",")[0]);
      }
    } catch (Exception e) {
      System.err.println("Error reading data: " + e.getMessage());
    }

    List<Book> books = join(isbnToTitle, isbnToAuthor);
    System.out.println(books);
  }

  private static List<Book> join(Map<String, String> titles,
                          Map<String, String> authors) {

    List<Book> books = new ArrayList<>();
    
    for (String isbn : titles.keySet()) {
      books.add( new Book(isbn, titles.get(isbn), authors.get(isbn)) ); 
    }
    return books;
  }
  
}
class Book {
  private String isbn;
  private String title;
  private String author;

  public Book(String isbn, String title, String author) {
    this.isbn = isbn;
    this.title = title;
    this.author = author;
  }

  public String toString() {
    return new StringBuilder(title)
      .append(" by ")
      .append(author)
      .append(" with isbn: ")
      .append(isbn)
      .toString();
  }
}

The CSV files:

$ for i in *.csv; do echo $i;cat $i;echo;done
authors.csv
Eva Holmquist,9789144117775
Lars Wiktorin,9789144120973
Lars Ahlin,9789144126531
Jonas Flodén,9789144130286

titles.csv
Praktisk mjukvarutestning,9789144117775
Utveckling av IT-system,9789144120973
Principles of Wireless Communications,9789144126531
Essentials of Information Systems,9789144130286

Bonus - Did you know?

In bash, if the files are sorted on the column that you want to join on (in our case, the isbn come in the same order in both files), you can do this:

$ join -t ',' -1 2 -2 2 -o 1.1,2.1,2.2 authors.csv titles.csv 
Eva Holmquist,Praktisk mjukvarutestning,9789144117775
Lars Wiktorin,Utveckling av IT-system,9789144120973
Lars Ahlin,Principles of Wireless Communications,9789144126531
Jonas Flodén,Essentials of Information Systems,9789144130286

The syntax for the join command means:

  • -t ',' use comma as separator
  • -1 2 -2 2 use second column from file one, and second column from file two
  • -o 1.1,2.1,2.2 Print the result in the order of file one column 1, file two column 1, file 2 column 2

Try it!

List exercises

Here's class with suggested suggested solutions to the exercises below: TryList.java

Create a list of 1000 contacts

Expand using link to the right to see a hint.

    ArrayList contacts = new ArrayList<>(nrContacts);

    for (int i=0; i<nrContacts; i++) {
      contacts.add(Kreator.createContact());
    }

Measure how long time it takes to sort a list

Write code to measure how long time it takes to sort a LinkedList and an ArrayList list with 1000 contacts.

Hint: check out currentTimeMillis

Expand using link to the right to see a hint.

    long start = System.currentTimeMillis();
    Collections.sort(contacts);
    long stop = System.currentTimeMillis();

    System.out.println("Sorting took " + (stop - start) + " milli seconds");

Increase the number of objects to create to 1000000 (one million), which you write like 1_000_000 in Java if you find that easier). How long time did it take to sort the list if it is a LinkedList and an ArrayList. If it takes less than 2 seconds to sort the list, increase the list size to 10 millions.

Expand using link to the right to see a hint.

sort       | 10000000 contacts | ArrayList | 7184 milli seconds
sort       | 10000000 contacts | LinkedList | 10457 milli seconds

Measure how long time it takes to remove elements

This time we should see how long time it takes to remove a Contact. Before we proceed we need to think a bit....creating 1 million (or 10 million ) Contacts will result in many Contacts having the same name, so we need to create a Contact that is unique and add that Contact at some position and then remove that Contact.

Expand using link to the right to see a hint.

  Contact contact = new Contact("LReallyoddname ThatsNotInTheList", "@", "1209");

How long time does it take to remove (individually):

  • an element in the middle of the list
  • the last element from the list
  • first element from the list?

Measure for both LinkedList and ArrayList.


Expand using link to the right to see what results we got.

remove     | at 0 | ArrayList | 160 milli seconds
remove     | at 5000000 | ArrayList | 86 milli seconds
remove     | at 9999997 | ArrayList | 0 milli seconds
remove     | at 0 | LinkedList | 0 milli seconds
remove     | at 5000000 | LinkedList | 431 milli seconds
remove     | at 9999997 | LinkedList | 0 milli seconds

Measure how long time it takes to add a Contact

Add three Contacts in the following position:

  • at the the first position
  • at the middle position
  • atthe end

Expand using link to the right to see what results we got.

add        | at 0 | ArrayList | 71 milli seconds
add        | at 5000000 | ArrayList | 0 milli seconds
add        | at 10000001 | ArrayList | 0 milli seconds
add        | at 0 | LinkedList | 0 milli seconds
add        | at 5000000 | LinkedList | 0 milli seconds
add        | at 10000001 | LinkedList | 0 milli seconds

Measure how long time it takes to find a Contact

Firstly we should iterate (using an Iterator over the list and find a Contact. How long time does it find a known object in a list? Let's find out. Add a unique Contact with a name in the middle of the list and Measure for both LinkedList and ArrayList.

Expand using link to the right to see a hint one how to use an Iterator.

    Iterator it = contacts.iterator();
    while (it.hasNext()) {
      Contact c = (Contact) it.next();
      if (c.equals(unique)) {
        break;
      }
    }

Expand using link to the right to see what results we got.

naive find | at 5000001 | ArrayList | 77 milli seconds
naive find | at 5000001 | LinkedList | 259 milli seconds

Now let's use the method binarySearch to find an element. We want the element to be somewhere in the middle so let's do rather naive trick to put a unique Contact (somewhere) in the middle:

  • sort the list
  • take the name, email and phone from the Contact in the middle
  • from those (name, email and phone) create a new Contact
  • put the new Contact in the same position as the middle contact
  • sort the list (since we replaced one Contact the list is most likely not sorted anymore)

Expand using link to the right to see what results we got.

find       | at 5003640 | ArrayList | 0 milli seconds | 6952 milli seconds sorting 
find       | at 5021693 | LinkedList | 670 milli seconds | 10413 milli seconds sorting

Finding an element in a sorted ArrayList is really quick. But the time to sort the list is slow. This is something to think about when you design your software.

Returning null from a method, or an empty list?

Often you are writing methods that return a List of some sort. Perhaps you are fetching some kind of objects from a database (or parsing them from JSON, or...) and putting them into a List of some type and return a reference to said List.

But, what to do if the fetch fails or is unable to provide the requested data?

Imagine, for instance that you have a method for getting a selection of objects according to some criteria. Could be something simple like, List<String> getNamesStaringWith(String start) . Using this method, the clients of the method (code which is calling the method) could request all names (as Strings) that start with some letter or prefix. But what should you return when there's no such requested names?

It might be tempting to return null. However, this is error prone. It puts a requirement on the calling code to check for null, and if it doesn't check for null, you'll have a nullpointer exception waiting to happen.

It is better to, in such cases, return an empty list.

One way to return an empty List<String> is to do return new ArrayList<String>(). However, this creates a new (empty) list each time this happens. What you can do instead, is to return the following:

return Collections.<String>emptyList();

The thing you gain from this, is that you are actually returning the same empty list every time, instead of a new empty list every time.

Calling code still might have to check whether the call succeeded, but instead of the special case null, the code gets more readable:

    String prefix = "von";
    List<String> nobles = getNamesStartingWith(prefix);
    System.out.println("Found " + nobles.size() + " names matching " + prefix); // this would crash if null was returned!
    if (nobles == Collections.EMPTY_LIST) {
      System.out.println("No nobles here.");
    } else {
      System.out.println(nobles);
    }

Your task is to create a class with a main method which fetches a List<String> with names, filtered by some prefix. Make sure that you have a long list of strings with various names. The prefix should come from the first argument to your program.

If no names match the prefix (i.e. no names start with the prefix given as argument), you should return Collections.<String>emptyList();. Your main method should handle this case and print some explanation about the prefix not found in the list of names. If the prefix indeed was found, the method should return a list of all names starting with the prefix.

Example run could be:

$ java FilterNames Zip
No names starts with Zip. Sorry.
$ java FilterNames B
Names starting with B:
["Beethoven", "Bach", "Barry", "Berlioz", "Bártok", "Brecht"]

Expand using link to the right to see a suggested example solution.

import java.util.Collections;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.stream.Collectors;

public class FilterNames {

  private static List<String> names = Arrays.asList("Mozart", "Beethoven", "Bach", "Berlioz",
                                                    "Bártok", "Händel", "Brecht", "Ravel", "Chopin",
                                                    "von Bingen", "Rachmaninov", "Stravinsky", "Rehnström",
                                                    "Sibelius", "Telemann", "Gesualdo");
  public static void main(String[] args) {
    if (args.length != 1) {
      System.err.println("java FilterNames <prefix>");
      System.err.println(" where <prefix> is the start of names to filter on");
      System.exit(1);
    }
    String prefix = args[0];
    List<String> result = getNamesStartingWith(prefix);
    if (result == Collections.EMPTY_LIST) {
      System.out.println("Sorry. No names start with " + prefix);
    } else {
      System.out.println("Names starting with " + prefix + ":");
      System.out.println(result);
    }
  }

  private static List<String> getNamesStartingWith(String prefix) {
    List<String> results = names.stream().filter(s -> s.startsWith(prefix)).collect(Collectors.toList());
    if (results.size() == 0) {
      return Collections.<String>emptyList();
    }
    return results;
  }
}

Note that the expression names.stream().filter(s -> s.startsWith(prefix)).collect(Collectors.toList()); evaluates to an empty list, if it can't collect any matching names. But it is a new empty list, but not the same as Collections.<String>emptyList();.

Your code would work as well without Collections.<String>emptyList();, but then you would have had to change your if-statement in main to check for result.size() rather than checking for == with Collections.EMPTY_LIST. That would of course work well too, but we wanted you to try out some code to handle the case when you get the empty list from Collection.

The code we wanted you to try out and get used to, was in the main method:

    List<String> result = getNamesStartingWith(prefix);
    if (result == Collections.EMPTY_LIST) {
      System.out.println("Sorry. No names start with " + prefix);
    } else {
      System.out.println("Names starting with " + prefix + ":");
      System.out.println(result);
    }

An example which perhaps would be easier to understand, could be the case where you have a class with a list as an instance variable.

If this list can be empty or non-empty, you could initialize it to an empty list. But, the empty list you get from Collections.emptyList(), is immutable, so you cannot add stuff to it.

So how would you use the empty list as an instance variable then?

If your class has an accessor method which returns a copy of the instance variable list (which could be empty) you could implement the accessor method like this:

public class Team {
  private List<Member> members; // null until we've added some members
  private String name; // team name
  public Team(String name) {
    this.name = name;
  }

  public void addMember(Member m) {
    if (members == null) {
      members = new ArrayList<>();
    }
    members.add(m);
  }

  public List<Member> members() {
    if (members == null) {
      return Collections.<Member>emptyList();
    }
    return Collections.unmodifiableList(members); // members are immutable, so is this list
  }
}

The above example perhaps shows the difference between returning null as the result of calling members() on a Team without any members.

Instead of returning null, it returns an empty list. This empty list is unmodifiable (the List returned from Collections.emptyList() always is).

If you didn't check if the list members was null, you could have returned null as a sign for a team without any members. This is considered bad style, and instead you should return the empty list from Collections.emptyList(). This is actually exactly what this list is for - to signify an empty list, so that we don't have to use null for that.

Map

Here's class with suggested suggested solutions to the exercises below:: TryMap.java and UseMap.java

Create a map with Contacts

Create 1000 Contacts as you did in the previous exercises and put them in a map. Use the Contact's name as key and the Contact itself as value. How many Contacts do you think will be in the map?

Expand using link to the right to see a hint.

    int nrContacts = 1000;

    Map<String, Contact> contacts = new HashMap<>();
    System.out.print("Creating map of Contacts:");
    for (int i=0; i<nrContacts; i++) {
      Contact c = Kreator.createContact();
      contacts.put(c.name(),c);
    }
    System.out.println(" " + contacts.size() + " contacts in the map");

Executing the above gives uss (the numbers will change due to the randomness in the Kreator class):

Creating map of Contacts: 373 contacts in the map

Why 373 when we put 1000? Well, a Map contains only one value per key.

Get one element from the map using a key

Add 10 elements (instead of 1000). Add one manually created Contact (not using Kreator). Use the name you gave the Contact you added to get the Contact from the map and print it out.

Expand using link to the right to see a hint.

    // Add a user to the map - so we know that the key has acorresponding Contact
    Contact c = new Contact("Henrikard", "henrikard@juneday.se", "3276234");
    contacts.put(c.name(), c);
    System.out.println(" Get Henrikard: " + contacts.get("Henrikard"));

When executin the above we will see:

 Get Henrikard: Henrikard henrikard@juneday.se 3276234

Get one element from the map using a key (that does not exist in the map)

Expand using link to the right to see a hint.

    // Get one element from the map using a key (that does not exist in the map)
    System.out.println(" Get Ozzy Osbourne: " + contacts.get("Ozzy Osbourne"));

When executin the above we will see:

 Get Ozzy Osbourne: null

Get all the elements from the map

Get and print all the elements in the map above.

Expand using link to the right to see a hint.

    // Get all the values from the map
    Collection<Contact> contactCollection = contacts.values();
    for (Contact con : contactCollection) {
      System.out.println(" * " + con);
    }

Get all the keys from the map

Get and print all the keys in the map above.

Expand using link to the right to see a hint.

    System.out.println("Keys");
    Set<String> keys = contacts.keySet();
    for (String key : keys) {
      System.out.println(" * " + key);
    }

Get all the keys and values from the map

Using the method entrySet() you can get a Set of Entry objects. Entry is declared in Map you therefore need to write Map.Entry.

Expand using link to the right to see a hint.

    System.out.println("Entries");
    Set<Map.Entry<String,Contact>> entries = contacts.entrySet();
    for (Map.Entry<String,Contact> contactEntry : entries) {
      System.out.println(" * " + contactEntry.getKey() + ":" + contactEntry.getValue());
    }

Create Contacts and use integer as key

Let's say you would like to map a Contact with a room number. If the room numbers start with 1 and go up to 100 and ArrayList will be useful. But if you have integer numbers with not in sequence and ranging from 1 to 100000 it might be more useful to map a Contact with an integer. So let's do this.

Add 10 Contacts to a map and map with an integer. Get the keys from the map and print them.

Expand using link to the right to see a hint.

    Map<Integer, Contact> contactsIC = new HashMap<>();
    System.out.print("Creating map <I,C> of Contacts:");
    for (int i=0; i<nrContacts; i++) {
      contactsIC.put(i,Kreator.createContact());
    }
    System.out.println(" " + contactsIC.size() + " contacts in the map");

    // ... and get all the keys from the map
    System.out.println("Keys");
    Set<Integer> keysI = contactsIC.keySet();
    for (Integer key : keysI) {
      System.out.println(" * " + key);
    }

Measure how long time it takes to find an element

Write a class that stores as many Contacts as you do above, but this time in a Map and with HashMap as the concrete class. Use the Contact's name as key and the Contact itself as value.

Expand using link to the right to see a hint.

package se.juneday.trials;

import java.util.HashMap;
import java.util.Map;
import java.util.Collections;

import se.juneday.domain.Contact;
import se.juneday.util.Kreator;

public class TryMap {

  private static final int nrContacts = 10_000_000;

  private static void findTest(Map<String, Contact> contacts, Contact contact) {
    int size = contacts.size();
    contacts.put(contact.name(), contact);

    long start = System.currentTimeMillis();
    contacts.get(contact.name());
    long stop = System.currentTimeMillis();

    System.out.println("Finding a Contact out of " + 
                       size + " contacts by name " +
                       " (" + contacts.getClass().getName() + ")"
                       + " took " + (stop - start) + " milli seconds");
  }
  
  public static void main(String[] args) {

    Map<String, Contact> contacts = new HashMap<>();
    
    System.out.print("Creating map of Contacts:");
    for (int i=0; i<nrContacts; i++) {
      Contact c = Kreator.createContact();
      contacts.put(c.name()+"_"+i, c); // We need them contact names to be unique
    }
    System.out.println(" " + contacts.size() + " contacts created");

    Contact contact = new Contact("Reallyoddname ThatsNotInTheList", "@", "1209");
    findTest(contacts, contact);
    
    System.out.println("Tests finished");
  }
  
}

Expand using link to the right to see a hint.

$ javac se/juneday/domain/Contact.java se/juneday/util/Kreator.java  se/juneday/trials/TryMap.java  && java -ea se.juneday.trials.TryMap
Creating map of Contacts: 10000000 contacts created
Finding a Contact out of 10000000 contacts by name  (java.util.HashMap) took 0 milli seconds
Tests finished

How long time did it take to find a Contact in a List (both LinkedList and ArrayList) using Java's binarySearch? Compare this to finding an element with Map

Expand using link to the right to see a hint.

These are the measured times we got:

  • ArrayList: 0 milli seconds
  • LinkedList: 670 milli seconds
  • HashMap: 0 milli seconds

Where to go next

The previous page contains the videos and examples on Collections and Maps.

The next page is not decided yet and leads nowhere.

The TOC (Table of Contents) goes to More_programming_with_Java#Java_Language for now.

« PreviousBook TOCNext »