## Testing

### Thinking Process

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:

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

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.

Exercise in Study Guide

## 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.

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)

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.

Compiler is conservative in type checking.

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

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

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:

#### 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.

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

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

#### Method Preferences

Example 0:

((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:

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:

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?).

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.

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

Interface:

Implementation:

Using:

## Ex (Examprep 4)

### Ex 1 (Puppers)

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.

### Ex 2 (Cast the line)

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

indexOf:

## 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:

Subtype Polymorphism Approach:

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.

So we can generalize the max function.

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:

### 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

• 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.

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!

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.

Now, the Dog class should be like:

In DogLauncher, the code is:

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.

### 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 no keyword for abstract methods.
• Use default keyword for concrete methods.
• Can provide only public static final variables.
• Can provide only public methods.

### Abstract Class

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

#### vs. Interface

Interfaces:

• Primarily for interface inheritance. Limited implementation inheritance.
• Classes can implement multiple interfaces.

Abstract classes:

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

#### List Hierarchy

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 can’t just throw it away.

A more of the real list hierarchy:

Even more:

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.

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.

Every time you visit a new page, clear the forward button stack.

## Ex (Discussion 5)

### 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):

### 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.

### 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.

Using stacks:

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

## 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.

• Can use import statement to provide shorthand notation for usage of a single class in a package.

• Wildcard import: Also possible to import multiple classes, but this is often a bad idea!

Import static members:

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).

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.

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.

### 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)

• If you don’t specify the package a class is in, is it part of a package? If so, which package?

A class that is not in a named package is in an unnamed package, also known as default package.

Such classes cannot be used from a named package, except via reflection.

### Ex 2 (Same Method Name)

Consider the following code:

The output is:

## Autoboxing

How it works:

• 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.

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.

Space occupied:

• ints are 32 bits.
• All Java objects take 64 bits + their fields.

## Access Control

### Access Modifier

How do public and private behave with packages and subclasses?

• 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.

Subtleties:

Interface methods are public in default.

### Nested class

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.

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.
• Classes other than Outer cannot make or access Inner anymore. Common for things like LinkedListDeque (make your IntNode class private).

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?

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

## 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.

0%