---
tags: labs, spr22
---

# Lab 1 (CS17/111/112/19): Using Classes and Interfaces in Java

**The goals of this lab are to:**
- help you practice with implementing trees in Java
- help you practice writing test cases in Java
- help you practice writing class-interface diagrams
- get you familiar with Javadocs, Java's documentation system
- make sure you are able to upload assignments for grading

### Getting Starter Files with GitHub

You can clone the starter files for this lab at [this GitHub Classroom link](https://classroom.github.com/a/w52Hw6bB
).

We will be using GitHub Classroom for CS0200. Refer to the [GitHub guide](https://hackmd.io/@csci0200/HJI-Zo4TK) if you are unfamiliar with it. Make sure you push your code regularly to back it up!

### Pair Programming

In CS0200's labs, you are expected to pair-program with different partners in each lab. Pair programming means that you're always working on the same piece of code, and one of you is typing while the other is telling them what to do and watching for mistakes, switching off coding and following in roughly 15 minute intervals (you can choose your stopping points). Mostly, just make sure everyone gets to code and also everyone gets to coach pretty equally. You should read our [Pair Programming Guide](https://hackmd.io/388rC8byRXq0bTRsFY1-WQ)!

:::info
**Note:** You should ignore any TODO comments you see in the code related to Javadoc comments until the end of the lab!
:::

### Back to Binary Search Trees!
Remember BSTs (binary search trees)? Well, get ready, because it's time to revisit them! As a refresher, in a binary tree, every node has 0, 1, or 2 children. Here are functional programming datatypes for binary trees:

In ReasonML

type tree ('a ) = Leaf | Node ('a, tree ('a ) , tree ('a ) )

In Pyret

data BinTree:
  | leaf
  | node(value :: Number, left :: BinTree, right :: BinTree)
end

A binary *search* tree has additional constraints on the order or structure of the nodes: for every node $p$, all the values in $p$'s left subtree are strictly less than the value of $p$, and all the value in $p$'s right subtree are greater than or equal to the value of $p$. In the example below, the blue circles represent the nodes and green circles represent the leaves.

We want to implement five methods on BSTs:
* `insert(int n)`, a method that inserts a value into the BST and returns the resulting BST.
* `contains(int n)`, a method that returns true if the given value is found in the BST, and false otherwise.
* `treeDepth()`, a method that returns the height of the longest branch in the tree
* `getLeft()`, a method that returns the left child of a Node / Leaf
* `getRight()`, a method that returns the right child of a Node / Leaf

**Task:** Declare these methods in the `IBST` interface provided in the stencil.

:::success
**Checkpoint!** Call over a TA to check your work.
:::

## Implementing Methods
For the following tasks, make *both* the Node and Leaf classes implement the IBST interface and its methods.

**Task:** Write the method `insert` that takes a number as its input, creates a new node with the number as its data, and then inserts that node into the BST.

**Task:** Write the method `treeDepth` that returns the height of the longest path down the tree.

**Task:** Write the method `contains` that takes a number and returns a boolean indicating whether a node with that number as its data is in the BST.

**Task:** Write the `getLeft` and `getRight` methods that return the left and right child nodes, respectively.

**Task:** Navigate to the test file `BSTTest.java`. Using `insert`, build two different binary search trees using the numbers 1 through 6 (you'll get different trees by adding the elements in different orders).

**Task:** Develop a good set of tests for `contains`. The point here is to think about what combination of tree shapes and numbers cover the different cases of the algorithm. You can draw your trees on paper, indicating which numbers you would use for good `contains` tests. Write a short description of the situation that each tree/input is trying to test (e.g., we want to see your testing strategy, not just that you came up with some collection of examples.)

**Task:** Develop tests for `treeDepth` in the same style as the `contains` tests.

:::success
**Checkpoint!** Call over a TA to check your work.
:::

## Javadocs
*Javadoc* is a system that generates documents in the form of web pages from annotated Java code. That is, if you comment your Java code using Javadoc annotations, then you can use the Javadoc system to automatically generate web pages that document your program. In CS0200, you will not be required to use Javadoc for document generation, but you will be required to write your comments using standard Javadoc annotations.

#### Javadoc Comments

The Java compiler recognizes comments delimited by `//` or `/* ... */`. Javadoc recognizes comments delimited like this: `/** ... */`. These comments are placed above the class, variable, or method about which you are writing a comment.

#### Javadoc Tags

The keywords that are included in Javadoc annotations are called *tags*. Tags inform the Javadoc system of the type of information a comment contains. Below we list a few of the tags of interest in CS0200. To learn more about built-in tags, and how to make your own, check out the [Javadoc Documentation](http://www.oracle.com/technetwork/java/javase/documentation/index-137868.html).
* `@param`: Documents a specific parameter (argument) of a method or class constructor.
* `@return`: Documents the return value of a method.

You should have a `@param` tag for each parameter passed into a method you write. Furthermore, you should have a `@return` tag for the return value of each method you write (unless it returns void).

Now, let's put together everything you've learned about Javadocs! The GitHub data you pulled has a class called `SongOfThe2000s.java`. Modify that file to put appropriate Javadocs on the `SongOfThe2000s` class and its methods.

The class represents a song from the 2000s and has private variables representing its name and listener count.

package sol;

// TODO: Write a Javadoc comment for this class
public class SongOfThe2000s {

    private String name;
    private double listenerCount;

    // TODO: Write a Javadoc comment for this constructor
    public SongOfThe2000s(String name, double listenerCount) {
        this.name = name;
        this.listenerCount = listenerCount;
    }

    // TODO: Write a Javadoc comment for this method
    public String getName() {
        return this.name;
    }

    // TODO: Write a Javadoc comment for this method
    public double getListenerCount() {
        return this.listenerCount;
    }
}

:::info
**Note:** When you write Javadoc comments for a method declaration in an interface, you don't need to write Javadoc comments when those methods are implemented in a class.
:::

**Task:** Fully fill in the required Javadoc comments to `SongOfThe2000s` and the rest of your Java files (`Node`, `Leaf`, `IBST`).

**Hint:** In IntelliJ, if you type `/**` followed by enter (above an existing class, variable, or method declaration), IntelliJ will auto-generate some of the tags for you!

<!-- ### Searching for Songs!

Binary search trees aren't just for numbers. We can use them to organize any type of data in which two elements can be "ordered". In the case of `SongOfThe2000s`, some ways we could order them is by their name or listener count. Let's adapt our code to sort `SongOfThe2000s` by listener count.

**Task:** Make a copy of the `IBST` interface in your `sol` folder, changing it so that it now uses `SongOfThe2000s` instead of `int`. Give it a descriptive name starting with `I` (representing an interface), such as `ISongBST.java`.

**Task:** Make a copy of your `Node` and `Leaf` classes changing them so that they now use the interface you just created above. Additionally, make sure the value they store is of type `SongOfThe2000s` Give them descriptive names, such as `SongNode.java` and `SongLeaf.java`.

**Task:** Modify `insert` to order `SongOfThe2000s` by their listener count.

**Task:** Add a method `leastPopular` to your nodes and leafs that returns the name of the `SongOfThe2000s` with the least amount of listeners in the binary search tree (assuming its already ordered by listener count). -->

:::success
**Checkoff!** Huzzah - you've finished the lab! Call over a TA to get checked off.
:::

______________________________

*Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS0200 document by filling out the [anonymous feedback form](https://docs.google.com/forms/d/e/1FAIpQLSdFzM6mpDD_1tj-vS0SMYAohPAtBZ-oZZH0-TbMKv-_Bw5HeA/viewform?usp=sf_link).*