summaries-se-ost

Object-Oriented Programming 2

// class
class Box<T> { }
// variable
Box<String> b = new Box<String>();
// method
public <T> void doStuff(T value) { }
// class
class Box<T> { }
// variable
Box<String> b = new Box<String>();
// method
public <T> void doStuff(T value) { }
T obj = new T(); // error
obj instanceof T; // error
T heh = (T) "asdf"; // no typechecking
var s = Stack<int>(); // no primitive types
private static T x; // static no workey
Node<Number> s = new Node<Integer>; // error
class IThrowAnErrorBecauseWhyNot {
void m(List<String> list) { }
void m(List<Integer> list) { }
} // error because of type erasure & identifiability
T obj = new T(); // error
obj instanceof T; // error
T heh = (T) "asdf"; // no typechecking
var s = Stack<int>(); // no primitive types
private static T x; // static no workey
Node<Number> s = new Node<Integer>; // error
class IThrowAnErrorBecauseWhyNot {
void m(List<String> list) { }
void m(List<Integer> list) { }
} // error because of type erasure & identifiability
for (String s : stringList) { } // ==
for (Iterator<String> i = stringList.iterator();
i.hasNext();) {
String s = i.next();
}
for (String s : stringList) { } // ==
for (Iterator<String> i = stringList.iterator();
i.hasNext();) {
String s = i.next();
}
interface Iterable<T> {
Iterator<T> iterator();
}
interface Iterator<E> {
boolean hasNext();
E next();
}
interface Iterable<T> {
Iterator<T> iterator();
}
interface Iterator<E> {
boolean hasNext();
E next();
}
static <T extends Comparable> T doStuff(T a, T b) {
// compareTo is possible with all types
return a.compareTo("b") > 0 ? a : b;
}
static <T extends Comparable<T>> T doStuff(T a, T b) {
// compareTo is possible only with T
return a.compareTo(b) > 0 ? a : b;
}
static <T extends Comparable> T doStuff(T a, T b) {
// compareTo is possible with all types
return a.compareTo("b") > 0 ? a : b;
}
static <T extends Comparable<T>> T doStuff(T a, T b) {
// compareTo is possible only with T
return a.compareTo(b) > 0 ? a : b;
}
class Graphic {
public void draw() { }
}
class Rectangle extends Graphic { }
class Circle extends Graphic { }
class GraphicStack<T extends Graphic>
extends Stack<T> {
public void drawAll() {
for (T item : this) item.draw();
}
}
class Graphic {
public void draw() { }
}
class Rectangle extends Graphic { }
class Circle extends Graphic { }
class GraphicStack<T extends Graphic>
extends Stack<T> {
public void drawAll() {
for (T item : this) item.draw();
}
}
  • Introduced because of “bAcKwArDs CoMpAtAbIlItY”
  • No type information at runtime (Non-Reifiable Type)
class MyStack<T> {
Entry<T> top;
int push(T value) { }
}
// becomes
class MyStack {
Entry top;
int push(Object value) { }
}
/* with bounds */
class MyStack<T extends Comparable<T>> {
Entry<T> top;
int push(T value) { }
}
// becomes
class MyStack {
Entry top;
int push(Comparable value) { }
}
/* what happens at/before runtime */
MyStack<String> s = new MyStack<String>();
s.push("Eh");
String x = s.pop();
// becomes
MyStack s = new MyStack();
s.push("Eh");
String x = (String) s.pop();
class MyStack<T> {
Entry<T> top;
int push(T value) { }
}
// becomes
class MyStack {
Entry top;
int push(Object value) { }
}
/* with bounds */
class MyStack<T extends Comparable<T>> {
Entry<T> top;
int push(T value) { }
}
// becomes
class MyStack {
Entry top;
int push(Comparable value) { }
}
/* what happens at/before runtime */
MyStack<String> s = new MyStack<String>();
s.push("Eh");
String x = s.pop();
// becomes
MyStack s = new MyStack();
s.push("Eh");
String x = (String) s.pop();
void printGs(List<Graphic> gs) { }
List<Graphic> gs1 = new ArrayList<>();
printGs(gs1); // ok
List<Circle> gs2 = new ArrayList<>();
printGs(gs2); // error
/* solution */
void printGs(List<? extends Graphic> gs) { }
void printGs(List<Graphic> gs) { }
List<Graphic> gs1 = new ArrayList<>();
printGs(gs1); // ok
List<Circle> gs2 = new ArrayList<>();
printGs(gs2); // error
/* solution */
void printGs(List<? extends Graphic> gs) { }
Type Compatible
Type-Args
R W
Invariance C<T>C<T> TT
Covariance C<? extends T>C<? extends T> TT and sub-types
Contravariance C<? super T>C<? super T> TT and basis-types
Bivariance C<?>C<?> All
static <T> void move(Stack<T>, from, Stack<T> to) {
while(!from.isEmpty()) to.push(from.pop());
}
var rectS = new Stack<Rectangle>();
var graphS = new Stack<Graphic>();
graphS.push(new Rectangle()); // ok
move(rectS, graphS); // error
Stack<Object> objS = graphS; // error
/* anotherone */
String[] strA = new String[10];
Object[] objA = strA; // ok
objA[0] = Integer.valueOf(2); // runtime err
static <T> void move(Stack<T>, from, Stack<T> to) {
while(!from.isEmpty()) to.push(from.pop());
}
var rectS = new Stack<Rectangle>();
var graphS = new Stack<Graphic>();
graphS.push(new Rectangle()); // ok
move(rectS, graphS); // error
Stack<Object> objS = graphS; // error
/* anotherone */
String[] strA = new String[10];
Object[] objA = strA; // ok
objA[0] = Integer.valueOf(2); // runtime err
public class Stack<E> {
public void pushAll(Iterable<? extends E> src) { }
}
Stack<? extends Graphic> graphS;
graphS = new Stack<Rectangle>(); // ok
graphS = new Stack<Circle>(); // ok
graphS = new Stack<Object>(); // error (duh)
/* read only */
Stack<? extends Graphic> stack = new
Stack<Rectangle>();
stack.push(new Graphic()); // error
stack.push(new Rectangle()); // error
stack.push(new Triangle()); // error
public class Stack<E> {
public void pushAll(Iterable<? extends E> src) { }
}
Stack<? extends Graphic> graphS;
graphS = new Stack<Rectangle>(); // ok
graphS = new Stack<Circle>(); // ok
graphS = new Stack<Object>(); // error (duh)
/* read only */
Stack<? extends Graphic> stack = new
Stack<Rectangle>();
stack.push(new Graphic()); // error
stack.push(new Rectangle()); // error
stack.push(new Triangle()); // error
static <T> void addToC(List<? super T> list, T e) {
list.add(e);
}
addToC(new ArrayList<Number>(), 3); // ok
addToC(new ArrayList<Object>(), 3); // ok
/* shenanigans */
Stack<? super Graphic> s = new Stack<Object>();
s.add(new Graphic()); // ok
s.add(new Rectangle()); // ok
Graphic g = s.pop(); // error
Object g = s.pop(); // ok
static <T> void addToC(List<? super T> list, T e) {
list.add(e);
}
addToC(new ArrayList<Number>(), 3); // ok
addToC(new ArrayList<Object>(), 3); // ok
/* shenanigans */
Stack<? super Graphic> s = new Stack<Object>();
s.add(new Graphic()); // ok
s.add(new Rectangle()); // ok
Graphic g = s.pop(); // error
Object g = s.pop(); // ok
static void printList(List<?> list) {
for (Object elem : list)
System.out.print(elem + " ");
}
/* more shenanigans */
static void appendNewObject(List<?> list) {
list.add(new Object()); // error
}
static void printList(List<?> list) {
for (Object elem : list)
System.out.print(elem + " ");
}
/* more shenanigans */
static void appendNewObject(List<?> list) {
list.add(new Object()); // error
}
<T extends Comparable & Collection> // multiple type bounds
<T extends Comparable & Collection> // multiple type bounds
List<? extends Media> mediaList;
public <S extends T> List<S>
filterBySubtype(Class<S> subtype) {
return mediaList.stream()
.filter(subtype::isInstance)
.map(subtype::cast)
.collect(Collectors.toList());
}
List<? extends Media> mediaList;
public <S extends T> List<S>
filterBySubtype(Class<S> subtype) {
return mediaList.stream()
.filter(subtype::isInstance)
.map(subtype::cast)
.collect(Collectors.toList());
}
  • Metadata
  • Not actually part of the code
  • @Override
  • @Test
  • @Json…
@Target(ElementType.TYPE)
@Retention(RetentionPolicy.RUNTIME)
public @interface Author {
String name();
String date() default "N/A";
}
@Author(name = "UwU", date = "idon'tvalidateinput")
public class WeeOoo { }
@Target(ElementType.TYPE)
@Retention(RetentionPolicy.RUNTIME)
public @interface Author {
String name();
String date() default "N/A";
}
@Author(name = "UwU", date = "idon'tvalidateinput")
public class WeeOoo { }
  • Information of Class (private and public): Methods, Attributes, Parent class, Implemented interfaces
  • Calling methods possible
  • Usages: Debugger, Serialization, Frameworks, Remote Procedure Call, ORM
// all of these `throws SecurityException`
public Field[] getDeclaredFields()
public Method[] getDeclaredMethods()
public Constructor<?>[] getDeclaredConstructors()
System.out.println(dump(new Student("a", "b"), 0));
// {
// firstName = a
// lastName = b
// }
Class c = "s".getClass(); // java.lang.String
// all of these `throws SecurityException`
public Field[] getDeclaredFields()
public Method[] getDeclaredMethods()
public Constructor<?>[] getDeclaredConstructors()
System.out.println(dump(new Student("a", "b"), 0));
// {
// firstName = a
// lastName = b
// }
Class c = "s".getClass(); // java.lang.String
// @Target(ElementType.METHOD)
public String getName()
public boolean isAnnotationPresent(
Class<? extends Annotation> annotationClass)
public Object invoke(Object obj, Object... args)
throws IllegalAccessException,
IllegalArgumentException,
InvocationTargetException
public class Profiler {
public static void main(String[] args) {
var testFunctions = new ProfileFunctions();
int[] array = {5, 2, 8, 1, 93, 3, 33, 1, 333};
var methods = ProfileFunctions.class
.getDeclaredMethods();
for (var m : methods) {
if(m.isAnnotationPresent(Profile.class)) {
m.setAccessible(true); // best practice or sth, idk, i write code in actually good languages
Profiler.profileMethod(testFunctions, m,
new Object[] {array});
}
}
}
}
// @Target(ElementType.METHOD)
public String getName()
public boolean isAnnotationPresent(
Class<? extends Annotation> annotationClass)
public Object invoke(Object obj, Object... args)
throws IllegalAccessException,
IllegalArgumentException,
InvocationTargetException
public class Profiler {
public static void main(String[] args) {
var testFunctions = new ProfileFunctions();
int[] array = {5, 2, 8, 1, 93, 3, 33, 1, 333};
var methods = ProfileFunctions.class
.getDeclaredMethods();
for (var m : methods) {
if(m.isAnnotationPresent(Profile.class)) {
m.setAccessible(true); // best practice or sth, idk, i write code in actually good languages
Profiler.profileMethod(testFunctions, m,
new Object[] {array});
}
}
}
}
// @Target(ElementType.TYPE)
getDeclaredConstructor().newInstance()
...
// @Target(ElementType.TYPE)
getDeclaredConstructor().newInstance()
...
// @Target(ElementType.FIELD)
...
// @Target(ElementType.FIELD)
...
@Min(value = 18, message = "Age must be >= 18")
@Max(value = 99, message = "Age must be <= 99")
private int age;
@NotNull(message = "Name cannot be null")
private String name;
@Min(value = 18, message = "Age must be >= 18")
@Max(value = 99, message = "Age must be <= 99")
private int age;
@NotNull(message = "Name cannot be null")
private String name;
  • Brute-force
  • Greedy

    • Take best option each step (optimize locally)
    • Fast
  • Backtracking

    • Trial and error
    • Best overall option
    • Higher compute costs
  • Divide and conquer

    • Binary search
  • Dynamic programming

    • Recursion optimization?
    • Tabulation
  • Worst case scenario
  • Atomic operations = constant time
  • Runtime measured as sum of primitive operations

Notation

complexity class

in order :

Big

If is polynomial of degree , then

  • ignore lower powers
  • ignore constants

Use most optimal function (lowest power)

  • is better than is

Simplify as far as possible

  • is instead of is
Name Class Example
Constant Array read
Logarithmic Binary search
Linear Linear search
Log-linear Merge+Quick sort
Quadratic Bubble+Insertion sort
Cubic Solve equation
Polynomial Various algorithms
Exponential Calculate all subsets
Factorial Calculate all permutations
  • Search for smallest elem in unsorted part and move in front
  • Less mutations in array
  • Same performance even if list almost sorted
public static void selectionSort(int[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++) {
int minimum = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[minimum])
minimum = j;
swap(a, i, minimum);
}
}
public static void selectionSort(int[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++) {
int minimum = i;
for (int j = i + 1; j < n; j++)
if (a[j] < a[minimum])
minimum = j;
swap(a, i, minimum);
}
}

  • Take elem and put into correct place in sorted part
  • Good for already partially sorted arrays
public static void insertionSort(int[] a) {
int n = a.length;
for (int i = 1; i < n; i++)
for (int j = i; j > 0 && a[j] < a[j - 1]; j--)
swap(a, j, j - 1);
}
public static void insertionSort(int[] a) {
int n = a.length;
for (int i = 1; i < n; i++)
for (int j = i; j > 0 && a[j] < a[j - 1]; j--)
swap(a, j, j - 1);
}

  • Compare neighboring elems and swap if needed
public static void bubbleSort(int[] a) {
for (n = a.length; n > 1; n--)
for (i = 0; i < n - 1; i++)
if (a[i] > a[i + 1])
swap(a, i, i + 1);
}
public static void bubbleSort(int[] a) {
for (n = a.length; n > 1; n--)
for (i = 0; i < n - 1; i++)
if (a[i] > a[i + 1])
swap(a, i, i + 1);
}

public static void countingSort(int[] a) {
int k = Arrays.stream(arr).max().getAsInt();
int[] c = new int[k + 1];
for (int i : a) c[i] += 1;
int pos = 0;
for (int i = 0; i < k; i++)
for (int j = 0; j < c[i]; j++) {
a[pos] = i;
pos++;
}
}
public static void countingSort(int[] a) {
int k = Arrays.stream(arr).max().getAsInt();
int[] c = new int[k + 1];
for (int i : a) c[i] += 1;
int pos = 0;
for (int i = 0; i < k; i++)
for (int j = 0; j < c[i]; j++) {
a[pos] = i;
pos++;
}
}

  • Sort pairs of far away elems
  • Sort the partially sorted array through insertion sort
public static void shellSort(int[] a) {
int n = a.length;
int h = 1;
while (h < n/3) h = 3 * h + 1;
while (h >= 1) {
for (int i = h; i < n; i++)
for (int j = i; j >= h && a[j] < a[j - h];
j = j - h) swap(a, j, j - h);
h /= 3;
}
}
public static void shellSort(int[] a) {
int n = a.length;
int h = 1;
while (h < n/3) h = 3 * h + 1;
while (h >= 1) {
for (int i = h; i < n; i++)
for (int j = i; j >= h && a[j] < a[j - h];
j = j - h) swap(a, j, j - h);
h /= 3;
}
}
public static <T extends Comparable<T>> boolean bs(
List<T> data, T target, int low, int high) {
if (low > high) return false;
int pivot = low + ((high - low) / 2);
if (target.equals(data.get(pivot)))
return true;
else if (target.compareTo(data.get(pivot)) < 0)
return searchBinary(data, target, low,
pivot - 1);
else
return searchBinary(data, target, pivot + 1,
high);
}
public static <T extends Comparable<T>> boolean bs(
List<T> data, T target, int low, int high) {
if (low > high) return false;
int pivot = low + ((high - low) / 2);
if (target.equals(data.get(pivot)))
return true;
else if (target.compareTo(data.get(pivot)) < 0)
return searchBinary(data, target, low,
pivot - 1);
else
return searchBinary(data, target, pivot + 1,
high);
}

When a function calls itself

Recursive call starts at most one further recursive call

Linear recursion where the recursive call is last

All non-terminal calls have two recursive calls

ADT

Abstract Data Type (e.g. Interface)

  • LIFO
  • FIFO