Java:Language - Collections

From Juneday education
Jump to: navigation, search

Introduction

This chapter (exercises are on our TODO list!) introduces some of the interfaces and classes from the Java Collections API (plus the Map interface and some implementations).

Often you have a bunch of objects (object references, really) that you want to lump together and treat as a collection of stuff of the same type. For this, you can use a plain old array. But arrays are limited (they lack methods and are not really type safe, like the generic collection classes). You have probably used, or at least seen classes such as ArrayList which we typically access via the interface List.

Lists

A List is very like an array, but it is a fully featured object with a generic type and useful methods (described in the List interface). This is typically how we use a list of String references:

// Get a reference to a list of Strings with names from some method:
List<String> names = getListOfNames();
// Iterate over each name in the list, using the forEachLoop:
for (String name : names) {
  // Do something with each name, like print it or something else
  System.out.println(name);
}

// Somewhere we have a method which creates the list of names (strings):
public List<String> getListOfNames() {
  List<String> names = new ArrayList<>(); // we could also use LinkedList<>, for instance
  names.add("Henrik");
  names.add("Rikard");
  return names;
}

You have probably seen similar code in oencur exercises and assignments of the Programming with Java book.

Here's a slightly more complicated program utilizing lists to encode/decode an input string with the ROT13 substitution cipher:

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class Rot13 {

  static List<Character> alphabet;  
  static List<Character> cipher;
  static {
    alphabet = new ArrayList<>();
    for (char ch = 'a'; ch <= 'z'; ch++) {
      alphabet.add(ch);
    }
    cipher = new ArrayList<>(alphabet);
    Collections.rotate(cipher, 13);
    
  }
  
  static void usage() {
    System.err.println("USAGE java Rot13 string");
    System.exit(1);
  }
  
  public static void main(String[] args) {
    String input = "";
    String direction = "";
    if (args.length != 1) {
       usage();
    }
    input = args[0];
    String result = "";
    result = encode(input);
    System.out.println("Result: " + result);
    System.out.println(alphabet);
    System.out.println(cipher);
  }
  
  static String encode(String input) {
    char[] result = new char[input.length()];
    for (int i = 0; i < input.length(); i++)  {
      // translate the current character to its sipher equivalent
      if (cipher.contains(input.charAt(i))) {
        result[i] = cipher.get(alphabet.indexOf(input.charAt(i)));
      } else {
        result[i] = input.charAt(i);
      }
    }
    return new String(result);
  }
}

The program makes use of two lists of characters. One with the English alphabet plus space, and one with the previous list rotated 13 steps:

[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z]
[n, o, p, q, r, s, t, u, v, w, x, y, z, a, b, c, d, e, f, g, h, i, j, k, l, m]

The program takes one argument, a string to be either encoded or decoded (the cipher is symmetric, so it works both ways). To encode the input string, we simply get the index of each character from the alphabet list, and use that index to get the character from the cipher on the same index in the cipher list. These characters are combined to the result string.

Example run:

$ javac Rot13.java && java Rot13 'all work and no play makes henrik a dull boy'
Result: nyy jbex naq ab cynl znxrf uraevx n qhyy obl
$ javac Rot13.java && java Rot13 'nyy jbex naq ab cynl znxrf uraevx n qhyy obl'
Result: all work and no play makes henrik a dull boy

# Running it twice gives back the same string:
$ javac Rot13.java && java Rot13 "$(java Rot13 'all work and no play makes henrik a dull boy'|head -1|cut -d ':' -f2|cut -d ' ' -f2-)"
Result: all work and no play makes henrik a dull boy

A slightly more object oriented version

The version above isn't very object oriented (not at all in fact), so for completeness we'll show you an object oriented version. Having the classes Encrypter and Decrypter allows you to re-use the components. Note that Rot 13 isn't really encryption, however, it is just here for fun and to demonstrate some things you can do with lists!

// Encrypter.java:
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class Encrypter {

  private String plainText;

  static List<Character> alphabet;  
  static List<Character> cipher;

  static {
    alphabet = new ArrayList<>();
    for (char ch = 'a'; ch <= 'z'; ch++) {
      alphabet.add(ch);
    }
    cipher = new ArrayList<>(alphabet);
    Collections.rotate(cipher, 13);
    
  }
  
  public Encrypter(String text) {
    this.plainText = text;
  }

  public String encrypt() {
    char[] result = new char[plainText.length()];
    for (int i = 0; i < plainText.length(); i++)  {
      // translate the current character to its sipher equivalent
      if (cipher.contains(plainText.toLowerCase().charAt(i))) {
        result[i] = cipher.get(alphabet
                               .indexOf(plainText.toLowerCase().charAt(i)));
      } else {
        result[i] = plainText.charAt(i);
      }
    }
    return new String(result);    
  }
}

// Decrypter.java:
public class Decrypter {

  private String encrypted;
  
  public Decrypter(String encrypted) {
    this.encrypted = encrypted;
  }

  public String decrypt() {
    return new Encrypter(encrypted).encrypt();
  }
  
}

//Rot13vOO:
public class Rot13vOO {
  public static void main(String[] args) {
    if (args.length != 2 ||
        !args[0].equals("-e") && !args[0].equals("-d")) {
      System.err.println("Usage:");
      System.err.println("java Rot13vOO -<option> \"(lower case) text\"");
      System.err.println("  -e\tEncrypt text");
      System.err.println("  -d\tDecrypt text");
      System.exit(1);
    }

    String mode = args[0];
    String text = args[1];
    String result = "";

    switch (mode) {
    case "-e":
      Encrypter enc = new Encrypter(text);
      result = enc.encrypt();
      break;
    case "-d":
      Decrypter dec = new Decrypter(text);
      result = dec.decrypt();
      break;
    default:
      assert false : "Option parse error";
    }

    System.out.println(result);

  }
}

Example runs:

$ java Rot13vOO 
Usage:
java Rot13vOO -<option> "(lower case) text"
  -e	Encrypt text
  -d	Decrypt text
$ javac Rot13vOO.java && java Rot13vOO -d "henrik och rikard"
uraevx bpu evxneq
$ javac Rot13vOO.java && java Rot13vOO -d "uraevx bpu evxneq"
henrik och rikard
$ java Rot13vOO -d "$(java Rot13vOO -e "henrik och rikard")"
henrik och rikard

Iterating over a List

There are three ways to iterate over a List (that we can think of):

  • Using a for-each-loop
  • Using a for loop over the indices from 0 to length() -1
  • Using an Iterator (like a ListIterator for instance)

Here's code showing each of them:

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

public class ListLoops {
  public static void main(String[] args) {
    List<String> names = new ArrayList<>(Arrays.asList(args));
    // Loop through the list and print names
    // 1. For-each-loop
    for (String name : names) {
      System.out.println("Name: " + name);
    }
    // 2. Using index and classic for loop
    for (int i = 0; i < names.size(); i++) {
      System.out.println("Name [" + i + "]: " + names.get(i));
    }
    // 3. Using a ListIterator
    for (ListIterator<String> it = names.listIterator(); it.hasNext(); ) {
      System.out.println("Next name: " + it.next());
    }
  }
}

Example run:

$ javac ListLoops.java && java ListLoops henrik rikard juho urban aida
Name: henrik
Name: rikard
Name: juho
Name: urban
Name: aida
Name [0]: henrik
Name [1]: rikard
Name [2]: juho
Name [3]: urban
Name [4]: aida
Next name: henrik
Next name: rikard
Next name: juho
Next name: urban
Next name: aida

Removing elements from a List while iterating over it

There is only one safe way to remove elements from a list while iterating over it, and that is to use an iterator (like ListIterator, for instance).

All other ways have unpredictable (even undefined) buggy behavior, because you are modifying the very same list you are looping over. Removing an element changes the index of every element after it, which surely is a problem. Removing an element using the List's own remove() method while iterating over a list using an iterator, screws up the iterator behavior (it messes up the behavior of the next(), previous() and hasNext() etc methods).

The remove() method of iterators take special care to keep the logic and semantics of the next() etc methods, even after it just removed an element.

Note that you cannot call remove() on an iterator before you have called next() or previous()!

Here's code showing you how to remove an element from a list while you are iterating over the very same list:

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

public class ListRemove {
  public static void main(String[] args) {
    List<String> names = new ArrayList<>(Arrays.asList(args));
    // Remove all names starting with "rik", Using a ListIterator
    for (ListIterator<String> it = names.listIterator(); it.hasNext(); ) {
      String currentName = it.next();
      if (currentName.toLowerCase().startsWith("rik")) {
        System.out.println("Removing: " + currentName);
        it.remove();
      }
    }
    System.out.println("The resulting list:");
    for (String name : names) {
      System.out.println(name);
    }
  }
}

Example run:

$ javac ListRemove.java && java ListRemove henrik rikard juho urban aida Rikard Rikardo RikaBarnLekaBäst
Removing: rikard
Removing: Rikard
Removing: Rikardo
Removing: RikaBarnLekaBäst
The resulting list:
henrik
juho
urban
aida

Java 8 version, using streams and stuff:

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

public class ListRemoveJava8 {
  public static void main(String[] args) {
    List<String> names = new ArrayList<>(Arrays.asList(args));
    // Filter on all names not starting with "rik"
    names = names
      .stream()
      .filter(s -> ! s.toLowerCase().startsWith("rik"))
      .collect(Collectors.toList());
    System.out.println("The resulting list:");
    for (String name : names) {
      System.out.println(name);
    }
  }
}

Example run:

$ javac ListRemoveJava8.java && java ListRemoveJava8 henrik rikard juho urban aida Rikard Rikardo RikaBarnLekaBäst
The resulting list:
henrik
juho
urban
aida

Moving on

Now, there are more types of collections than those described by the List interface. Next, we'll look at some of those.

Sets

Basic usage of Set

If you have a collection of objects where every object (as identified by the hashCode/equals contract) is a member only once (no duplicates are allowed), you can use a Set, which is another interface in the collections API. There are, as with List more than one implementation of the Set interface. If you want an unordered set, you can use a HashSet. If you want an ordered set (where the elements retain their insert-order), you can use a LinkedHashSet. If you need a set which keeps its elements ordered according to their natural order (they implement Comparable or you provide a Comparator for the order when you create the set), you can use a TreeSet.

As when dealing with lists, you should use the interface type Set<T> when programming with sets:

Set<String> userNames = new HashSet<>(); // usernames must be unique, but the order is not important
userNames.add("xfrobr");
userNames.add("xshenc");

At times you need to make sure your collection doesn't contain duplicates, use a Set!

Mathematical set operations on Sets

Taken from Oracle's tutorial:

Set<Type> union = new HashSet<Type>(s1);
union.addAll(s2);

Set<Type> intersection = new HashSet<Type>(s1);
intersection.retainAll(s2);

Set<Type> difference = new HashSet<Type>(s1);
difference.removeAll(s2);

Examples:

If we have the Set s1 with elements {1, 2, 3, 4, 5}, and Set s2 with elements {3, 4, 5, 6, 7}, then the union of s1 and s2 means all the elements together (but no duplicates, because the result is a Set): {1, 2, 3, 4, 5, 6, 7}.

The intersection of s1 and s2 means the elements they have in common, so {3, 4, 5}.

The difference of s1 and s2 means the elements unique to s1 (remove all elements from s1 that are present in s2), so {1, 2}.

The same example in code:

import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;

public class SetOperations {
  public static void main(String[] args) {
    Set<Integer> s1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
    Set<Integer> s2 = new HashSet<>(Arrays.asList(3, 4, 5, 6, 7));
    Set<Integer> union = new HashSet<>(s1);
    union.addAll(s2);

    Set<Integer> intersection = new HashSet<>(s1);
    intersection.retainAll(s2);

    Set<Integer> difference = new HashSet<>(s1);
    difference.removeAll(s2);

    System.out.println("s1: " + s1);
    System.out.println("s2: " + s2);
    System.out.println("union: " + union);
    System.out.println("intersection: " + intersection);
    System.out.println("difference: " + difference);
  }
}

/*
$ javac SetOperations.java && java SetOperations
s1: [1, 2, 3, 4, 5]
s2: [3, 4, 5, 6, 7]
union: [1, 2, 3, 4, 5, 6, 7]
intersection: [3, 4, 5]
difference: [1, 2]
*/

Maps

At other times, you need a collection of key-value pairs. This is very common, actually. For this, you use a map, described by the Map interface. In a map, the keys are unique, so that you only have one key-value pair per key. So internally, a Map uses a Set for its keys.

You can think of a map as an oracle, or a dictionary which can store key-value pairs in a way so that you later can retrieve the value if you know only the key. This is useful for lookup objects, where you have a bunch of objects with keys representing the objects and you want to store them together with their respective key:

Map<String, User> usersByUserName = new HashMap<>();
usersByUserName.put("xfrobr", new User("Rikard", "xfrobr", "rikard.froberg@some.mail.se");
usersByUserName.put("xshenc", new User("Henrik", "xshenc", "henrik.sandklef@some.mail.se");
// Later, you have the userName and want to get the corresponding user object:
User aUser = usersByUserName.get("xfrobr"); // will get the correct user from the map

There are a few different implementations of the Map interface. One thing that separates some of the implementations, is the way the key set is implemented. If the keys are stored in no particular order, use a HashMap. If the keys are stored in the same way objects are inserted, use a LinkedHashMap. If you want the map to maintain its keys by their natural order, use a TreeMap. These differences are useful when you iterate over each key in the map, and the order of said keys are important to you (or not).

Wrapping it up: Using List, Set, Map, Collections

To wrap it up, here's an example program which calculates the character frequency of all characters of the argument to the program:

import java.util.Arrays;
import java.util.Map;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
import java.util.TreeMap;
import java.util.Collections;

public class CharacterFrequency {
  public static void main(String[] args) {

    if (args.length != 1) {
      System.err.println("USAGE: java CharacterFrequency string");
      System.exit(1);
    }

    // A set for unique chars in args[0]
    Set<Character> uniqueChars = new HashSet<>();
    // Create a list of all characters in args[0]
    List<Character> chars = new ArrayList<>();

    // Populate the list and set
    for (char ch : args[0].toLowerCase().toCharArray()) {
      chars.add(ch);
      uniqueChars.add(ch);
    }
    
    // Create a map <Character, Integer> with the frequencies
    Map<Character, Integer> frequency = new TreeMap<>();
    // Create a map <Integer, List<Character>> with the top list of frequencies
    Map<Integer, List<Character>> topList = new TreeMap<>();

    // Populate the maps
    for (Character ch : uniqueChars) {
      int freq = Collections.frequency(chars, ch);
      frequency.put(ch, freq);
      if (! topList.containsKey(freq)) {
        topList.put(freq, new ArrayList<>());
      }      
      topList.get(freq).add(ch);
    }
    
    System.out.println("Frequencies by character: " + frequency);
    System.out.println("Frequencies by frequence: " + topList);
  }
}

The program creates a List<Character> from the argument in arg[0], and a Set<Character> with all characters (to create a unique collection of the characters). Next, the program creates two maps. One with a character key and a frequency int as the value, and one with an integer key (the frequency) and a list of all characters for the frequency as the value.

The maps are populated in a loop over the unique characters. To calculate the frequency of a character in the list of all characters, we use the Collections.frequency(List, Element) method. To populate the other map (the one with frequency -> character list key-values), we check if a frequency is already present. If not, we put the frequency with an empty list of characters as value. Then, the character is added to this list.

Finally, we print both maps to standard out as the report for the argument input.

Example run:

$ javac CharacterFrequency.java && java CharacterFrequency 'The frequency and disjoint algorithms test some aspect of the composition of one or more Collections'
Frequencies by character: { =15, a=3, c=5, d=2, e=10, f=3, g=1, h=3, i=6, j=1, l=3, m=4, n=6, o=13, p=2, q=1, r=4, s=7, t=9, u=1, y=1}
Frequencies by frequence: {1=[g, j, q, u, y], 2=[d, p], 3=[a, f, h, l], 4=[m, r], 5=[c], 6=[i, n], 7=[s], 9=[t], 10=[e], 13=[o], 15=[ ]}

Other collection types

  • Stack TODO
  • Vector TODO
  • Queue TODO

Links

Exercises

See "Where to go next" below.

Lectures (videos, lecture presentaion, etc)

Further reading

Where to go next

The next page contains some exercises on Collections and Maps.

The previous page goes to More_programming_with_Java#Java_Language for now, which is also true for the TOC (table of contents).

« PreviousBook TOCNext »