Object-Oriented Programming 2
// classclass Box<T> { }// variableBox<String> b = new Box<String>();// methodpublic <T> void doStuff(T value) { }
// classclass Box<T> { }// variableBox<String> b = new Box<String>();// methodpublic <T> void doStuff(T value) { }
T obj = new T(); // errorobj instanceof T; // errorT heh = (T) "asdf"; // no typecheckingvar s = Stack<int>(); // no primitive typesprivate static T x; // static no workeyNode<Number> s = new Node<Integer>; // errorclass IThrowAnErrorBecauseWhyNot { void m(List<String> list) { } void m(List<Integer> list) { }} // error because of type erasure & identifiability
T obj = new T(); // errorobj instanceof T; // errorT heh = (T) "asdf"; // no typecheckingvar s = Stack<int>(); // no primitive typesprivate static T x; // static no workeyNode<Number> s = new Node<Integer>; // errorclass 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) { }}// becomesclass MyStack { Entry top; int push(Object value) { }}/* with bounds */class MyStack<T extends Comparable<T>> { Entry<T> top; int push(T value) { }}// becomesclass 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();// becomesMyStack s = new MyStack();s.push("Eh");String x = (String) s.pop();
class MyStack<T> { Entry<T> top; int push(T value) { }}// becomesclass MyStack { Entry top; int push(Object value) { }}/* with bounds */class MyStack<T extends Comparable<T>> { Entry<T> top; int push(T value) { }}// becomesclass 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();// becomesMyStack s = new MyStack();s.push("Eh");String x = (String) s.pop();
void printGs(List<Graphic> gs) { }List<Graphic> gs1 = new ArrayList<>();printGs(gs1); // okList<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); // okList<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()); // okmove(rectS, graphS); // errorStack<Object> objS = graphS; // error/* anotherone */String[] strA = new String[10];Object[] objA = strA; // okobjA[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()); // okmove(rectS, graphS); // errorStack<Object> objS = graphS; // error/* anotherone */String[] strA = new String[10];Object[] objA = strA; // okobjA[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>(); // okgraphS = new Stack<Circle>(); // okgraphS = new Stack<Object>(); // error (duh)/* read only */Stack<? extends Graphic> stack = new Stack<Rectangle>();stack.push(new Graphic()); // errorstack.push(new Rectangle()); // errorstack.push(new Triangle()); // error
public class Stack<E> { public void pushAll(Iterable<? extends E> src) { }}Stack<? extends Graphic> graphS;graphS = new Stack<Rectangle>(); // okgraphS = new Stack<Circle>(); // okgraphS = new Stack<Object>(); // error (duh)/* read only */Stack<? extends Graphic> stack = new Stack<Rectangle>();stack.push(new Graphic()); // errorstack.push(new Rectangle()); // errorstack.push(new Triangle()); // error
static <T> void addToC(List<? super T> list, T e) { list.add(e);}addToC(new ArrayList<Number>(), 3); // okaddToC(new ArrayList<Object>(), 3); // ok/* shenanigans */Stack<? super Graphic> s = new Stack<Object>();s.add(new Graphic()); // oks.add(new Rectangle()); // okGraphic g = s.pop(); // errorObject g = s.pop(); // ok
static <T> void addToC(List<? super T> list, T e) { list.add(e);}addToC(new ArrayList<Number>(), 3); // okaddToC(new ArrayList<Object>(), 3); // ok/* shenanigans */Stack<? super Graphic> s = new Stack<Object>();s.add(new Graphic()); // oks.add(new Rectangle()); // okGraphic g = s.pop(); // errorObject 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, InvocationTargetExceptionpublic 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, InvocationTargetExceptionpublic 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