---
tags: summer 2018 cs61bl
---
# CS 61BL Week 3 Notes
Hi! Every week, I like to compile notes based off concepts that my tutees get confused about and good questions that they ask! If you’re already familiar with all the topics, check out the **Resources** section for [practice problems](https://drive.google.com/drive/folders/1qDkBDDt9BQOQSKgyyzfCLG5s1UFYUfRB?usp=sharing) or insights.

Also, if there's anything that doesn't make sense or seems confusing, feel free to shoot me an [email](mailto:[e-mail]).

[TOC]

## Data structures
What are they? Data structures are concrete implementations of ADTs (Abstract Data Types). Funny enough, abstract data types are defined as blueprints for data structures. They contain methods and fields that would be implemented in a data structure! (This is why ADTs are interfaces)

**ADTs:** Lists, Sets, Map, etc.

**Data Structures:** ArrayLists, HashSets, HashMaps, TreeMaps, LinkedList, etc.

## Generics
Generics provide a container that allow you to use *any type* with the class. In the example below, **T** is a *dummy variable* that represents a generic type. Note that you could have used any variable name that is not the name of an existing data structure such as **K**, **X**, **Y** to represent a generic type. It's common convention to name generic types as single uppercase letters!

**Example of Class using Generic Type:**

public class Container<T> {
    private T item;
                        
    //sets item field to item of type T
    public void putItem(T item) {
        this.item = item;
    }
    
    //returns type T object
    public T getItem() {
        return item;
    } 
}

**Below are a few examples of how Container would work:**

Container<String> c = new Container<String>(); 
//T will now refer to a String object

c.putItem("cat");

c.putItem(new Point(3, 4)); //Compile-Time Error

Container<Point> p = new Container<Point>(); 
//T will now refer to a Point object

c.putItem(new Point(3, 4));

Container<T> t = new Container<String>(); //Compile-Time Error
//T only exists inside the Container class so the symbol T would not exist

Container<Animal> a = new Container<Cat>(); //Cat extends Animal 
//While Animal may be a superclass of Cat, Container<Animal> is not a superclass of Container<Cat>. Therefore, there would be a compile-time error.

### Why use Generic types?
A common question is why use a **Generic** type over an **Object** type.

:::info
Reminder: **Object** is a superclass of all of the classes in Java. The hierarchy looks like the picture below, but even bigger! Just know that all classes are extending **Object**.


This means you can run the code below and it would work!

String s = "hi";
Object o1 = s; 

Integer i = new Integer(1);
Object o2 = i;

//Even custom (user-defined) classes work
Container<String> c = new Container<>();
Object o3 = c;

:::

If **Object** can hold any kind of instance object, what's the point of generic types?

Well, let's take a look at Container using **Object**.

public class Container {
    private Object item;
                           
    public void putItem(Object item) {
        this.item = item;
    }
    
    public Object getItem() {
        return item;
    } 
}

With **Object**, we could have **Container** hold any object! **Item** could be **Object**, **String**, or **Boolean** etc.

Container c = new Container();

c.putItem("hi"); //works fine

c.putItem(new Integer(1)); //works fine

However, what if we wanted **Container** to only hold **String** objects as the item? The code above wouldn't work because any instance object from a class can fit into **Object**! Therefore, we use Generic type.

**Throwback to original code:**

public class Container<T> {
    private T item;
                        
    //sets item field to item of type T
    public void putItem(T item) {
        this.item = item;
    }
    
    //returns type T object
    public T getItem() {
        return item;
    } 
}

Now we run the code below:

Container<String> c1 = new Container<>(); //specifies T to be String! 
//For this particular instance object, T = String!

c1.putItem("hi"); //works fine!

c1.putItem(new Integer(1)); //compile-time error 
//Container now only takes in Strings, not any other object!

### Method Header Syntax
*Note: References Iterators as an example. Read this only if you understand Iterators and/or have read the Iterator section.*

We use Generic types used in our method signatures in different ways:

**1. Interfaces Implemented by a Class Without Generic Types**
To be able to address different types in classes that implement them, interfaces often use Generic types. An example is the **Iterator** interface. We use the **Iterator** interface for a variety of objects, so it's best for the **Iterator** interface to use the Generic Type **T**.

//Iterator interface header contains a Generic type
interface Iterator<T>

//when implemented, the Generic Type is replaced with a concrete type
class StringListIterator implements Iterator<String> {
    String current;
    //rest of the implemented methods (not written)
}

**2. Interfaces Implemented by a Class With Generic Types**
Banking off the example above, what if instead of StringList, we wanted to iterate through a list with a Generic Type? Consider the implementation below.

class GenericList<T> implements Iterable<T>{
   
    ArrayList<T> arr = new ArrayList<>();
    
    void add(T item) {
        arr.add(item);
    }
    
    GenericListLiterator<T> iterator() {
        return new GenericListIterator<T>();
    }
    
    //This class header has two references to Generic Types 
    class GenericListIterator<T> implements Iterator<T> {
        T item;
        //implementation of GenericListIterator
    }
}

More importantly, look at the class header of **GenericListIterator**.

class GenericListIterator<T> implements Iterator<T> 

We need both of the **<T>** references because **GenericListIterator** will be directly referencing whatever object is represented by **T** in its implementation.

**3. Method Generics**
The method header below is from Quiz 9.

public static <R extends Comparable<R>> Comparator<T> getComp(Function<T, R> getter)

**<R extends Comparable<R>>** is called a method generic. As defined in your lab:

> A method generic declares a generic type local to a single method (rather than the entire class), and can be used throughout the method similar to generics in classes. The method generic goes after the visibility keyword, public, and before the return type declaration. Additionally, there is a bound on the generic type R, stating that only types that extend Comparable<R> will be accepted by the compiler.

## Comparables and Comparators
Suppose we're given an array or list of objects. We want to be able to sort the objects in the list/array based on some order (e.g. descendingOrder, ascendingOrder, etc). This is where **Comparable** and **Comparator** come in!

### What is the difference between a Comparable object and Comparator object?

**Comparable**
A **Comparable** object is able to compared with itself by some metric. It also *implements* the **Comparable** interface.

**Comparable interface:**

interface Comparable<T> {

    //compares the current object calling this method to the object in the parameter 
    int compareTo(T o);
}

**compareTo** returns an int value based on if **o** should be before or after the current object calling the method. If **o** is "larger" than the current object and should be sorted behind it, then **compareTo** returns a negative number. If **o** is "smaller" than the current object and should be sorted before it, then **compareTo** returns a positive number. If **o** is "equal" to the current object, then **compareTo** returns 0.

**Common Usage of compareTo:**

//String implements Comparable and has a compareTo method
//allows you to compare different Strings lexographically
String longWord = "longlonglonglongword";
String shortWord = "shortword";
String equalWord = "shortword";

longword.compareTo(shortWord); //returns negative integer
shortword.compareTo(longWord); //returns positive integer
equalword.compareTo(shortWord); //returns 0

**Comparator**
A **Comparator** determines the metric for comparison.

**Comparator interface:**

class Comparator<T> {

    //Compares its two arguments of type T for order. 
    compare(T o1, T o2);
    
}

The method **compare** returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second. If **o1<o2**, then **compare** returns a negative number. If **o1>o2**, then **compare** returns a positive number. If **o1=o2**, then **compare** returns 0.

#### Common Usage

String[] arr = new String[]{"hi","whatever","fun"};

//Arrays.sort is used for arrays
Arrays.sort(arr, /* Comparator object that compares objects in arr*/);

ArrayList<String> a = new ArrayList<>();
a.add("hi")
a.add("whatever")
a.add("fun")

//Collections.sort is used for Lists
Collections.sort(a, /* Comparator object that compares objects in a*/);

Now, let's actually create a **Comparator** object.

Suppose we want to sort the Strings in the array below by their length (longest will be last). We can create a **Comparator** object that will do this for us. Note: Before making a comparator, make sure objects being compared in the **compare** method are comparable!

Note: It's common convention for **Comparator** classes to be implemented directly when we try to create an **Comparator** instance object.

String[] arr = new String[]{"hi", "whatever", "fun"};

Comparator<String> arrComp= new Comparator<String>() {
    //what is this doing? We're directly creating a StringComparator class
    // new Comparator<String> is then instantiating an instance object of this class
    @Override 
    public int compare(String o1, String o2) {
        //short complicated version
        //return (new Integer(o1.length())).compareTo(new Integer(o2.length()));
        
        //longer clearer version
        if (o1.length == o2.length) {
            return 0;
        } else if (o1.length < o2.length) {
            return -1;
        } else {
            return 1;
        }
    }
};

Arrays.sort(arr, arrComp);

//arr should now look like ['hi', 'fun', 'whatever']
System.println(a[0]); //prints hi
System.println(a[1]); //prints fun
System.println(a[2]); //prints whatever

### Strange Syntax
The most confusing part about comparators is the syntax. As shown above, we can instantly create an object **Comparator** class and instantiate it in a couple of lines. We can also create **Comparator** instance objects in a couple of other ways.

Suppose, we're still trying to create a **Comparator** object that sorts Strings based on their length.

Comparator<String> arrComp = (s1, s2) -> (new Integer(s1.length())).compareTo(new Integer(s2.length()));

The code above is using a *lambda expression* to express the **compare(String o1, String o2)** method. In this case, **s1** and **s2** are the two String objects being compared. The **->** operator divides the expression, so the left side refers to the parameters and the right side specifies the actions of the expression.

We can also use a function and a **Function** object to create a **Comparator** object (You did this for Quiz 9).

**Comparators Using Function**
Now, let's write our function that uses a **Function** object to return a **Comparator**. If you're confused, review the Function section below!

public static Comparator<String> getStringComp(Function<String, Integer> getter){
    return (s1, s2) -> getter.apply(s1).compareTo(getter.apply(s2))
}

//We can call the function the following way:
Function<String, Integer> getter = String::length;
Comparator<String> arrComp = getStringComp(getter);

## Function Object

Since Java cannot pass functions as parameters, it will pass in a **Function** object instead. There is a Java interface called [**Function**](https://docs.oracle.com/javase/8/docs/api/java/util/function/Function.html#apply-T-) that allows you create **Function** objects.

interface Function<T,R> {
    //takes in an input of type T and returns a Type R
    R apply(T t);
}

**T** is meant to be the type of your input that your function can be applied to and **R** is the type that is outputted.

We want to write a **Function** object that takes in a String and returns its length so we can use it in our comparator!

### What does the **Apply** method do?
The **apply** method is meant to apply the specified function to an object or take in a parameter to input into the function. More specified below:

1. You can input an object that you want to call the function on (e.g. if you pass in a **User** object called u1 and the **Function** is **User::getEmail**, then **apply(u1)** is really calling **u1.getEmail()**).

2. You can input an object that you want to pass into the function as an input (i.e. if the **Function** is referring to a method that takes in a parameter, then you can input the parameter into apply to pass it into the method).

### Instantiating a Function Object
**Function** is a special type of interface called a [functional interface](https://docs.oracle.com/javase/8/docs/api/java/lang/FunctionalInterface.html), which means instances of the interface can be created with lambda expressions, method references, or constructor references.

//First Way: Constructor Reference
Function<String, Integer> getter = new Function<String, Integer>() {
    Integer apply(String s) {
        return s.length();
    }
};

//Second Way: Method Reference
Function<String, Integer> getter = String::length;
// '::' operator divides the expression
// the left hand side refers to the class that contains the method
// the right hand side refers to the method name

//Third Way: Lambda Expression
Function<String, Integer> getter = (s) -> s.length;

### Primitive Function Specialization
If we take a look at the **Function** spec, we realize that **Function** is limited to taking in objects as parameters. What if we want to insert a primitive type such as an int?

Well, one way is to instantiate the int as an **Integer** through:

Integer i = new Integer(5);

However, we can also use other **Function** interfaces from the [java.util.function](https://docs.oracle.com/javase/8/docs/api/java/util/function/package-summary.html) package! There are three types of these objects:
* *IntFunction, LongFunction, DoubleFunction*: arguments are of specified type and return type is an object
* *ToIntFunction, ToLongFunction, ToDoubleFunction*: return type is of specified type, arguments are objects
* *DoubleToIntFunction, DoubleToLongFunction, IntToDoubleFunction, IntToLongFunction, LongToIntFunction, LongToDoubleFunction*: having both argument and return type defined as primitive types, as specified by their names

## Iterables and Iterators
The concept of iterators in CS 61B is very similar to that of iterators in CS 61A! With iterators, you are able to iterate through the elements of a data structure (denoted as an iterable).

### What is the difference between an iterable and iterator?
An **iterable** is a data structure that can be iterated through. Examples are arrays, Linkedlists, and Arraylists. An iterable will *implement* an **Iterable** interface.

An **iterator**, on the other hand, is a data structure that acts as a tool, allowing you to iterate through an iterable. An iterator will *implement* an **Iterable** interface.

### Why are iterators useful?
With iterators, we can use **for-each loops** for arrays of any object. In the example below, we use an **int** **array**.

int[] arr = {1, 2, 3}; //the array we want to iterate through 
//(arr is an iterable)

//normal for loop (more code to handle indexing)
for (int i = 0; i < arr.length; i++) {
      System.out.println(i);
}

//for-each loop (looks much nicer!)
for (int i: arr) {
    System.out.println(i);
}
  
//what the for-each loop is actually doing
Iterator arrIterator = arr.iterator();
while (arrIterator.hasNext()) {
    System.out.println(arrIterator.next());
}

The normal **for loop** requires more methods regarding the data structure we're iterating through while the **for-each loop** implicitly uses an iterator that handles all the specifics *under the hood*. An iterator can eliminate an extra layer of abstraction and make your life much more convenient!

### Why are Iterable and Iterator interfaces?
It also makes sense for **Iterator** to be an interface because many *unrelated* data structures should have a way of iterating through themselves. The same reason applies to **Iterable**.

### Making a Class Iterable
Most existing data structures already implement the **Iterable** interface, so we can simply call their **iterator** method. However, if you wrote a custom class and you want to make it iterable, you have to have it implement **Iterable**.

**Iterable Interface:**

interface Iterable<T> {
    Iterator<T> iterator();
}

The **Iterable** interface requires you to return an **Iterator** object based on the the class. Therefore, we need to write an **Iterator** class that implements the **Iterator** interface.

**Iterator Interface:**

interface Iterator<T> {
    //tells us if there are more objects to iterate over
    boolean hasNext();
      
    //tells us the object that will be iterated over
    T next(); 
}

**Example of a Class Implementing Iterable:**

import java.util.ArrayList;
import java.util.Iterator;

//example of a class implementing Iterable
public class StringList implements Iterable<String> {

    private ArrayList<String> words = new ArrayList<>();
    
    public void add(String s) {
        words.add(s);
    }
    
    @Override
    //implemented method from Iterable interface
    public Iterator<String> iterator() {
        returns new StringListIterator();
    }
    
    //nested class that implements Iterator
    class StringListIterator implements Iterator<String> {
        private int counter = 0;
        
        
        @Override
        //implemented method from Iterator interface
        boolean hasNext() {
            return counter < words.size();
        }
        
        
        @Override
        //implemented method from Iterator interface
        String next() {
            String word = words.get(counter);
            counter++;
            return word;
        } 
    }
}

## Exceptions
**Throwable** is a superclass with two subclasses, **Error** and **Exception**.

**Error** objects indicate serious problems with your application and a reasonable application should not catch one. They are in a separate class from **Exception** because they *cannot* be handled. An example is **OutOfMemoryError**, which cannot be fixed with programming. At this point, we want our program to end to fix it. Also, any exceptions thrown under the **Error** class and its subclasses are considered *unchecked exceptions*. Don’t worry too much about **Error**! It is out of scope.

**Exception** objects, on the other hand, can be caught and handled with programming. There are two types of exceptions:

1. **Checked Exceptions:** exceptions that need to be explicitly handled and are caught by the compiler
*Examples:* file name is not equal to class name, casting an object to an independent class, symbol not resolved, non-static field/method cannot be referenced from a static context

2. **Unchecked Exceptions:** exceptions that are not caught by the compiler, but thrown during runtime
*Examples:* NullPointerException, ArrayIndexOutOfBoundsException, ClassCastException
*Note:* These are exception subclasses that explicitly extend the **RuntimeException** class. Also, the class **RuntimeException** extends **Exception**. Any unchecked exception object, disregarding any **Error** object, such as **NullPointerException** extends **RuntimeException**.

**Some further clarification:**
**Exception** is considered a superclass of all exceptions, unchecked (disregarding Error objects) and checked. This means a **catch** block (you'll read about this later) that catches an **Exception** type object could catch checked exceptions.

Below is what the **Exception** class hierarchy looks like:

### Why are exception objects useful?
We want to be able to catch and handle exceptions during runtime. This makes debugging easier!

Sometimes, programs want to do something with exceptions. Suppose we’re programming a game. If we have any conditions that satisfy game over, we can purposely throw a **RuntimeException**, print out ‘Game Over’, and immediately end the game.

### What actually happens if an exception occurs?
Suppose we have a **main** method that calls a **f1** method, which calls a **f2** method and an exception occurs. This creates an **Exception** object that must be handled by the runtime system. What will happen is the runtime system will go down the call stack searching for something that will handle the exception. If it finds nothing, the program will terminate with the exception. If a **try-catch** block catches the exception, then the exception is considered *handled*.


### Try-Catch Blocks
**Try-catch** blocks in Java are very similar to the **try-catch** blocks you’ve seen in CS 61A! If any code in your **try** block throws an exception, it can be “caught” by a **catch** block!

Note: The **catch** blocks would only catch exceptions thrown in the **try** block. If any exceptions are thrown in a **catch** block, the code would terminate with the exception!

**Example of Try-Catch Block:**

try {
     //code that produces the exception
     throwException();
} catch (NullPointerException e) {
    //code that handles the specific exception that is thrown
} catch (Exception e) {
     //code that handles any type of exception that is thrown
}

### Compile-Time Errors Associated with Try-Catch
Consider the following code below and ask if we would ever reach the second **catch** block:

try {
    throwException();
} catch (Exception e) {
    System.out.println(”This catch block would catch all exceptions.”);
} catch (NullPointerException e) {
    System.out.println(”This catch block would never be reached.”);
}

The code above would not compile since all exceptions would be caught by the first **catch** block. Remember: All specific exception classes (such as **NullPointerException**) extend **Exception**. The compiler would complain because the second **catch** block would never run! A general rule of thumb when creating **try-catch** blocks is to catch *specific* errors first before addressing more *general* errors.

### Creating and Throwing Exception Objects

try {
    throw new RuntimeException();
    //the code above is equivalent to: 
    //RuntimeException e = new RuntimeException(); //throw e;
} catch (Exception e) {
    throw e; 
}

Since **RuntimeException** extends **Exception**, the **RuntimeException** would be caught by the **catch** block. In the **catch** block, the same object with static type **RuntimeException** and dynamic type **RuntimeException** will be thrown.

## Resources
[Week 3 Resources](https://drive.google.com/drive/folders/1qDkBDDt9BQOQSKgyyzfCLG5s1UFYUfRB?usp=sharing): compilation of all the problems and solutions I send out this week

[Iterators and Generics](http://cs61bl.org/su17/materials/lab/lab10/lab10.html): Nice reading for Iterators and Generics!

[Nested Classes](http://mindprod.com/jgloss/nestedclasses.html#EXTENDING): Interesting info on how access control works with nested classes!

[Advantages of Exceptions](https://docs.oracle.com/javase/tutorial/essential/exceptions/advantages.html)