Goals for Today

• Understanding how to use the Java Collections Framework
• Understanding Iterators and Iterable
• All of this from the users perspective
• The rest of the semester will be from the providers perspective

Collections

• Iterable
• Collection
• Set
• List
• Queue
• Deque

Collection Interface

• No direct implementations.
• Methods make no assumptions about the ordering of the elements.

• Why might we declare a variable as type “Collection”?

  public static someMethod(Collection<String> strings) {
      // do some stuff
  }

The Value of Interfaces

Why would we ever do this…

Queue<String> queue = new LinkedList<>();

// now work with queue to solve a problem.

Instead of this…

LinkedList<String> queue = new LinkedList<>();

// now work with the queue to solve a problem.

given that we have strictly less functionality to work with in the first example?

Socrative: Using Collections Effectively

Let’s say we want a method that returns an ArrayList with all duplicate elements removed. This seems reasonable:

 public static ArrayList<String> noDuplicates(ArrayList<String> items) {
    
    ArrayList<String> result = new ArrayList<String>();
    
    for (String item : items) {
      
      if (!result.contains(item)) {
        result.add(item);
      }
      
    }
    return result;
  }

Is this Correct?

How long would you expect it to run if items contains 1000000 distinct items?

A. Yes, around .01s

B. Yes, around 1s

C. Yes, more than a minute.

D. No, around .01 s

E. No, around 1s

F. No, more than a minute.

A better implementations…

public static ArrayList<String> noDuplicates(ArrayList<String> items) {
  return new ArrayList<String>(new HashSet<String>(items));
}

Or, if you prefer:

public static ArrayList<String> noDuplicates(ArrayList<String> items) {
  HashSet<String> setVersion = new HashSet<>(items);
  ArrayList<String> noDups = new ArrayList<>(setVersion);
  return noDups;
}

Warning: order of the items will not be retained unless you use a LinkedHashSet.

Iterable/Iterator

Collection extends Iterable…

• Iterable
• Iterator

• Iterators are the magic behind for-each loops:

  for (String s : someCollection) {
     System.out.println(s);
  }

  Is (pretty much) just shorthand for:

  Iterator<String> it = SomeCollection.iterator();
  String s;
  while(it.hasNext()) {
    s = it.next();
    System.out.println(s);
  }

• This would also work, but is terrible:

     Iterator<String> it = SomeCollection.iterator();
     try {
         while (true) {
           String s = it.next();
           System.out.println(s);
         }
     } catch (NoSuchElementException ex) {
     }

• One more option, using a lambda function:

  Iterator<String> it = SomeCollection.iterator();
  it.forEachRemaining((e) -> System.out.println(e));

Socrative Quiz

Fill in the blanks

The Set class implements the          interface which includes the          method.

When that method is called, it returns an object that implements the          interface.

That object provides the          method.

A. Iterator

B. next

C. Iterable

D. iterator

DON’T USE ITERATORS DIRECTLY!

• Iterators (mostly) exist to support for-each loops.
• Only a small number of scenarios where it makes sense to use them directly:
  • Removing during iteration.
  • Some classes provide more than one iterator, but there can be only one iterator method.

• This doesn’t work:

  Set<String> strs = new HashSet<>();
  strs.add("");
  strs.add("B");
  for (String s : strs) {
    if (s.isBlank()) {
      strs.remove(s);   // concurrentModificationException!!!!
    }
  }

• This does:

  Set<String> strs = new HashSet<>();
  Iterator<String> it = strs.iterator();
  
  while(it.hasNext()) {
    String s = it.next();
    if (s.isBlank()) {
      it.remove();       // Safely removes the most recently accessed item.
    }
  }

Maps

• HashMap, TreeMap
• Also called “Dictionaries” or “Associative Arrays”.
• A Map “maps” from Keys to Values, which may or may not be of the same type.
• Maps are part of the Java Collections framework, but do not implement Collection or Iterable.
• HashMap - More efficient (on average).
• TreeMap - Orders items according to the keys.

HashMap Demo

import java.util.HashMap;
import java.util.Scanner;


public class HashMapDemo {

  public static void main(String args[]) {
    HashMap<String, String> eDirectory;
    Scanner kb = new Scanner(System.in);
    String key;

    eDirectory = new HashMap<String, String>();

    eDirectory.put("bernstdh", "David Bernstein");
    eDirectory.put("duanzx", "Zhuojun Duan");
    eDirectory.put("spragunr", "Nathan Sprague");

    System.out.print("Enter an eid: ");
    key = kb.nextLine();
    System.out.println(eDirectory.get(key));

  }

}