Core Java. Lecture #7

Collections: Separation of interfaces and implementations

Collection Interfaces: Descendants of Collection

Iterable: an interface that can participate in for loop

Iterable<T> collection = ...
for (T e: collection) {
  ...
}

Iterable<T> collection = ...
Iterator<T> i = collection.iterator();
while (i.hasNext()) {
  T e = i.next();
  if (e...)
    i.remove();
}

ListIterator: extension for List

Collection Interfaces: Descendants of Map

Comparable and Comparator

public interface Comparable<T>{
/**
 * @param  o the object to be compared.
 * @return a negative integer, zero, or a positive integer as this object
 *         is less than, equal to, or greater than the specified object.
 */
 int compareTo(T o);
}

/*Applies if objects being compared
do not implement Comparable*/
public interface Comparator<T> {
  int compare(T o1, T o2);
}

Intermediate Conclusions

//IMMUTABLE
//Empty                   //From a single element
Collections.emptyList();   Collections.singletonList(o);
Collections.emptySet();    Collections.singleton(o);
Collections.emptyMap();    Collections.singletonMap(k,v);

Immutable collections of specified elements

//Of specified elements
List.of(a, b, c...);
Set.of(a, b, c...);
Map.of(k1, v1, k2, v2...);

Surrogate collections: (partial) protection when an object is published

Collections.unmodifiableList(List<? extends T> l);
Collections.unmodifiableSet(Set<? extends T> s);
Collections.unmodifiableMap(Map<? extends K,
                                ? extends V> s);
...

ArrayList the Great

List<String> list = new ArrayList<>();
list.add("foo"); list.add("bar"); list.add("baz");

Algorithmic properties of ArrayList

LinkedList

List<String> list = new LinkedList<>();
list.add("foo"); list.add("bar"); list.add("baz");

Algorithmic properties of LinkedList

Does anyone use LinkedList?

What if you still need Deque?

PriorityQueue

PriorityQueue<String> q = new PriorityQueue<>();
q.add("foo"); q.add("bar"); q.add("baz");

HashMap the Great

Map<String, Integer> map = new HashMap<>();
map.put("foo", 1); map.put("bar", 2); map.put("baz", 3);

Hash collisions

Map<String, Integer> map = new HashMap<>(); map.put("foo", 1); map.put("Aa", 2); map.put("BB", 3); If there are a large number of collisions on one cell, if the value implements Comparable, the linked list is replaced with a tree. Implement Comparable!!

LinkedHashMap

Map<String, Integer> map = new LinkedHashMap<>(); map.put("foo", 1); map.put("bar", 2); map.put("baz", 3); Maintains element insertion order. Good for LRU cache. Good for keeping key-value settings (e. g. stored in .properties file).

More variations on the hash table theme

TreeMap

Map<String, Integer> map = new TreeMap<>(); map.put("foo", 1); map.put("bar", 2); map.put("baz", 3); Red-black tree, keys are compared by Comparable or Comparator. If used as an ordinary Map is inferior to HashMap, Indispensable in cases where the key is known only approximately.

Sets

private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

Bitmap-based sets

Algorithms: sorting and shuffling

/*Implements Comparable*/
List<String> names = ...
Collections.sort(names);

/*We pass Comparator*/
List<Employee> staff = ...
Collections.sort(staff,
  Comparator.comparingLong(
    Employee::getSalary));

/*Sometimes we need to shuffle*/
List<Card> cards = ...
Collections.shuffle(cards);

/*Implements Comparable*/
String[] names = ...
Arrays.sort(names);

/*We offer Comparator*/
Employee[] staff = ...
Arrays.sort(staff,
  Comparator.comparingLong(
    Employee::getSalary));

/*There is no Arrays.shuffle!*/

Algorithms: binary search

List<Employee> staff = ...

Collections.sort(staff,
  Comparator.comparing(
    Employee::getName));

Employee p = ...

int i =
  Collections.binarySearch(
    staff, p,
    Comparator.comparing(
      Employee::getName));

Employee[] staff = ...

Arrays.sort(staff,
  Comparator.comparing(
    Employee::getName));

Employee p = ...

int i =
  Arrays.binarySearch(
    staff, p,
    Comparator.comparing(
      Employee::getName));

Also already implemented

Callbacks: before lambdas

public interface ActionListener {
  void actionPerformed(ActionEvent event);
}

// ----using----
String text = ...
new Timer(1000, new ActionListener(){
  @Override
  public void actionPerformed(ActionEvent e) {
    ... //'text' var is available here
    }
  });

Callbacks: Comparator

String[] friends = {"Peter", "Paul", "Mary"};

Arrays.sort(friends,
  new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
      return o1.length() - o2.length();
  }
});

Predicate

File[] hiddenFiles = new File(".").listFiles(
  new FileFilter() {
    public boolean accept(File file) {
      return file.isHidden();
    }
  }
);

Welcome lambda expressions!

//single-line
(String first, String second) ->
  first.length() - second.length()

//multi-line with int return
(String first, String second) -> {
  if (first.length() < second.length()) return -1;
  else if (first.length() > second.length()) return 1;
  else return 0;
}

//no-arg, void return
() -> System.out.println("Hello!");

Which of these are valid lambda expressions?

What can lambdas be assigned to?

//You don't need to specify the types of lambda arguments: type inference!
ActionListener = e -> {...}
Comparator<String> c = (s1, s2) -> s1.length() - s2.length();

Void-compatibility

final List<String> list = ...

//Predicate.test returns boolean
Predicate<String> p = s -> list.add(s);

//Consumer.accept returns void!
Consumer<String> c = s -> list.add(s);

Object is not a functional interface!

//will not compile
Object o = ()->{};

//Compiled!
Runnable r = ()->{};

//Also compiled
Object o = (Runnable) ()->{};

As a result we have

new Timer(100, new ActionListener(){
 @Override
 public void
   actionPerformed(ActionEvent e) {
     ...
   }
});

new Timer(100, e -> {...});

Arrays.sort(friends,
 new Comparator<String>() {
   @Override
   public int compare(
     String o1, String o2) {
    return o1.length()-o2.length();
 }
});

Arrays.sort(friends, (s1, s2)->
  s1.length() - s2.length());

Closures

void repeatMessage(String text, int delay) {
  ActionListener  listener = event -> {
    //text variable is accessible inside the lambda!
    System.out.println(text);
  }
  new Timer(delay, listener).start();

}

Effectively final only

int start = ...

for (int i = 0; i < count; i++) {
  ActionListener linstener = event -> {
    start--; //ERROR: Can't mutate captured value

    //ERROR: Cannot refer to changing i
    System.out.println(i);
  }
}

Method references: even shorter, even more efficient

event -> System.out.println(event)

System.out::println

(s1,s2)->s1.compareToIgnoreCase(s2)

String::compareToIgnoreCase

(x, y) -> Math.pow(x,y)

Math::pow

Three ways to define a Method reference

Constructor/Array Constructor Reference

IDE will help, but there is a difference!

obj = null;

//NPE on lambda invocation only!!
//obj must be effectively final!
doSmth(x -> obj.method(x));

//NPE here and now
//obj must not be effectively final
doSmth(obj::method)

Methods specially created to be method references

//Come on, is it hard to check for null??
Objects.isNull(Object obj)...
Objects.nonNull(Object ob)...


list.removeIf(Objects::isNull);

stream.filter(Objects::nonNull)...

Ready-made functional types

Combination of consumers

Consumer<String> foo = ...
List<String> list = ...

//Compound consumer sending
//object first in the first, then in the second
Consumer<String> bar = foo.andThen(list::add);

Functions

Composition of functions and identity

Operators

Composition of operators

Predicates

Predicate composition

Predicate<T> a = ...
Predicate<T> b = ...

a.and(b).negate(); // ! (a(x) & b(x)

//Double predicate (x,y)-> Objects.equals(x, y)
Objects::equals

//Single predicate y -> Objects.equals(x, y)
Predicate.isEqual(x)

Functional interfaces for primitive types

Functional interfaces for primitive types (continued)

Default Map interface methods

V computeIfAbsent(K key,
  Function<? super K, ? extends V> mappingFunction)

V computeIfPresent(K key,
  BiFunction<? super K, ? super V, ? extends V> remappingFunction)

V compute(K key,
  BiFunction<? super K, ? super V, ? extends V> remappingFunction)

V merge(K key, V value,
  BiFunction<? super V, ? super V, ? extends V> remappingFunction)

Comparators

@AllArgsConstructor
public class Person {
    @Getter
    private final String firstName;
    @Getter
    private final String lastName;
}
List<Person> people = new ArrayList<>();

Sort by last name

/*WRONG*/
Collections.sort(people,
 (p1, p2) ->
   p1.getLastName()
   .compareTo(
     p2.getLastName());
);

/*CORRECT*/
Collections.sort(people,
  Comparator.comparing
   (Person::getLastName));
);

Sort by last name, then by first name

//DON'T WRITE THIS HORRIBLE MESS
Collections.sort(people,
  (p1, p2) -> {
    int result = p1.getFirstName().compareTo(p2.getFirstName());
    if (result == 0) {
      result = p2.getLastName().compareTo(p2.getLastName());
    }
    return result;
  }
);

Correct:

Collections.sort(people,
  Comparator
    .comparing(Person::getLastName)
    .thenComparing(Person::getFirstName));
);

Also:

Comparator.comparing(keyExtractor, keyComparator)
Comparator.comparingInt/Double(...)
Comparator.reversed()
Comparator.nullsFirst/nullsLast(Comparator c)