<style>h3{border-bottom: 3px solid black}</style> # Lab 1 (CS17/111/112/19): Using [Classes](https://i.redd.it/246by6ewudu31.png) 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 <!-- TODO: change links --> You can clone the starter files for this lab at this **[GitHub Classroom link](https://classroom.github.com/a/YjeeS0EF)**. **[Look here for instructions](https://docs.cs200.io/s/java-stencil-setup-guide#Accepting-an-Assignment-on-GitHub-Classroom)** on how to accept the assignment and open the code in IntelliJ. Refer to the [GitHub guide](https://docs.cs200.io/s/github-guide) if you are unfamiliar with it. Make sure you push your code regularly to back it up! ## How labs work: Pair Programming You should work on the labs using *pair programming*. This is a style of collaboration where both participants are always working on the same piece of code: one of you should be typing at the keyboard while the other should be helping to "navigate" by giving direction on what to do and watching for mistakes. You should alternate betweek roles at roughly 15 minute intervals (you can choose when to switch). Mostly, just make sure everyone gets a chance to both type at the keyboard and be "navigator" pretty equally. For details, see our [Pair Programming Guide](https://docs.google.com/document/d/1qJBZcPxNC6X1k95YH2w8K4ZC-K1IEy9eVbk4YuzeRXc/edit?usp=sharing). ## Starting note As you read through the code, you'll notice that there are several Javadoc comments (starting with `/**`) marked with `TODO` that ask you to fill stuff in. These are for the end of the lab, when we'll learn about how Javadoc can help document our code--**please ignore these TODOs until the tasks direct you to fill them in**. ## Back to Binary Search [Trees](https://cdn.drawception.com/drawings/802092/W4O0pyLKlr.png)! 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 data types for binary trees: In ReasonML: ```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 values 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. In this lab, we will implement five methods on BSTs: - `insert(int n)`, a method that inserts a value into the BST and returns the resulting IBST object. - `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 1 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, first make _both_ the Node and Leaf classes implement the IBST interface and its methods. **We recommend starting with Leaf, and then moving onto Node**. ### Task 2 Write the `getLeft` and `getRight` methods that return the left and right child nodes, respectively. ### Task 3 Write the method `treeDepth` that returns the height of the longest path down the tree. ### Task 4 Write the method `contains` that takes an integer and returns a boolean indicating whether a node with that integer as its data is in the BST. ### Task 5 Write the method `insert` that takes an integer as its input, creates a new node with the integer as its data, and then inserts that node into the BST. ### Task 6 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 7 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 8 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. ```java= 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; } } ``` ### Task 9 Fully fill in the required Javadoc comments to `SongOfThe2000s` and the rest of your Java files (`Node`, `Leaf`, `IBST`). :::info **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! ::: :::success **Checkpoint:** 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://forms.gle/Kpk1Do76jF2eVSUP8)_._