Class4.md

title: IST-4-JAV Java Programming
subtitle: Class 4 - New heights
author: Alice BRENON `<alice.brenon@liris.cnrs.fr>`
date: 2021-10-19
header-includes:
	\usepackage{fdsymbol}
	\usepackage{textgreek}
	\usepackage{bclogo}
	\usepackage{hyperref}
	\usepackage{color}
	\definecolor{yellow}{RGB}{255, 127, 0}
	\definecolor{greyblue}{RGB}{58, 103, 183}
	\hypersetup{
		colorlinks,
		linkcolor = yellow,
		urlcolor = greyblue
	}
	\usetheme{Frankfurt}
	\usecolortheme{seahorse}

Advanced Objects

Enumerations

Need

class PureBreedCat extends DomesticCat {
	String breed;
	…
}

String ?

1. for user: what are the possible values ?
2. possible errors (case, typos…)
3. need to validate input
4. (\Rightarrow what to do with unexpected values ?)

\Rightarrow type too "large"

A possible solution

:::columns ::::{.column width=40%}

need a finite number of values that are

• unique
• easy to compare
• associated to names

\Rightarrow constants of any integral type will do !

:::: ::::{.column width=60%}

final static byte SIAMESE = 0;
final static byte CHARTREUX = 1;
final static byte SAVANNAH = 2;
…

:::: :::

\vspace{0.5cm}

• 1 and 2 are fixed !
• 3 and 4 remain : (

The enum types

• fixed set of symbolic constants
• introduced by enum instead of class
• names separated by , (ended by ;)
• it's a class like any other ! (fields, methods)

enum CatBreed {
	SIAMESE, CHARTREUX, SAVANNAH
}

CatBreed breed = CatBreed.SIAMESE;
breed == CatBreed.SAVANNAH; // false

Advanced example

• optional constructor can't be public
• all values are constructed statically
• properties can be initialized

enum BreedType {
	NATURAL, MUTATION, HYBRID
}
enum CatBreed {
	SIAMESE (BreedType.MUTATION),
	CHARTREUX (BreedType.NATURAL),
	SAVANNAH (BreedType.HYBRID);
	private BreedType type;
	CatBreed (BreedType type) { this.type = type; }
	BreedType getBreedType() { return this.type; }
}

Type variables

Remember containers ?

List<Integer>
List<Double>
List<String>
List<List<String>>
…

• a "family" of classes (infinite)
• work on any type

Methods signatures

List<Integer> ints = new ArrayList<>();
List<String> strings = new ArrayList<>();
for(int i = 0; i < 10; i++) {
	ints.add(i);
	strings.add(Integer.toString(i));
}

\rightarrow what is the signature of .add ?

An "input"

void add(Integer n) // ??
void add(String s) // ??

• type of their methods depend on the type context
• \rightarrow need to be named in the class declaration
• "input" of a class, like arguments are the inputs of a function
• type variables

Generics

• an identifier (any variable name)
• inside the "diamond" <>
• usually a single letter:
  • N \rightarrow "number" type
  • K \rightarrow "key" in an association
  • V \rightarrow "value" in an association
  • T \rightarrow any type
• multiple parameters are comma separated <K, V>

May appear

in classes

class Box<T> {
	…
}

in methods

as the last modifier, just before the return type

public <T> List<T> preview(List<T> full, int size);

Wildcards

• the "unknown type"
• no name \Rightarrow strictly less powerful (!)
• syntax: ?

Remark

• List<Integer> isn't a subtype of List<Object>
• but it's a subtype of List<?> !
• \Rightarrow allows to get supertypes !

Bounds

:::columns ::::column

extends

• any type that derives from the given type
• useful on covariant operations
• works for generic types

<? extends Integer>

:::: ::::column

super

• any type which the given type derives from
• useful on contravariant operations
• (only for wildcards ! not generics)

<? super Integer>

:::: :::

Useful with interfaces

• conditions on input types
• like variables: reusing the name in the same formula makes the types equal
• hypothesis used in the implementation
• can be combined with &:
  <T extends Comparable & Number>

Example

sorting requires ordered elements:

<T extends Comparable<T>> List<T> sort(List<T> elems);

A little bit of functional programming why not ?

Functional interfaces

A key distinction

:::columns ::::{.column width=49%}

Regular values

• data: raw types, objects…
• can be created dynamically
• can be stored
• passed to functions

::::

::::{.column width=1%}

\rule{.1mm}{.4\textheight}

::::

::::{.column width=49%}

Functions

• structural unit
• (similar to loops)
• no dynamic handling

:::: :::

But what if we want to…

• store a function into a variable ?
• associate it to a key ? (menus…)
• pass it to another function ?
• use concurrency (threads) ?

boolean isEven(int n) {
	return n % 2 == 0;
}
someList.filter(isEven); // Error: cannot find symbol

Interfaces !

• classes can have (several !) methods
• passing an object is a way to pass its methods
• only need a convention to find the method

\rightarrow it's called an interface !

interface MyFunctionType {
	int run(List<Integer> primes);
}

Representing a function

• special case: interface with only one method to implement
• the class is a simple "wrapper" around it
• conventional name to find it
• (can have other methods but only 1 abstract)

\rightarrow it's called a functional interface !

Example

@FunctionalInterface
public interface Predicate<T> {
	public boolean test(T t);
}

Lambda expressions

Concept

:::columns ::::column

From the \textlambda-calculus

• Alonzo Church (1930s)
• base of many languages: Lisp, Ocaml, Haskell…
• the set of terms T contain:
  • atoms: constants C, variables V
  • abstractions: \{\lambda x.t \ \forall v \in V, t \in T\}
  • applications: \{(t\ u) \ \forall t, u \in T\}

:::: ::::column

• like functions (arguments mapped to a value)
• one-liner
• anonymous

\Rightarrow function literals

:::: :::

Syntax

assuming

• (a, b, …) is a tuple of n variables (parentheses optional when 1 only)
• e is an expression
• b is a block ending with a return statement

(a, b, …) -> e
(a, b, …) -> { b }

are values for a given functional interface

Example

(n, m) -> n+m
x -> {System.out.println(x); return -x;}

Literal values

What about their types ?

• no "arrow" types in Java so can't really be written "int -> String"
• the @FunctionalInterface are perfect for the job !
• (mind the conceptual gap)

@FunctionalInterface
public interface Endofunction<T> {
	T apply(T t);
}
Endofunction<Integer> succ = n -> n+1;

Method reference

• what about existing functions ?
• (can be wrapped into a \textlambda, but boring:

n -> someObject.someMethod(n)

• can't handle regular functions except to apply them
• but you can refer to a method with ::

Example

class PartialSum {
	private int firstNumber;
	PartialSum (int initialValue) {
		this.firstNumber = initialValue;
	}
	public int plus(int secondNumber) {
		return this.firstNumber + secondNumber;
	}
}
PartialSum two = new PartialSum(2);
Endofunction<Integer> add2 = two::plus;

Use cases

"Canned computations"

• multi-threading (computations in parallel): Thread
• asynchronous computations: Future<T>
• (all implement Runnable)

Higher-order operations

• no variables, lighter to read
• "add seven to all the elements in this array"

int[] newArray = new int[initialArray.length];
for(int i = 0; i < newArray.length; i++) {
	newArray[i] = initialArray[i] + 7;
}

• map, reduce, iter…

Complexity

Simple containers

Implementing interfaces

One interface, several implementations.

Two implementations

List

• a set of functionalities
• a contract to prove a class can act as a list

:::columns ::::column

ArrayList

\vspace{0.5cm}

• an array larger than the number of elements
• an index to remember where it stops

:::: ::::column

LinkedList

\vspace{0.5cm}

• a "head": the element in the current cell
• a "queue": the pointer to the rest of the list

:::: :::

Getting element at index i

:::columns ::::column

ArrayList

\vspace{0.5cm}

• check the bounds: O(1)
• return cell i: O(1)

\Rightarrow O(1)

:::: ::::column

LinkedList

\vspace{0.5cm}

does i == 0 ?

• if yes, get the head:
• otherwise, get the i-1\textsuperscript{th} element of the queue

\Rightarrow O(n)

:::: :::

Prepending

:::columns ::::column

ArrayList

\vspace{0.5cm}

• create a new array large enough: O(n)
• write the new element: O(1)
• copy all the other elements after: O(n)

\Rightarrow O(n)

:::: ::::column

LinkedList

\vspace{0.5cm}

• create a new cell with the new element pointing to the existing list: O(1)

\Rightarrow O(1)

:::: :::

Performance comparison

So which one is best ?

• if frequent random access is needed: ArrayList
• if frequent modification is needed: LinkedList

\Rightarrow No "one-size-fits-all", implementation should match the use

Associating values to keys

A common need

• "white pages", phone books…
• Domain Name System
• looking up users in a table by their ID
• finding the selected action in a menu

interface Map<K, V> {
	…
	V get(Object k);
}

Association list

:::columns ::::column

class Pair<K, V> {
	…
}

:::: ::::column

class ArrayList<T> {
	…
}

:::: :::

\begin{center} \downarrow \end{center}

class PhoneBook<K, V> {
	private ArrayList<Pair<K, V>> records;
	PhoneBook (int initialSize) {
		this.records = new ArrayList<>(initialSize);
	}
}

Retrieving a number from a key

…
V get(Object k) {
	for(Pair<K, V> record: this.records) {
		if(record.getKey().equals(k)) {
			return record.getValue();
		}
	}
	return null;
}

• must walk the phonebook until found
• on average, this.records.size() / 2
• \Rightarrow O(n)

HashMaps

A clever implementation

• uses .hashCode() on the key: O(1)
• keeps a separate association list for each hash value
• each list as long as the number of collisions (if .hashCode is good, then few): O(c)
• (see birthday problem)

Consequences

• fast access
• fast insertion
• resizing costs when it gets too full (initial capacity / load factor)