CS 61B Part 3 Inheritance, Implements, Iterators

prev:[[61B_Part_2_LinkList]]
next:[[part4-Iterators]]
Hug61B chapter4

Part 3 Inheritance, Implements, Iterators

overload

Suppose we want to write a class WordUtilsthat includes functions we can run on lists of words, including a method that calculates the longest string in an SLList.

public static String longest(SLList<String> list) {
    int maxDex = 0;
    for (int i = 0; i < list.size(); i += 1) {
        String longestString = list.get(maxDex);
        String thisString = list.get(i);
        if (thisString.length() > longestString.length()) {
            maxDex = i;
        }
    }
    return list.get(maxDex);
}

make it suitable for AList?

change the SLList<String> list into the AList<String> list!

coexistence of the two functions are allowed in the function!

(method overloading)

interface

In Java, in order to express this hierarchy, we need to do two things:

Step 1: Define a type for the general list hypernym – we will choose the name List61B.

Step 2: Specify that SLList and AList are hyponyms of that type.

here is the 61B interface:

public interface List61B<Item> {
    public void addFirst(Item x);
    public void addLast(Item y);
    public Item getFirst();
    public Item getLast();
    public Item removeLast();
    public Item get(int i);
    public void insert(Item x, int position);
    public int size();
}

then, we define this relationship in the class definition:

public class AList<Item> implements List61B<Item>{...}

overriding

When implementing the required functions in the subclass, it’s useful (and actually required in 61B) to include the @Override tag right on top of the method signature.

@Override
public void addFirst(Item x) {
    insert(x, 0);
}

actually, the Override keyword is not needed. But it can be served as a checklist for us to debug.

Inheritance

Interface Inheritance

interface can also inheritance.

just have interface, no code!

Implementation Inheritance

with default method, we can write default method in interfaces

for SLList and AList, we write:

default public void print() {
    for (int i = 0; i < size(); i += 1) {
        System.out.print(get(i) + " ");
    }
    System.out.println();
}

However, the efficiency of the method in SLList and ‘AList’ differs.

For an SLList, the get method needs to jump through the entirety of the list. during each call. It’s much better to just print while jumping through!

for this, we need to override it:

@Override
public void print() {
for (Node p = sentinel.next; p != null; p = p.next) {
System.out.print(p.item + " ");
}
}

when adding:

List61B<String> lst = new SLList<String>();

which print() to call?

the SLList.print() one

How do java know which print() to call?

dynamic method selection (DMS)

an object: compile-time type x

run-time type y

if y overrides the method, y’s method would be used instead.

without @Override, the default method in the interface would be excuted!

e.g.:

public interface Animal {
  default void greet(Animal a) {
    print("hello animal"); }
  default void sniff(Animal a) {
    print("sniff animal"); }
  default void praise(Animal a) {
    print("u r cool animal"); }
}
public class Dog implements Animal {
  @Override
  void sniff(Animal a) {
    print("dog sniff animal"); }
  void praise(Dog a) {
    print("u r cool dog"); }
}
Animal a = new Dog();
Dog d = new Dog();
a.greet(d);
a.sniff(d);
d.praise(d);
a.praise(d);

// ans:
a.greet(d); // greet(Animal a) - “hello animal”
a.sniff(d); // sniff(Animal a) - “dog sniff animal”
d.praise(d);// praise(Dog a) - “u r cool dog”
a.praise(d);// praise(Animal a) - “u r cool animal”

Another way to understand DMS

DMS as two-step process: compiling step & running step

Dynamic type of a is Dog. So use Dog’s praise(Animal)

important: “is-a” relationships are better than “has-a” relationships.

Extends

the extends keyword

class is a hyponym of an interface –> implements

class is a hyponym of another class –> extends

features

all methods from the superclass are contained

change the method in the superclass: @Override

you can also call the method in the superclass by super

constructor: must come first with super

public VengefulSLList(Item x) {
   super(x);
   deletedItems = new SLList<Item>();
}

Java requires that all constructors must start with a call to one of its superclass’s constructors.

without super(x), you just get the default method!

The reason:

public class Human {...}
public class TA extends Human {...}

if run: TA Christine = new TA();

Then the TA would be human first, and then be TA!

Object class

every class was extended from the Object class

Encapsulation 封装

Core: hiding information from the outside

hiding information that others don’t need is another fundamental approach when managing a large system.

a module: a set of methods that work together as a whole to perform a task or set of related tasks

the private keyword: ensuring that the underlying complexity isn’t exposed to the outside world.

How Inheritance Breaks Encapsulation

example 1:

public void bark() {
    System.out.println("bark");
}

public void barkMany(int N) {
    for (int i = 0; i < N; i += 1) {
        bark();
    }
}

example 2:

public void bark() {
    barkMany(1);
}

public void barkMany(int N) {
    for (int i = 0; i < N; i += 1) {
        System.out.println("bark");
    }
}

it is basically the same without inheritance.

when overriding them:

@Override
public void barkMany(int N) {
System.out.println("As a dog, I say: ");
for (int i = 0; i < N; i += 1) {
bark();
}
}

Given a VerboseDog vd, what would vd.barkMany(3) output, given the first implementation above? The second implementation?

a: As a dog, I say: bark bark bark

b: bark bark bark

c: Something else

Actually, for example 1, the answer is A

for example 2, the answer is infinite loop.

Type Checking

For each line of code below, decide the following:

Does that line cause a compilation error?

Which method uses dynamic selection?

The lines: sl.printLostItems();

a compile-time error: the compiler determines whether something is valid based on the static type of the object. Since sl is of static type SLList, and printLostItems is not defined in the SLList class, the code will not be allowed to run

VengefulSLList<Integer> vsl2 = sl;

also a compile-time error(similar reason)

Like variables as seen above, expressions using the new keyword also have compile-time types.

SLList<Integer> sl = new VengefulSLList<Integer>();

compile-time type of right hand side: VengefulSLList

VengefulSLList<Integer> vsl = new SLList<Integer>();

compile-time type of right hand side: SLList

Casting

tell the compiler that the specific expression has a specific type

Poodle largerPoodle = (Poodle) maxDog(frank, frankJr); // compiles! Right hand side has compile-time type Poodle after casting

Caution: casting do not do its type-checking duties!

One possible error:

Poodle frank = new Poodle("Frank", 5);
Malamute frankSr = new Malamute("Frank Sr.", 100);

Poodle largerPoodle = (Poodle) maxDog(frank, frankSr); // runtime exception!

Higher-order functions

in python:

def tenX(x):
    return 10*x

def do_twice(f, x):
    return f(f(x))

In java:

public interface IntUnaryFunction {
    int apply(int x);
}
public class TenX implements IntUnaryFunction {
    /* Returns ten times the argument. */
    public int apply(int x) {
        return 10 * x;
    }
}
public static int do_twice(IntUnaryFunction f, int x) {
    return f.apply(f.apply(x));
}

when calling:

System.out.println(do_twice(new TenX(), 2));

The new feature was added after Java8.

To notice: Java is mainly an OOP language, so that its implementation of Functional Programming is much limited!

Subtype Polymorphism

Java: how objects can have many forms or types

OOP: how an object can be regarded as an instance of its own class, an instance of its superclass, an instance of its superclass’s superclass, and so on.

for python comparison:

Explicit HoF Approach

def print_larger(x, y, compare, stringify):
if compare(x, y):
return stringify(x)
return stringify(y)

Subtype Polymorphism Approach

def print_larger(x, y):
if x.largerThan(y):
return x.str()
return y.str()

An example: Max function

debug the following program:

public static Object max(Object[] items) {
    int maxDex = 0;
    for (int i = 0; i < items.length; i += 1) {
        if (items[i] > items[maxDex]) {
            maxDex = i;
        }
    }
    return items[maxDex];
}

public static void main(String[] args) {
    Dog[] dogs = {new Dog("Elyse", 3), new Dog("Sture", 9), new Dog("Benjamin", 15)};
    Dog maxDog = (Dog) max(dogs);
    maxDog.bark();
}

the error was items[i] > items[maxDex], in which the Object cannot be compared.

In python or C++, > operator can refer to different meanings when applied to different types of parameters.

In Java, however, the operator cannot be done like this.

Therefore, we can add a function like this:

public static Dog maxDog(Dog[] dogs) {
    if (dogs == null || dogs.length == 0) {
        return null;
    }
    Dog maxDog = dogs[0];
    for (Dog d : dogs) {
        if (d.size > maxDog.size) {
            maxDog = d;
        }
    }
    return maxDog;
}

However, we have to rewrite the method for many other programs. Therefore, Instead, we turn to interface inheritance to help us out.

public interface OurComparable {
public int compareTo(Object o);
}

We will define its behavior like so:

Return -1 if this < o.

Return 0 if this equals o.

Return 1 if this > o.

The implementation of it in class of Dog:

public int compareTo(Object o) {
        Dog uddaDog = (Dog) o;
        if (this.size < uddaDog.size) {
            return -1;
        } else if (this.size == uddaDog.size) {
            return 0;
        }
        return 1;
    }

then, we can generalize the function in previous:

public static OurComparable max(OurComparable[] items) {
    int maxDex = 0;
    for (int i = 0; i < items.length; i += 1) {
        int cmp = items[i].compareTo(items[maxDex]);
        if (cmp > 0) {
            maxDex = i;
        }
    }
    return items[maxDex];
}

Benefits for it:

No need for maximization code in every class(i.e. no Dog.maxDog(Dog[]) function required

We have code that operates on multiple types (mostly) gracefully

Comparables

The interface OurComparable have some issues:

• Awkward casting to/from Objects
• No existing classes implement OurComparable (e.g. String, etc.)
• No existing classes use OurComparable (e.g. no built-in max function that uses OurComparable)

to fix them, we used the comparable interface that have been defined by Java.

comparator

an interface that looks very similar

inside:

public interface Comparator<T> {
    int compare(T o1, T o2);
}

The rule for compare is just like compareTo.

let’s give Dog class a NameComparator.

import java.util.Comparator;

public class Dog implements Comparable<Dog> {
    ...
    public int compareTo(Dog uddaDog) {
        return this.size - uddaDog.size;
    }

    private static class NameComparator implements Comparator<Dog> {
        public int compare(Dog a, Dog b) {
            return a.name.compareTo(b.name);
        }
    }

    public static Comparator<Dog> getNameComparator() {
        return new NameComparator();
    }
}

The structure is:

summarize

Interfaces in Java give us the ability to make callbacks.

comparable: defines the natural ordering of a type (only one compareTo method can exist!)

comparator: a third-party machine that compares two objects to each other.

Multiple ways to compare –> comparator