Testing

Thinking Process

The Evolution of our Design

Often, development is an incremental process that involves lots of tasks switching and on the fly design modification.

Tests provide stability and scaffolding:

  • Provide confidence in basic units and mitigate possibility of breaking them.
  • Help you focus on one task at a time.

In large projects, test also allow you to safely refactor (still have the same function)!

Four Philosophies

Here we have four testing philosophies:

  • Autograder Driven Development (ADD)
  • Unit Tests
  • Test-Driven Development (TDD)
  • Integration Testing

Autograder Driven Development (ADD)

The worst way to approach programming. This workflow is slow and unsafe!

Wait for the autograder to run, and test everything at the end of development.

Unit Tests

But, how do you test units that rely on others. e.g. how do you test addFirst in Project 1?

Test-Driven Development (TDD)

It is a repeat process consisting of three parts:

Integration Testing

Idea: Tests cover many units at once.

Not JUnit’s focus, but JUnit can do this.

But it tests at highest level of abstraction what may miss subtle or rare errors.

Dependency

Exercise in Study Guide

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@Test
public void testEquals() {
  /** Arrays */
  int[][] a1 = {{1, 2, 3}, {2}, {3}};
  int[][] a2 = {{1, 2, 4}, {2}, {3}};
  assertArrayEquals(a1, a2); /* Test fails */
  /** String (Wrapping Class) */
  String s1 = "123123123";
  String s2 = "123123123";
  String s3 = new String("123123123");
  String s4 = new String("123123123");
  // Since they are wrapping classes, Java just compare their inside values.
  assertEquals(s1, s2); /* Test pass! */
  assertEquals(s3, s4); /* Test pass! */
  assertEquals(s1, s4); /* Test pass! */
  /** Other Classes - Compare addresses (id) */
  Object o1 = new Object();
  Object o2 = new Object();
  assertEquals(o1, o2); /* Test fails */
}

Inheritance & Implements

Interface & Implementation

Interface Inheritance (what):

  • Subclass inherits signatures, but NOT implementation
  • So we can also say it is Signature Inheritance.

Implementation Inheritance (how):

  • Subclasses can inherit signatures AND implementation.

Static vs. Dynamic Type

Every variable in Java has a compile-time type, a.k.a. static type.

  • This is the type specified at declaration. Never changes!

Variables also have a run-time type, a.k.a. dynamic type.

  • This is the type specified at instantiation (e.g. when using new).
  • Equal to the type of the object really being pointing at.

Static Type vs. Dynamic Type

1
2
3
4
5
6
Animal a =  new Animal("Pluto", 10);
Dog d = new Dog("Fido", 4);
a = new Dog("Spot", 10);
d = a; // Dog (static)  <-  Animal (static)
// Compiler error because the static type of d is Dog and the static type of a is Animal. We can fix this by casting:
d = (Dog) a;

If Y overrides the method, Y’s method is used instead. This is known as dynamic method selection.

Implementation inheritance may sound nice, but there are some drawbacks:

  • We are fallible humans, and we can’t keep track of everything, so it’s possible that you overrode a method but forgot you did.
  • It may be hard to resolve conflicts in case two interfaces give conflicting default methods.
  • It encourages overly complex code.

Encapsulation

When building large programs, our enemy is complexity.

Ways of managing complexity (ultimately determine whether a programmer is successful), as shown in Software Engineering lectures:

  • Hierarchical abstraction (List, LinkedList, ArrayList)
  • Design for (future) change (D. Parnas)
    • Organize program around objects (modules)
    • Let objects decide how things are done. Outsider needs not to know.
    • Hide information others don’t need (helper functions)

Even when writing tests, you don’t (usually) want to peek inside.

Ideally, a user should not be able to observe the internal workings of, say, a data structure they are using. Java is a great language for enforcing abstraction barriers with syntax (language aspect).

Later, we use Abstract Data Types (ADTs) to handle what we need.

Inheritance Breaks Encapsulation:

1st Implementation:

(The upper box is in superclass)

1st Implementation - Answer: a

2nd Implementation (Really bad):

2nd Implementation - Answer: c (infinite loop)

By allowing inheritance in a particular situation, we now have a way to peek inside a beautifully encapsulated class.

We didn’t change anything in overridden barkMany, but someone changed the superclass implementation that they thought it was safe and kapow (爽).

Type Checking & Casting

Type Checking

Static type is also called compile-time type.

Override:

If a method in SLList is overridden by the VengefulSLList class, then the method that is called at runtime is determined by the run-time type (dynamic type) of that variable (dynamic method selection).

  • If a method overridden: Call from dynamic type.
  • If a method not overriden: Call from static type.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Overridden: removeLast
 * Not Overridden: addLast
 * Only VengefulSLList has printLostItems() method
 */
VengefulSLList<Integer> vsl = new VengefulSLList<Integer>(9);
// Static type: VengefulSLList<Integer>
// Dynamic type: VengefulSLList<Integer>
SLList<Integer> sl = vsl;
// Static type: SLList<Integer>
// Dynamic type: VengefulSLList<Integer>

sl.removeLast(); // Overridden, call dynamic type VengefulSLList<Integer>
sl.addLast(50); // Not overridden, call static type

Compiler is conservative in type checking.

1
2
3
/* Compile-time Error */
sl.printLostItems();
// Not overridden, call static type. But SLList<Integer> has no idea about printLostItems() in compile-time, even later it knows during runtime.

In general, the compiler only allows method calls and assignments based on compile-time types.

1
2
VengefulSLList<Integer> vsl2 = sl;
// Since the compiler only sees that the static type of sl is SLList, it won't allow a VengefulSLList to hold it.

Also, expressions using the new keyword also have compile-time types.

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

Above, the compile-time type of the right-hand side of the expression is SLList. The compiler checks if SLList “is-a” VengefulSLList, which it is not in all cases, and thus a compilation error results.

Further, method calls have compile-time types equal to their declared types. Suppose we have this method:

1
2
3
4
5
6
7
8
9
public static Dog maxDog(Dog d1, Dog d2) { ... }
/* Any call to maxDog will have compile-time type Dog */

Poodle frank = new Poodle("Frank", 5);
Poodle frankJr = new Poodle("Frank Jr.", 15);

Dog largerDog = maxDog(frank, frankJr); // okay
Poodle largerPoodle = maxDog(frank, frankJr); // does not compile! 
// Return value: RHS (right hand side) has compile-time type Dog, but on the left side it is Poodle and Dog is not a Poodle.

Casting

Java has a special syntax where you can tell the compiler that a specific expression has a specific compile-time type. This is called casting. With casting, we can tell the compiler to view an expression as a different compile-time type, ignoring its type checking duties.

1
2
3
4
5
// Pass type checking in compile time.
Poodle frank = new Poodle("Frank", 5);
Malamute frankSr = new Malamute("Frank Sr.", 100);
Poodle largerPoodle = (Poodle) maxDog(frank, frankJr);
// At runtime, it'll crash when maxDog returns the Malamute.

Should be careful when doing downcasting, especially when downcasting a superclass to a subclass.

1
2
3
4
5
6
7
8
/* The problem lies in the right hand side. */
Animal a = (Dog) new Animal(); // Runtime Error
// Dog is an Animal. Static types are compatible.
// Runtime: 
// - Downcasting: Animal is a Dog? No

Dog a = (Dog) new Animal(); // Runtime Error
// - Downcasting. But it is in fact an Animal. Not compatible.

It’s okay if we are sure that the object whose static type is superclass actually has a subclass dynamic type.

1
2
3
Animal a = new Dog();
Dog b = a; // compile error, type-checking error
Dog c = (Dog) a; // pass type-checking and okay in runtime since a is indeed a Dog object.

Method Preferences

Example 0:

1
2
Dog d = new Dog();
((Animal) d).makeNoise(d);

((Animal) d).makeNoise(d): In compile-time type checking, when checking to see if a method called makeNoise exists in Animal, do we check for a makeNoise(Dog) method or a makeNoise(Animal) method?

  • Compile time (Animal):
    • Check method name -> matched
    • Check parameter types -> It depends the methods in Animal class.
      • It can match Animal’s makeNoise(Animal)
      • Or match makeNoise(Dog)
      • But it will definitely goes for the later one because it is a more specific match.
  • Run time (Dog):
    • d is a Dog, not an Animal.
    • If the method is overridden?
      • Yes. Call the overridden version. (Dynamic Method Selection)
      • No. Call the superclass version.

Idea:

  • Parameter type-checking prefers specific if possible.
  • The order is important:
    • Class type Checking:
      • Static type == Dynamic type:
        • Override won’t happen. Overload may happen.
      • Static type != Dynamic type:
        • If the method is overridden -> dynamic method selection.
        • If not -> just call the one matched in superclass.
  • The method we consider later in run time is the one decided in compile-time type checking.
    • In run time, it won’t change its mind from makeNoise(Dog) to makeNoise(Animal).
    • In run time, we check if this method is overridden to decide if we need dynamic method selection.

Consider the two examples (Very important):

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Animal {
  public void makeNoise(Animal a) {
    System.out.println("Dog01");
  }
  // public void makeNoise(Dog d) {
  //   System.out.println("Dog02");
  // }
}
class Dog extends Animal {
  @Override
  public void makeNoise(Animal a) {
    System.out.println("Dog1");
  }
  /* Overload */
  public void makeNoise(Dog d) {
    System.out.println("Dog2");
  }
}

// main
Animal a = new Dog(); // a is actually Dog
a.makeNoise(new Dog()); // 1: Dog1
a.makeNoise(new Animal()); // 2: Dog1

// No dynamic method selection since Dog's makeNoise is not overridden
(new Dog()).makeNoise(new Animal()); // 3: Dog1
(new Dog()).makeNoise(new Dog()); // 4: Dog2

Line 1:

  • Compile time (Animal):
    • Check method name -> matched
    • Check parameter types -> compatible (Dog is an Animal), matched
  • Run time (Dog):
    • a is Dog. The method makeNoise(Animal) is overridden. So it outputs “Dog1”.

Line 2:

  • Compile time (Animal):
    • Check method name -> matched
    • Check parameter types -> exactly matched
  • Run time (Dog):
    • a is Dog. The method makeNoise(Animal) is overridden. So it outputs “Dog1”.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Animal {
  public void makeNoise(Animal a) {
    System.out.println("Dog01");
  }
  public void makeNoise(Dog d) {
    System.out.println("Dog02");
  }
}
class Dog extends Animal {
  @Override
  public void makeNoise(Animal a) {
    System.out.println("Dog1");
  }
  /* Overridden (not overloaded) */
  public void makeNoise(Dog d) {
    System.out.println("Dog2");
  }
}

// main
Animal a = new Dog(); // a is actually Dog
a.makeNoise(new Dog()); // 1: Dog2 <- Difference
a.makeNoise(new Animal()); // 2: Dog1

Line 1:

  • Compile time (Animal):
    • Check method name -> matched
    • Check parameter types -> prefer specific version, exactly matched (makeNoise(Dog)).
  • Run time (Dog):
    • a is Dog. The method makeNoise(Dog) is overridden (not overloaded). So it outputs “Dog2”.

Line 2:

  • Compile time (Animal):
    • Check method name -> matched
    • Check parameter types -> exactly matched
  • Run time (Dog):
    • a is Dog. The method makeNoise(Animal) is overridden. So it outputs “Dog1”.

Higher Order Functions (HoFs)

Higher Order Function: A function that treats another function as data (or input?).

1
2
3
4
5
6
7
8
# In Python
def tenX(x):
  return 10 * x

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

print(do_twice(tenX, 2))

In old school Java (Java 7 and earlier), memory boxes (variables) could not contain pointers to functions. What that means is that we could not write a function that has a “Function” type, as there was simply no type for functions.

The Default Way

In Java, we can use Interface to do this. Use a Interface class to wrap up a method / function.

Interface:

1
2
3
public interface IntUnaryFunction {
  public int apply(int x);
}

Implementation:

1
2
3
4
5
public class TenX implements IntUnaryFunction {
  public int apply(int x) {
    return 10 * x;
  }
}

Using:

1
2
3
4
5
6
7
8
// Use Interface IntUnaryFunction rather than TenX - Abstraction
public static int do_twice(IntUnaryFunction f, int x) {
  return f.apply(f.apply(x));
}

public static void main(String[] args) {
  do_twice(new TenX(), 2);
}

Ex (Examprep 4)

Ex 1 (Puppers)

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Dog {
  public void bark(Dog d) { /* Method A */ }
}

public class Corgi extends Dog {
  public void bark(Corgi c) { /* Method B */ }

  @Override
  public void bark(Dog d) { /* Method C */ }

  public void play(Dog d) { /* Method D */ }
  public void play(Corgi c) { /* Method E */ }
}

For the following main method, at each call to play or bark, tell us what happens at runtime by selecting which method is run or if there is a compiler error or runtime error.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
  Dog d = new Corgi();
  Corgi c = new Corgi();

  d.play(d);  /* Compile-Error: Dog has no method play(Dog) */
  d.play(c);  /* Compile-Error: Dog has no method play(Corgi) */
  c.play(d);  /* Method D */
  c.play(c);  /* Method E */

  c.bark(d);  /* Method C */
  c.bark(c);  /* Method B */

  // Notice there is no bark(Corgi c), so d.bark(c) matchs A first, and then matchs C in dynamic method selection.
  d.bark(d);  /* Method C (dynamic selecting) */
  d.bark(c);  /* Method C (dynamic selecting), not B */
}

Ex 2 (Cast the line)

Consider each line independently whether it causes a compilation error, runtime error, or runs successfully.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Animal    Tree
// ^  ^
// |   \
// Cat  Dog
public static void main(String[] args) {
  Cat c = new Animal();  // Compile Error
  Animal a = new Cat();  // Okay
  Dog d = new Cat();     // Compile Error
  Tree t = new Animal(); // Compile Error

  Animal a = (Cat) new Cat();     // Okay
  Animal a = (Animal) new Cat();  // Okay
  Dog d = (Dog) new Animal();     // Runtime Error
  Cat c = (Cat) new Dog();        // Compile Error (not up-or-down casting)
  Animal a = (Animal) new Tree(); // Compile Error: The casting is not compatible
}

Ex 3 (SLList Vista)

indexOf:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// IntList class: 
// - item
// - next
public int indexOf(int x) {
  int index = 0;
  IntList p = this.first; // no sentinel
  while (p != null) { // end at the last item
    if (p.item == x) {
      return index;
    }
    index += 1;
    p = p.next;
  }
  return -1;
}

Polymorphism vs. HoFs

Polymorphism

Polymorphism, at its core, means many forms. In Java, polymorphism refers to how objects can have many forms or types.

In object-oriented programming, polymorphism relates to 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.

The above statement is very great.

Subtype Poly. vs. HoF

Explicit HoF Approach:

1
2
3
4
5
def print_larger(x, y, compare, stringify):  
  # callback: a function needs the help of another function (callback) that might not have been written yet (function passing)
  if compare(x, y):
    return stringify(x)
  return stringify(y)

Subtype Polymorphism Approach:

1
2
3
4
def print_larger(x, y):
  if x.largerThan(y): # x object makes its choices
    return x.str()
  return y.str()

In Python or C++, the way that the > operator works could be redefined (overloaded) to work in different ways when applied to different types.

Unfortunately, Java does not have this capability. Instead, we turn to interface inheritance to help us out. We do this by wrapping up the needed function in an interface (e.g. Arrays.sort needs compare which lives inside the comparator interface). Arrays.sort “calls back” whenever it needs a comparison.

1
2
3
4
5
6
7
8
9
10
11
12
13
public interface OurComparable {  // should be "extends Comparable"?
  public int compareTo(Object o);
}

public class Dog implements OurComparable {
  private String name;
  private int size;

  public int compareTo(Object o) {  // or Comparable o
    Dog uddaDog = (Dog) o;  // casting
    return this.size - uddaDog.size;
  }
}

So we can generalize the max function.

1
2
3
4
5
6
7
8
9
10
11
/* Maximizer class */
public static OurComparable max(OurComparable[] items) {
  int maxDex = 0;
  for (int i = 0; i < items.length - 1; i += 1) {
    int cmp = items[i].compareTo(items[maxDex]);
    if (cmp > 0) {
      maxDex = i;
    }
  }
  return items[maxDex];
}

What are the benefits to this approach?

  • No need for maximization code in every class (i.e. no Dog.maxDog(Dog[]) function required.
    • We don’t need to know that class should be Dog class.
  • We have code that operates on multiple types (mostly) gracefully

Easy Quizzes:

Answer: Dog.java

Answer: DogLauncher.java (Maximizer.java won't fail because of abstraction code)

Comparable

The OurComparable interface that we just built works, but it’s not perfect. Here are some issues with it:

  • Awkward casting to/from Objects
    1
    2
    3
    4
    public int compareTo(Object o) {  // or Comparable
      Dog uddaDog = (Dog) o;  // casting
      return this.size - uddaDog.size;
    }
  • We made it up.
    • No existing classes implement OurComparable (e.g. String, etc.)
    • No existing classes use OurComparable (e.g. no built-in max function that uses OurComparable)

The solution? We’ll take advantage of an interface that already exists called Comparable. Comparable is already defined by Java and is used by countless libraries.

Comparable looks very similar to the OurComparable interface we made, but with one main difference.

1
2
3
public interface Comparable<T> {
  public int compareTo(T obj);
}

The generic type will help us avoid casting an object to a specific type.

Comparator

Let’s start off by defining some terminology.

  • Natural order - used to refer to the ordering implied in the compareTo method of a particular class. (Dog - size)

What if we’d like to sort Dogs in a different way than their natural ordering, such as by alphabetical order of their name?

In explicit HoF approach, we can use compare to specify a different compare function. However, in subtype polymorphism approach, compareTo1, compareTo2, and so forth? No!

1
2
3
4
def print_larger(T x, T y, comparator<T> c):
  if c.compare(x, y):
    return x.str()
  return y.str()

Java’s way of doing this is by using Comparator‘s. Since a comparator is an object, the way we’ll use Comparator is by writing a nested class (so it’s static) inside Dog that implements the Comparator interface.

Note: It is static because we don’t need to instantiate a Dog to get a NameComparator. Instead, we get it when initializing the class.

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

Now, the Dog class should be like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.Comparator;

public class Dog implements Comparable<Dog> {

  public int compareTo(Dog uddaDog) {
    return this.size - uddaDog.size;
  }

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

  /** getNameComparator()
   *  public: accessible (set NameComparator class as private)
   *  static: Dog.getNameComparator()
   */
  public static Comparator<Dog> getNameComparator() {
    return new NameComparator();
  }

  // We can have other comparators, but we have only one compareTo().
}

In DogLauncher, the code is:

1
2
3
4
5
Dog.NameComparator nc = Dog.getNameComparator();
// or
Comparator<Dog> nc = Dog.getNameComparator();
// or
someMethod(data, Dog.getNameComparator()); // more common

In summary, a Comparable says, “I want to compare myself to another object”. It is imbedded within the object itself, and it defines the natural ordering of a type.

However, a Comparator, on the other hand, is more like a third party machine that compares two objects to each other. Since there’s only room for one compareTo method, if we want multiple ways to compare, we must turn to Comparator.

Abstract Data Types (ADT)

Interface

In Java, Deque is called an interface. Conceptually, we call deque an Abstract Data Type. Deque only comes with behaviors, not any concrete ways to exhibit those behaviors. In this way, it is abstract.

Stack: LIFO property
Queue: FIFO property
Deque: Both LIFO and FIFO

In Java, we use interfaces to achieve ADTs:

  • Cannot be instantiated.
  • Can provide either abstract or concrete methods.
    • Use default keyword for concrete methods.
  • Can provide only public static final variables.
  • Can provide only public methods.
1
2
// In an interface class
public static void hahah(); // Error: Static methods in interfaces should have a body

Abstract Class

Answer: C

Abstract class doesn’t have to implement the method listed in interface.

Interface vs. Abstract Class

Interfaces:

  • Primarily for interface inheritance. Limited implementation inheritance.
  • Classes can implement multiple interfaces. (main difference)

Abstract classes:

  • Can do anything an interface can do, and more.
  • Subclasses only extend one abstract class.

List Hierarchy

Why didn’t we use Interface only?

AbstractList provides default implementations for methods. But why not just put them in List itself? No default methods in Java interfaces until 2014, and the AbstractList was public so we can’t just throw it away.

A more of the real list hierarchy:

More of the real list hierarchy

Even more:

The Whole Shebang

When in doubt, try to use interfaces in order to build up abstraction, reduce complexity, and hide unnecessary information.

Discussion 5:

Some scenes of application:

  • Given a news article, find the frequency of each word used in the article:

    Use a map.

  • Given an unsorted array of integers, return the array sorted from least to greatest:

    Use a priority queue. For each integer in the unsorted array, enqueue the integer with a priority equal to its value.

  • Implement the forward and back buttons for a web browser:

    Use two stacks, one for each button. Each time you visit a new web page, add the previous page to the back button’s stack, and also clear the forward button stack.

    When you click the back button, add the current page to the forward button stack, and pop a page from the back button stack.

    When you click the forward button, add the current page to the back button stack, and pop a page from the forward button stack.

Ex (Discussion 5)

Ex 1 (Queue)

Two-Stack Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Queue {
  private Stack stack = new Stack();

  public void enqueue(E element) {
    Stack temp = new Stack();  // a temp stack
    while (!stack.isEmpty()) { // move to temp stack
      temp.push(stack.pop());
    }
    stack.push(element);
    while (!temp.isEmpty()) { // move from temp stack
      stack.push(temp.pop());
    }
  }

  public E dequeue() { return stack.pop(); }
}

A Stack can also be implemented by two Queues.

Recursive Version

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Queue {
  private Stack stack = new Stack();

  public void enqueue(E element) { stack.push(element); }

  public E dequeue() {  // recursion
    return dequeue(stack.pop()); 
  }

  private E dequeue(E previous) { // consider size = 1
    if (stack.isEmpty()) {  // size = 0
      return previous;  // previous is the last item
    }
    E toReturn = dequeue(stack.pop());
    stack.push(previous);  // push it back to the stack
    return toReturn;
  }
}

Ex 2 (TwoSum)

Given an array of integers $A$ and an integer $k$, return true if any two numbers in the array sum up to $k$, and return false otherwise. How would you do this? Give the main idea and what ADT you would use.

Brute-force: 2 loops.

A smarter way (use a map): 

1
2
3
4
5
6
7
8
9
public boolean twoSum(int[] A, int k) {
  Set<Integer> seenItems = new HashSet<>();
  for (int i : A) {
    if (seenItems.contains(k - i)) {
      return true;
    }
    seenItems.add(i);
  }
}

Ex 3 (K-most Words)

Find the k-most common words in a document. Assume that you can represent a string as an array of words, where each word is an element in the array. You might find using multiple data structures useful.

Keep a count of all the words in the document using a HashMap<String, Integer>. After we go through all of the words, each word will be mapped to how many times it’s appeared.

Then we can put all the words into a MaxPriorityQueue<String>, using a custom comparator that compares words based on the counts in the HashMap. We can then pop off the k-most common words by just calling poll() on the MaxPriorityQueue k times.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void topFivePopularWords(String[] words, int k) {
  /** Counting words */
  Map<String, Integer> counts = new HashMap<>();
  for (String w : words) {
    counts.put(w, counts.getOrDefault(w, 0) + 1);
  }
  /** Comparator */
  PriorityQueue<String> pq = new PriorityQueue<>(new Comparator<String>(){
    @Override
    public int compare(String a, String b) {
      return counts.get(b) - counts.get(a);
    }
  });

  for (String w : counts.keySet()) {
    pq.add(w); /* automatically put in order */
  }
  for (int i = 0; i < k; i += 1) {
    System.out.println(pq.poll());
  }
}

Ex 4 (SortedStack)

Suppose we wanted a data structure SortedStack that takes in integers, and maintains them in sorted order. SortedStack supports two operations: push(int i) and pop(). Popping returns the next smallest item in the SortedStack.

For example, if we inserted [10, 4, 8, 2, 14, 3] into a SortedStack, and then popped everything off, we would get [2, 3, 4, 8, 10, 14].

My Way

Not using stacks (iterative way). We have some invariants:

  • The smallest item is at the top of stack.
  • Push guarantees that the items in stack is in increasing order.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class SortedStack() {
  
  SLList items = new SLList();
  /** Push */
  public void push(int x) {
    if (items.size == 0) {
      items.addLast(x);
      return;
    }
    /* From big to small number (First -> Last)*/
    IntNode ptr = items.sentinel.next; /* First element */
    while (ptr != sentinel) {
      if (x <= ptr.item) {
        /** Insert! But we have no related function of SLList */
        ptr.next = new IntNode(x, ptr.next);
        break;
      }
      ptr = ptr.next;
    }
  }
  /** Pop */
  public int pop() {
    if (items.size == 0) {
      return -1;
    }
    return items.removeLast();
  }
}

Answer

Using stacks:

We have two stacks A and B. A holds all the items, and B is our buffer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class SortedStack<Item extends Comparable<Item>> {
  private Stack<Item> main;
  private Stack<Item> buffer;

  public SortedStack() {
    main = new Stack<>();
    buffer = new Stack<>();
  }

  public void push(Item t) {
    // keep smaller items away in the buffer
    while (!main.empty() && main.peek().compareTo(t) < 0) {
      buffer.push(main.pop());
    }
    main.push(t);
    // push back the smaller items
    while (!buffer.empty( )) {
      main.push(buffer.pop());
    }
  }

  public Item pop() {
    return main.pop();
  }
}

Package

Package names give a canonical name for everything. “Canonical” means a unique representation for a thing.

Importing Class

Here are some different ways we can use a class:

  • Entire name.
    1
    ug.joshh.animal.Dog d = new ug.joshh.animal.Dog();
  • Can use import statement to provide shorthand notation for usage of a single class in a package.
    1
    2
    import ug.joshh.animal.Dog;
    Dog d = new Dog();
  • Wildcard import: Also possible to import multiple classes, but this is often a bad idea!
    1
    2
    import ug.joshh.animal.*;
    Dog d = new Dog();

Import static members:

1
2
3
4
import static org.junit.Assert.assertEquals;
assertEquals(5, 5);
// we usually use (probably only wildcard import used in the course):
import static org.junit.Assert.*;

The built-in java.util package provides a number of useful interfaces and implementations.

Creating A Package

The reason why we use Package is to address the fact that classes might share names. A package is a namespace that organizes classes and interfaces.

Naming convention: Package name starts with website address (backwards).

1
2
package bearmaps.hw4.wordladderpuzzle;
package com.junhaow;

Two steps:

  • At the top of every file in the package, put the package name.
  • Make sure that the file is stored in a folder with the appropriate folder name. For a package with name ug.joshh.animal, use folder ug/joshh/animal.

The Default Package

Any Java class without a package name at the top are part of the default package. In other words, from now on, when writing real programs, your Java files should always start with a default package declaration.

Idea: Ensure that we never have two classes with the same name at any situation.

But, you cannot import code from the default package! For example, if I were to create a DogLauncher class in the default package in a DogLauncher.java file, I would be unable to access this DogLauncher class anywhere else outside of the default package.

1
2
3
4
package cat.place;

DogLauncher.launch(); // don't work
default.DogLauncher.launch(); // doesn't exist

JAR Files

JAR file are just zip files.

  • They do not keep your code safe!
  • Easy to unzip and transform back into .Java files (from .class).

Note: Do not share .jar files of your projects with other students.

Ex (Guide)

Ex 1 (Q&A)

  • If an abstract class extends an abstract class, would it need to have function definitions for the abstract methods in the parent class? Similarly would an interface that implements another interface have to implement the non-default methods in the parent interface.

    No. No. If not implementing in the subclass or subinterface, the sub-subclass or sub-subinterface should do the job.

  • Can an abstract class be the subclass of a normal class?

    Yes. (The default package)

Ex 2 (Same Method Name)

Consider the following code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Tree {
  public void bark() {
    System.out.println("haha - Tree");
  }
}

interface Dog {
  default void bark() {
    System.out.println("haha - Dog");
  }
}

public class TreeDog extends Tree implements Dog {
  public static void main(String[] args) {
    TreeDog td = new TreeDog();
    td.bark();
  }
}

The output is:

1
haha - Dog

Autoboxing

How it works (wrapper type and primitive type):

  • If Java code expects a wrapper type and gets a primitive, it is autoboxed.
  • If the code expects a primitive and gets a wrapper, it is unboxed.
1
2
3
4
5
6
7
8
/* Not a magic */
public final class Integer extends Number implements Comparable<Integer> {
  private final int value;
  public Integer(int value) {
    this.value = value;
  }
  // ...
}

Note:

  • Arrays are never autoboxed/unboxed, e.g. an Integer[] cannot be used in place of an int[] (or vice versa).
  • Autoboxing / unboxing incurs a measurable performance impact!
  • Wrapper types use much more memory than primitive types because of object overheads.

Space occupied:

  • Addresses are 64 bits.
  • ints are 32 bits.
  • All Java objects take 64 bits + their fields.
1
2
3
4
5
6
public static void bleepblorp() {
  Integer x = new Integer(5);
  System.out.println(x);
  // Output: 64 (address) + 64 (other information) + 32 (int)
  //         = 160
}

Access Control

Access Modifier

How do public and private behave with packages and subclasses?

Access Table

  • Public: This keyword opens up the access to everyone! This is generally what clients of the package can rely on to use.

    • Once deployed, the public members’ signatures should not change. It’s like a promise and contract to people using this public code that it will always be accessible to them.
    • Usually if developers want to “get rid of” something that’s public, rather than removing it, they would call it deprecated instead.
    • TL;DR: Open and promised to the world.

  • Protected: Protected members are protected from the outside world.

    • Classes within the same package and subclasses can access these members, but the rest of the world (e.g. classes external to the package or non-subclasses) cannot!
    • TL;DR: Subtypes might need it, but subtype clients will not.

  • Package Private: This is the default access given to Java members if there is no explicit modifier written.

    • Package private entails that classes that belong in the same package can access, but not subclasses!
    • The original owners of the class that’s being extended may not want certain features or members to be tampered with, if people choose to extend it — hence, package-private allows those who are familiar with the inner workings of the program to access and modify certain members, whereas it blocks those who are subclassing from doing the same.
    • TL;DR: Only classes that live in the same package can access.

  • Private: Only code from the given class can access private members.

    • It is truly private from everything else, as subclasses, packages, and other external classes cannot access private members.
    • TL;DR: Only the class needs this piece of code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package syntax3.map;
public class ArrayMap
  int size; // package-private
// ...

package syntax3.map;
public class MyonicArrayMap extends ArrayMap {
  public MyonicArrayMap(int s) {
    size = s; 
    // Will this work? Yes, because it is part of the same package
    // Don't need to think about whether it is part of the same subclass
    // Default access (package private) only supports Class, Package
  }
}
// ...

package syntax3.map;
public class MapHelper {
  public static void printSize(ArrayMap am) {
    System.out.println(am.size); // OK. It's part of the same package
  }
}

Subtleties:

Interface methods are public in default.

Access Is Based Only on Static Types - Client has no idea about HasHair but BlackHole

Nested class

1
2
3
4
5
6
7
public class Outer {
  public int outvar;

  public class Inner {
    public int invar;
  }
}

In the example above: Anybody can create an Outer, anybody can create an Inner, and anybody can access an Inner’s variable. And an Inner can access this.outvar.

1
2
3
4
5
6
7
public class Outer {
  public int outvar;

  private class Inner {
    public int invar;
  }
}

In the example above, Inner is private. At this point, the access modifiers to all of inners’ members are irrelevant.

  • An Outer can access an Inner’s variables. The reason is that “Inner” is a subordinate slave of Outer, and thus has no personal possessions.
  • We can change public (invar) to anything and have no observable effect (its function has been shadowed).
  • Classes other than Outer cannot make or access Inner anymore. Common for things like LinkedListDeque (make your IntNode class private).
1
2
3
4
5
6
7
8
9
10
public class Outer {
  private int outvar;

  private class Inner {
    public int invar;
    public void test() {
      outvar = 5; /* OKAY */
    }
  }
}

In the example above, can an Inner access an Outer’s outvar? Yes, it can because Inner is part of the Outer class.

What could I do so that an Inner can’t use outvar?

1
2
3
4
5
6
7
8
9
10
public class Outer {
  private int outvar;
  
  private static class Inner {
    public int invar;
    public void test() {
      outvar = 5;  // I cannot access my enclosing instance's outvar
    }
  }
}

Can I instantiate a non-static inner class (nested class) without an outer instance?

1
2
3
4
5
/** 1 */
Outer out = new Outer();
Outer.Inner in1 = out.new Inner();
/** 2 */
Outer.Inner in2 = new Outer().new Inner();

Discussion 6

Exception

There are 2 overarching types of exceptions:

  • Checked

    You must either wrap them in a try/catch block or pass the buck by using throws exception in the method header.

  • Unchecked

    You don’t need to handle these. They are typically an error on a user’s part, which can’t really be helped.

Exception Hierarchy

Iterators and Iterables

Ex (Discussion 6)

Ex 1 (AltList)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public AltList<X, Y> pairSwapped() {
  AltList<Y, X> ret = new AltList<Y, X>(next.item, new AltList<X, Y>(item, null));

  /* Recursive */
  if (next.next != null) {
    ret.next.next = next.next.pairSwapped();
  }

  /* Iterative */
  AltList<X, Y> ptr = next.next;
  AltList<Y, X> newPtr = ret;
  while (ptr != null) {
    newPtr.next.next = new AltList<Y, X>(ptr.next.item, new AltList<X, Y>(ptr.item, null))
    newPtr = newPtr.next.next;
    ptr = ptr.next.next;
  }

  return ret;
}

Ex 2 (Every K-th Element)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class KthIntList implements Iterator<Integer> {
  private IntList curList;
  public int k;
  private boolean hasNext;

  public KthIntList(IntList L, int k) {
    this.curList = L;
    this.k = k;
    this.hasNext = true;
  }

  public boolean hasNext() {
    return this.hasNext;
  }

  /* Returns the next K-th element of the IntList given in the constructor
   * Returns the 0-th element firsts. Throws a NoSuchElementException if
   * there are no Integers available to return.
   */
  public Integer next() {
    
    if (curList == null) {
      throw new NoSuchElementException();
    }
    
    Integer ret = curList.item;

    int count = k;
    while (count > 0) {
      curList = curList.next;
      count -= 1;
      if (curList == null) {
        hasNext = false;
        break;
      }
    }

    return ret;
  }
}