CS61B: Lecture 9

Subtype Polymorphism Vs Function Passing

• function passing is common in python, but Java code relies more on polymorphism.
• Polymorphism: The ability in programming to present the same programming interface for different underlying forms.
  • Operator overloading is a form of polymorphism which allows operators to have different implementations for different types, while providing the same interface to the user.
• Function Passing: A function is passed as an argument into function.

Comparables

• In Java, to compare two objects, we have to specify that object is something that can be compared.
  • How do we specify that a class has a certain capability? Use an interface.
• To compare a Dog object, we declare to Java that Dog is-a Comparable
  • Any subclass that implements Comparable must have the compareTo(T o) method.

public class Dog implements Comparable<Dog> {
    public String name;
    public int size;

    public Dog(String n, int s) {
        name = n;
        size = s;
    }

    @Override
    public int compareTo(Dog other) {
        return size - other.size;
    }
}

List<Dog> dogs = new ArrayList<Dog>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 5000));
Collections.max(dogs).name;

Clifford

• Now, our Dog is something that may be compared to other dogs.
• This comparable example is called a subtype polymorphism.
  • A supertype (Comparable) sepcifies the capability.
  • A subtype implements the new way of how the capability works.
• “Natural Order” is used to refer to the ordering implied by a Comparable’s CompareTo method.
• What if we wanted to find the dog with the greatest alphabeticaly name?

Comparator

• Java provides a Comparator interface for objects that are degiend for comparing objects.
  • We make a nested class:

public class Dog implements Comparable<Dog> {
    public String name;
    public int size;

    public Dog(String n, int s) {
        name = n;
        size = s;
    }

    @Override
    public int compareTo(Dog other) {
        return size - other.size;
    }

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

List<Dog> dogs = new ArrayList<Dog>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 5000));
Collections.max(dogs, new Dog.NameComparator()).name;

Pelusa

• The second argument that we passed into Collections.max() is an object of the type Comparator<Dog>.
  • In Python we pass dunctions directly
  • In Java, we package our compariso function inside of a Comparator object. We rely on on subtype polymorphism.
  • This allows us to open other ways to compare dogs.
• The following code may be more syntactically beautiful:

public class Dog implements Comparable<Dog> {
    public String name;
    public int size;
    public static Comparator<Dog> NAME_COMPARATOR = new NameComparator();

    public Dog(String n, int s) {
        name = n;
        size = s;
    }

    @Override
    public int compareTo(Dog other) {
        return size - other.size;
    }

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

List<Dog> dogs = new ArrayList<Dog>();
dogs.add(new Dog("Grigometh", 200));
dogs.add(new Dog("Pelusa", 5));
dogs.add(new Dog("Clifford", 5000));
Collections.max(dogs, Dog.NAME_COMPARATOR).name;

Pelusa

Comparables vs Comparators

• The Comparable interface specifies that a “natural order” exists.
  • Instances of the class can compare themselves to other objects. Only one such order is possible.
• The Comparator interface is used to compare extrinsically (by other classes)
  • We may have many such classes each specifying one such order.

Writing a Generic Function

• We can create a Generic Class and then instantiate an object every time to use the methods with generics.
• However, we may also create a static generic method by specifying that the function works for objects with a type T, it returns a T, and is called pickRandom.

public class RandomPicker {
    public static <T> T pickRandom(T[] x) {
        Random random = new Random();
        int randomIndex = random.nextInt(x.length);
        return x[randomIndex];
    }
}

• However, this type of implementation does not work for primitives. Primitives must have their own implementations.
• Now we may write a max function.
  • We must specify that we want not just any T, but a Comparable<T>

public class Maximizer {
    public static <T extends Comparable<T>> T max(T[] items) {
        T maxItem = items[0]
    }
}