<style> h3 { border-bottom: 1px solid #ccc; } section { margin-bottom: 2rem; padding: 0em 1em; padding-bottom: 1em; border-radius: 4px; background-color: #f7f7f7; border: 1px solid #ccc; } summary { font-weight: bolder; } summary:hover { text-decoration: underline; } .todo { color: #ff00ff; border: 2px dashed #ff00ff; padding: 0em 1em; border-radius: 5px; //display: none; // UNCOMMENT TO HIDE TODOs } </style> # **Homework 3: Hashtables** **Due: Friday, October 11th at 11:59pm** **Collaboration policy**: This assignment uses the default course [collaboration policy](https://docs.cs200.io/collaboration-policy). Roughly, you may discuss conceptual issues, but you must code alone. See the policy for details and examples of what is and isn’t allowed. **For questions**: We'll maintain an **HW3 FAQ/reading list post** on Ed with a list of important clarifications and common questions. If you're confused or stuck, please check this list first. Ed is a great discussion resource--please take advantage of the questions and answers we have already posted! # Learning objectives This assignment has you practice the following course objectives: - Implementing common data structures - Understanding hashtables - Working with exceptions - Writing good test cases - Making design choices in real-world settings # Overview In this assignment, you'll gain some practice thinking about hash tables from two perspectives: - In **Part 1**, you will implement a chaining-based hash table based on an array of lists, similar to the version you saw in lecture - In **Part 2** is more open-ended and design-oriented: you will gain some perspective on *testing* by writing some tests for a program that uses Java's built-in hash tables to implement a system. You'll consider how the system could be modified to accommodate different users' requirements, and write some tests to specify what you'd like a new design to do (you won't do the implementation, though--just the testing). **Note that parts 1 and 2 are independent**--you can work on them in any order. If you get stuck on one part, you can switch to the other one and come back to it later! **Assignment Link**: Use this [GitHub Classroom link](https://classroom.github.com/a/Btl1-GWB) to get the stencil code for this assignment. **Be sure to follow the [Java Stencil setup guide](https://docs.cs200.io/s/java-stencil-setup-guide)** for instructions on how to do this. **Style Expectations**: For all future assignments, including this one, we expect your code to conform to the [CS200 Java Style Guide](https://docs.cs200.io/s/java-style-guide). ## Stencil code The `src` folder has the following files (**which you should not modify**): - `IDictionary.java` containing `interface IDictionary<K, V>` - `KeyNotFoundException.java` containing `class KeyNotFoundException` - `KeyAlreadyExistsException.java` containing `class KeyAlreadyExistsException` You will, however, alter the files that are in the `sol` folder: - `ChainingHashTable.java`, containing `class ChainingHashTable<K, V>` AND `KVPair<K, V>` - `Homework3TestSuite.java` - `Yulp.java`, containing `class Yulp` The `sol` folder also contains a collection of files that you might choose to modify (`Member.java`, `Review.java`, and `Restaurant.java`). # **Part 1: Chaining Hash Tables** In this problem, you will implement your own hash table based on an array of lists, as we saw in lecture. In your implementation, you will use Java’s `LinkedList` for your list implementation. :::warning **Important**: Since the point of this problem is for you to see how hash tables are built when they don’t already exist in a language. Therefore, **you may NOT use Java’s hashmaps or hashsets in your implementation.** ::: In your `sol` directory, we’ve given you a class `ChainingHashTable` that implements the `IDictionary<K, V>` interface. This class has: - A constructor that takes in the size of your hashtable - An inner class` KVPair<K, V>` for combining keys and values (as shown in lecture 10/4) - Several methods from the `IDictionary` interface that we must implement: - `lookup`: we’ve implemented this method for you, but it will be your job (later) to implement its helper method `findKVPair` - `update`: we’ve written for you in its entirety - `insert` and `delete`: you must write these methods on your own (more info later in the handout) - Overridden methods for `equals` and `toString` that you should implement (later). ## The Constructor ### **Task 1-A**: Set up the data and constructor for `ChainingHashTable.java` To begin your implementation: - Create a field `data` in your `ChainingHashTable` class, which will be the underlying array to make your hash table. As we discussed in lecture, each array slot will hold a `LinkedList` of `KVPair<K, V>`. - Fill in the constructor for `ChainingHashTable.java`. The `ChainingHashTable` constructor should take as input a size variable, which specifies the size (number of slots) of the table. Attempts to make a hashtable with a negative or 0 size should throw an `IllegalArgumentException` with the error message "Invalid size." When the constructor is done, you should have a valid empty hashtable. :::warning **How to set up the `data` field in your constructor**: The syntax for setting up the underlying array is a bit tricky due to how Java's type parameters (eg. `K`, and `V`) work with arrays. You should set up your array like this: ```java this.data = (LinkedList<KVPair<K,V>>[]) new LinkedList[size]; ``` This line creates an array of `LinkedList` objects, then uses a **cast** in parentheses to tell Java that the array type is a Linked list of `KVPair<K, V>` objects, which is what we want. We need to do this because Java doesn't typically allow creating arrays of *generic* types, but this is possible with a cast. <br /> After adding this, **you might see warnings about "unchecked casts"**. This is expected. It's generally not good to ignore warnings in your code, but in this case we know the cause (and we can't really avoid it). To get rid of the warning, add the following line above methods where it appears (similar to how you write `@Test` on tests): ```java @SuppressWarnings("unchecked") ``` <!-- Typically, warnings such as these indicate a problem with your code, so you should not suppress them; you should pay attention to them! In this specific instance, however, we justify its use as we are trying to get around a Java limitation. --> ::: :::success <details> <summary><b><i>Hint:</i></b> Thinking about your data</summary> This task requires you to set up fields for the underlying data structures for the hashtable (which we discussed in class) and create the corresponding objects. The subtlety here is that you have to **completely set up the objects**. We’re leaving it to you to figure out what that means (that’s one of the learning goals of this assignment), but we have later tasks that will explicitly hint you toward this. Look back at the lectures on hashtables for an idea of what underlying data structure could be helpful here. </details> ::: ## Handling Exceptions Some of the methods in `IDictionary` throw exceptions (which can be seen in the method declarations in the stencil code). If the method declaration `throws` a specific exception, your code should throw that exception when appropriate. Some of the thrown exceptions are really for the *user* of the hashtable and aren’t useful for your own implementation. Therefore, you don’t need to catch these exceptions, but you should test for them. However, you may find situations in which the thrown exceptions are useful, in which case you should catch them and do something appropriate (we’re intentionally leaving this for you to think about). :::warning With that said, here are some concrete things to keep in mind about exceptions as you work on your implementation: - You may **NOT** modify the `throws` annotations (or anything else) in `src/IDictionary`. Work with the `throws` annotations that we have provided. - You should **NOT** just print out messages to the user just because an exception got thrown. **If you don’t see a reason to use an exception in the logic of your code, don't add a try/catch block**: this will *pass* the exception up to whatever code called your method (in our case, the test suite; normally, the user) to deal with it appropriately. See the code in the next section for an example of what this means for your tests. ::: <section> ### Important Java background: Testing Exceptions When working with your own Exception classes, your tests need to handle the fact that the methods you call might throw exceptions. **When an exception shouldn't happen**: In most cases, you'll be writing tests for *correct* behavior (eg. you add some data to the hash table, and then check to make sure it's there afterward). From Java's point of view, this code *might* throw an exception even though this shouldn't happen if the code is working properly... but it might if there's a bug! In situations like these, you should add a `throws` annotation to your test, which tells Java that you know an exception *might* get thrown if there's a problem. When this happens, the test will fail, and you'll get output you can use to debug: ```java import static org.junit.Assert.assertThrows; import static org.junit.Assert; @Test public void testExnNotExpected() throws KeyNotFoundException, KeyAlreadyExistsException { // NEW: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ // . . . } ``` **When you *want* an exception to occur**: You'll also frequently write tests where you *want* to check that an exception occurs: in this case, you want the test to pass when an exception is thrown, and fail when it is not. Junit, our tester, provides a special assert statement for this called `Assert.assertThrows`, which you can use like this: ```java @Test public void testExnExpected() { Assert.assertThrows(MyException.class, () -> someObject.codeThatThrowsException()); } ``` </section> ## Finding key-value pairs ### **Task 1-B:** Write test methods In `Homework3TestSuite.java`, write test methods that: :::info <details> <summary> <b>Requirements for Test Methods</b> </summary> - Initialize new `ChainingHashTable` objects - Call `lookup` and `update` on empty ChainingHashTable objects (an empty ChainingHashTable object has a positive initial size, but has no key-value pairs added to it) - Call on the `insert` method to add key-value pair(s) to the hashtables and use `lookup` to make sure the correct key-value pair(s) exist in the hashtables - Test the interaction between `insert`, `update` (which updates the value for a given key), and `lookup` (which looks up the value for a given key) - Call on the `delete` method to delete key(s) - Test for basic edge cases (such as a key not existing in a table) - Test more complex interactions between `insert`, `delete`, `update`, and `lookup` </details> ::: :::warning <details> <summary><b>Important Pointers about Writing Tests 🧪</b></summary> Separate these out into multiple test methods – we want you to write these tests now to think of example hashtable operations and how all of these methods might interact with each other, but some of the tasks below will have you run some tests and not others as you start implementing the methods. Do not go overboard writing tests for this task (you will add more once you implement `equals`), but be confident that you’ve thought through and written tests that show examples of the possible interactions of the four methods. If a key is not found or already exists in the table, the appropriate methods will throw a `KeyNotFoundException` or `KeyAlreadyExists` exception (check the stencil code to see if a method should be throwing such an exception). </details> ::: ### **Task 1-C**: Write `findKVPair` Fill in  `findKVPair`, which searches your data structure for the KVPair for a given key value. This method should throw a `KeyNotFoundException` if the given key is not in the hashtable. **Reminder**: You are welcome to implement additional (helper) methods if you wish. If they are only for use within your class, mark them as private. :::success <details> <summary><b><i>Hint:</i></b> About hashing and <code>hashCode</code></summary> Recall that hash tables are backed by a hashing function, which maps a key to an index in the array. You can use the built-in Java hashCode method (e.g. <code>int hash = myValue.hashCode()</code>), which returns a signed (either positive or negative) integer. You should take the absolute value (<code>Math.abs(hash)</code>) of this integer and use the modulo (<code>%</code>) operator to map this to a value that will fit in your array. </details> ::: ### **Task 1-D**: Make sure everything works :) Once you have `findKVPair` implemented, you should have an empty hashtable on which the `lookup` and `update` methods (which we provided) can run. **Run your empty-hashtable tests for** `lookup` **and** `update` **NOW.** The subtlety we warned about in the constructor regarding setting up the objects can show up on these empty tests if you missed something. Making sure the empty case works now could save you a lot of debugging headaches later. You have not implemented `insert` and `delete` quite yet, so don’t run any tests that use those methods. ## Implement insert and delete ### **Task 1-E**: Write `insert` Fill in the `insert` method, which takes a key and a value and stores the value for the given key in the underlying hashtable, unless the key was already in the hashtable. - If the key was already in the hashtable, throw a `KeyAlreadyExistsException` and leave the hashtable contents unmodified. ### **Task 1-F**: Test `insert` Run your tests that use the `insert` method but not the `delete` method. If you get an unexpected problem, ask yourself whether you could avoid it by modifying the constructor (this is another place where the constructor subtlety we warned about could arise). :::warning <details> <summary><b>Warning: OO Design 👀</b></summary> We have mentioned in lecture how good OO design avoids code that has to ask what type something is. Asking whether something is equal to `null` is often a type check in disguise. If your code asks whether something is `null`, consider whether that is actually necessary (this again connects to the constructor subtlety). </details> ::: ### **Task 1-G**: Write `delete` Fill in the `delete` method, which removes a KVPair from the hashtable. The method header in the stencil indicates which exceptions this method can throw. 🤽 You are welcome to use [LinkedList methods](https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/LinkedList.html) if you think they will help (but this is not required). ### **Task 1-H**: Test! Run all of the tests from Task 1-B and debug your code. ## Implementing toString and equals ### **Task 1-I**: Write `toString` Fill in `toString` in the stencil file. Use a format such as: [key1: value1, key2: value2, ...] (small variations on this are also fine – the goal is to print the key/value mappings, but not the internal indices). The order in which the keys print out doesn’t matter. :::success <details> <summary><b><i>Hint:</i></b> How should we approach this?</summary> Consider nested `for` loops! </details> ::: :::warning **_Warning:_** Since your format may not match our wheat solution format exactly, do not put tests for this method in `Homework3TestSuite.java`. Write your own small testing file to test toString, or create a main method to print some sample tables out. ::: ### **Task 1-J**: Write some tests Write some tests that: - Initialize multiple `ChainingHashTable` objects and insert some values into them - Call on `equals` to check if two of the hashtables you initialized are equal. Two `ChainingHashTable` objects should be considered equal if they have the same set of key-value pairs. They could have different underlying array sizes and different organizations of KVpairs within the arrays (including the same KVPair being stored in different array slots in otherwise equal arrays). ### **Task 1-K:** Write `equals` Fill in the `equals` method in the stencil file. There are no running-time restrictions on your solution. :::success <details> <summary> <b><i>Hint:</i></b> How do we test if two <code>ChainingHashTable</code> objects are equal? What does it mean for them to be equal? 🤔 </summary> This problem requires you to figure out how to iterate through one hashmap while checking its contents against the other. <code>findKVpair</code> may be helpful depending on how you break this down, but using it is not required. It may also be helpful to think of this problem as “are all KV pairs that are in hashtable A also in hashtable B, <i>and</i> are all KV pairs that are in hashtable B also in hashtable A?” </details> ::: ### **Task 1-L:** Test `equals` Test and debug your `equals` method. :::success <details> <summary><b><i>Hint:</i></b> Do you have issues with the <code>testEquals</code> test case?</summary> If you have issues with the testEquals test case, it is related to this method! Try to make sure your equals method checks all the requirements and nothing more. </details> ::: ## Testing ### **Task 1-M**: Expand your test suite Revise or add to your tests, as necessary, based on what you think would make a good test suite, and based on the wheat/chaff test results. To meet the testing requirements: - You need to catch a certain number (**but not all!!!!**) of the chaffs. See the [Grading](#Grading) section for details on which chaffs are required. Some chaffs are *very* tricky and are designed to catch very narrow bugs, so it's completely fine to not catch all of them! - You do **NOT** need to test `findKVPair`, `toString`, or any helper methods that you write in order to write `insert` and `delete`. :::success **Helpful testing tips** - Since your class is generic, be sure to use multiple key and value types in your testing. - Since we are working with a mutable data structures, don’t forget about `@Before` methods that can be used to set up your data across tests. This can make your life easier! - **Don’t forget to test exceptions!** You should test for both `KeyNotFoundException` and `KeyAlreadyExistsException` ::: One again, :sparkles:**you do not need to catch all of the chaffs**:sparkles:. See the [Grading](#Grading) section for details on which chaffs are required. # Part 2: Design decisions for Yulp: a restaurant review system This part of the assignment is about testing and design. You'll gain some practice thinking about code that implements a small *application*: something that uses data structures like hashmaps and lists to support users as they do something. In any application, users have different (and *conflicting*!) constraints on what they want the system to do. To get you thinking about this, we'll give you a small, working, example application and a pair of *stakeholders*: users who have goals on how they want the system to be extended. You'll play the role of a designer or product manager who needs to consider the system as it is, and decide how it *would* be extended, taking your pair of users into account. To demonstrate your design, you'll **write some tests** to show what kind of behavior you *want* the system to have, but **you won't write the actual implementation**! (Imagine you would bring this to a larger team to review, first, then someone else would implement the code to fit your tests.) To be clear up-front: **This is an open-ended assignment and there is no correct answer.** We want to see how you grapple with making a technical design choice when you have different goals, and then communicate this by writing some tests. We'll explain what this means in more detail in the rest of the assignment. <section> ## Background: Java’s built-in hash tables (HashMap and HashSet) In this part, you'll see code using Java's implementation for hash tables and sets: - A `HashMap` uses a hashtable to map keys to values, similar to the hash table we've seen in lecture. Look [here](https://brown-csci0200.github.io/assets/lectures/15excnshashmaps/Lec15_whiteboard.pdf) for some common HashMap syntax, or read Java's documentation [here](https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/HashMap.html). - A `HashSet` ([java doc]((https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/HashSet.html))) implements the Java interface `Set` ([doc](https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/Set.html)). A set is an **unordered** collection of objects that has **no duplicates**. In Java terms, this means that a set cannot hold two elements that are considered equal (using `.equals`). So, if we call a Set’s `add` method on an object already contained within the `Set`, the `Set` will not change (see the documentation for more details). Hashtables and sets are related: Since hash tables cannot have duplicate keys, a common implementation for a set is to use a hash table, but ignore the values! </section> ## Scenario: a restaurant review system Imagine that you are implementing a restaurant review system, such as Yelp (here, we call it "Yulp"). In such a system, members add new restaurants, search for restaurants, and leave reviews. To help users search for restaurants meeting specific criteria, every restaurant has a set of *tags* that highlight some information about them. We've provided a basic implementation for the Yulp reservation system in `Yulp.java`. Here's an example of how it might be used: :::success **Reading this for the first time?** **Don't go open up `Yulp.java` yet.** Since this is a design assignment, you don't need to understand how the code in `Yulp.java` works in detail. Before opening up the code, keep reading here to understand what we're asking you to think about (ie, how to think like a product manager). ::: ```java public static void main(String[] args) { Yulp y = new Yulp(); // add two restaurants, each with name, address, and tags Restaurant bar = y.addRestaurant("Mango", "22 15th st", new String[]{"bar", "open late", "pizza"}); Restaurant pizza = y.addRestaurant("Nonna Pie", "10 Main st", new String[]{"pizza", "family friendly"}); // Search for restaurants by tag System.out.println(y.lookupByTag("pizza")); // Mango, Nonna Pie System.out.println(y.lookupByTag("vegetarian")); // No results! } ``` **The implementation we've given you for `Yulp` already works**--the actual code that does the job isn't what interests us right now. What's most important is the data it stores, and what methods it provides to interact with the data, and how we might want to change this based on our users. With that in mind, here's a sketch of the fields and public methods that implement `Yulp`. Internally, this system uses several hashmaps keep track of all the restaurants and users, as well as to support users searching for restaurants by tag, and editing tags: ```java public class Yulp { // **** Fields **** HashMap<String, Member> allMembers; // map usernames -> Member objects HashSet<Restaurant> allRestaurants; // set of all restaurants // Map of tag to list of restaurants with that tag HashMap<String, LinkedList<Restaurant>> tagData; // map of restaurant to a map with a list of changes made // to each of that restaurant's tags HashMap<Restaurant, HashMap<String, LinkedList<String>>> tagHistory; // **** Methods **** public void addMember(String username); public Restaurant addRestaurant(String name, String address, String[] tags); public Set<Restaurant> lookupByTag(String tag); public void addTag(String tag, Restaurant toRestaurant, String byUser, String reason); public void removeTag(String tag, Restaurant toRestaurant, String byUser, String reason); } ``` :::info <details> <summary>What is a HashSet (as seen in the above code)? </summary> In class so far, we have created lists to hold collections of elements. HashSets are collections (sets) of elements that get stored and retrieved in (effectively) constant time using the same ideas that underlie HashMaps. A HashSet uses the hashCode and % to place each element in an array index, which lets us check whether that element is in the set in (effectively) constant time. <br><br> In the `Restaurant` class, you will see the `hashCode` function that allows the class to be converted to an array index. </details> ::: ### Our focus: adding and removing tags Sometimes, people want to change the tags that were initially assigned to a Restaurant. To do this, the system has two methods: `addTag` and `removeTag`: ```java public void addTag(String tag, Restaurant toRestaurant, String byUser, String reason); public void removeTag(String tag, Restaurant toRestaurant, String byUser, String reason); ``` For example, here's how some user with username "ted" would add a tag: ```java // user "ted" adds a tag to an existing restaurant y.addTag("healthy", bar, "ted", "serves salad"); ``` As we said, Yulp already supports adding and removing tags--we've already provided you a design. **However, the current system allows any user to add or remove a tag from any restaurant**. As a product manager, it's up to you to decide how or if the system should be changed, based on how you decide to handle your users' goals. Read on to see your users' goals, and what we're asking you to do. ### The Yulp users Here are summaries of how different users want tag modification to behave in Yulp. You will work with one of the following three pairs of users, **based on the first letter of your brown email address** - **Pair 1 (Lupe and Jana)**: email addresses starting with a-h - **Pair 2 (Moe and Yash)**: email addresses starting with i-p - **Pair 3 (Carroll and Moe)**: email addresses starting with q-z :::warning **Heads up!** Your two users have conflicting values, it might not be possible to satisfy all demands--this is okay! We want you propose how to navigate those differences in deciding how the system would need to be updated. ::: #### Pair 1: Lupe and Jana - **Lupe** is an immigrant who has run a successful restaurant since arriving in this country 10 years ago. She's been hearing from other people around the area that a local hate group is targeting immigrant-owned businesses. Some restaurants have been defaced with graffiti or had their windows broken. Lupe wants to prevent undue attention by updating her Yulp tags to remove the "Guatemalan" label until the current threat subsides. She also wants Yulp to lock down her restaurant's entry so others can't add tags to it without her consent. - **Jana** is a local activist who wants to bring attention to restaurants headed by under-represented populations. She's been visiting lots of eateries to find such places. She wants to tag the ones she finds with the ethnicity or demographics of the owner (such as "women owned", "Black owned", etc) so she can help drive up their business. In the spirit of being helpful, she wants to do this without the owners knowing who was responsible for the new tags. #### Pair 2 - **Moe** owns a local pub that has been struggling to meet expenses. The pub's entry in Yulp is tagged as "pub" and "kid friendly". Moe knows he needs to attract new customers in order to stay open. His menu includes standard pub appetizers such as nachos, mozzarella sticks, and pretzel bites. Moe wants to be able to add the tags "mexican", "italian", and "vegetarian" to his Yulp entry in the hopes of getting more customers to notice his bar. - **Roy** is vegetarian by religion. He has been trying to build a local restaurant culture that is more supportive of his beliefs, which includes not eating in establishments where meat products are also served. Arguing that inaccurate tags interfere with a person's ability to adhere to their religious beliefs, he wants Yulp to allow removing the "vegetarian" tags from venues that also serve meat. #### Pair 3 - **Carroll** is extremely sensitive to noise, and can only dine comfortably at restaurants with a quiet ambiance. Yulp already includes "quiet" among its tags, but Carroll has recently had some bad experiences in which they went to restaurants that were labeled "quiet", but instead found them full of noisy kids. Carroll wants Yulp to prevent fundamentally conflicting tags (such as "quiet" and "kid friendly") from being assigned to any one restaurant, so as to protect the mental health of other customers with noise sensitivity. - **Moe** owns a local pub that has been struggling to meet expenses. The pub's entry in Yulp is tagged as "pub" and "kid friendly". Moe knows he needs to attract new customers in order to stay open. His menu includes standard pub appetizers such as nachos, mozzarella sticks, and pretzel bites. Moe wants to be able to add the tags "mexican", "italian", and "vegetarian" to his Yulp entry in the hopes of getting more customers to notice his bar. ### Task 2-A: Understand the current *system* (by skimming the code :eyes:) As product manager, your job is to understand how your company should extend the system to support your users' goals. To do this, you don't actually need to undestand how every line of code works, but you need to understand what the current system can do, so you can figure out how it might be changed. Doing this requires an important software skill: how to *look* at code, without getting bogged down with the details. We want you to get some practice with this. Yulp spans several files: - `Yulp.java` contains the `Yulp` class, which is where most operations happen - `Restaurant.java`, `Member.java`, and `Review.java` represent the different data types in the system (Restaurants, Members, and Reviews, respectively) - `YulpTests.java` contains some examples for how users may interact with the system (more on this later) To understand the code, here's what we recommend: 1. Open up each file in turn 2. Scroll through the file and **hide the code for each method**. You can do this by hovering your cursor next to the line number for the first line of each method, and clicking the little arrow that appears:  3. After you hide the contents of all the methods, **focus on what's left**: these are the high-level components of the system, which tell you what it does. Specifically, you're looking for: - The fields in each class: what data does each class hold, and how is it used? - What methods does each class have, and what do they do? How do you tell without reading the code? Read the javadoc! This is why we make you write it. :wink: Remember, **your goal is not to know how every line of code works** (though you can certainly read it if you want!). Once you feel like you have a rough idea, go onto the next task, and then circle back to the code as you need it. Overall, though, your goal is just to try and get the high level details, to fuel thinking about how you might propose a design change. If you have questions on interpreting the code/fields/methods/etc, feel free to post questions to Ed, come to hours, or discuss this part with others as well! Collab hours are a great place for this! ### Task 2-B: Design for your user pair Once you feel like you have an understanding of what the current system can do, think about how the system might be extended to better manage tags, based on your user pair. You'll write out your answers as part of task 2-D, so you may want to start taking notes in a document. In particular, some things to consider: - At a high level, how would you want to change the system's behavior? - Would you need any additional classes, fields, or methods? - Based on what you know about the current code (from the method headers, javadocs, etc.), how might the existing methods need to be changed? **This is an open-ended task**--you have the freedom to propose what you'd like the system to based on your interpretation of the situation: you could perhaps use the history of tag justifications in creative ways, add new types of members, consider other data you might want to have about members, and so on. Your choices just need to be practical, and be grounded in what you *would* change about the code. Overall, we want to see how you choose to grapple with making a technical design choice when you have conflicting user goals. In the next task, you'll start making your a bit more concrete, but you won't build it. (As product manager at a larger company, the next step would be to review your proposal with others, and then work with a team to get it implemented.) :::warning **Remember: We don't expect you to find a solution that satisfies both users, and there is no correct answer**. Rather, the goal is for you make a decision that you feel you can justify. We want to see you make an argument and propose technically-feasible implementations. The main thing we will check is whether your design reflects your reasoning, rather than being a random approach for which you felt you could suggest as code. ::: ### Task 2-C: Write some tests, and make your design sketch concrete Open up `YulpTests.java` and take a look at the tests. The example tests describe an interaction for adding and removing tags. For example, here's a test for adding a tag (in the original Yulp, where any user could add any tag to any restaurant): ```java public void testExampleAddTag() { Yulp y = new Yulp(); // Add two restaurants Restaurant rMango = y.addRestaurant("Mango", "22 15th st", new String[]{"bar", "open late", "pizza"}); Restaurant rNonna = y.addRestaurant("Nonna Pie", "10 Main st", new String[]{"pizza", "family friendly"}); // Start: Nonna is does *not* have tag "open late" Assert.assertFalse(y.lookupByTag("open late").contains(rNonna)); // User anh adds the tag "open late" to Nonna y.addTag("open late", rNonna, "anh", "They were open until midnight yesterday"); // Nonna now present when searching for the tag Assert.assertTrue(y.lookupByTag("open late").contains(rNonna)); } ``` Tests like these demonstrate some expected behavior of system: for example, making sure a user can search for a tag after it's been added. **Your task**: In `YulpTests.java`, write around 3-4 **tests** that demonstrate the expected behavior of your proposed design. To do this: - Your tests should cover cases where users both are allowed to add/remove tags, and (if you want to prevent certain users from updating tags) situations where they are not (see [this section](#Important-Java-background-Testing-Exceptions) for guidance on how to test exceptions) - Your tests should be roughly as long as the examples--don't try to be fully-comprehensive, or write mega-tests with tons of assertions. We just want to see some examples of your design's behavior. - Your design may need to use methods or fields that aren't present in the existing implementation. That's okay! However, **you should not implement these methods**. Instead, do the following: - **If you need to add any extra fields, add them to the class, but don't set them up**. You don't need to initialize anything, add fields to constructors, etc, but you should add your fields to your respective classes, so we can see what you mean - **If you need to add new methods, define the method, but leave it empty** (or just make it return something like null or 0 so Java doesn't complain). This is called a *stub*, and acts as a placeholder for someone to fill in later (like we do in your assignments :wink:). To be more specific on what this means: :::success **You may:** - You can add fields/instance variables or methods to the classes in the system (but don't bother setting them up) - Add *stub* methods (ie, blank placeholder methods that just return 0 or null) in place of any methods you want to create - Add any new classes you may want, and define their fields (but don't bother with any other components of them) - Define new exception classes, and write tests that check for exceptions ::: :::danger **You may not**: - Change the fields or headers of any existing methods. However, you can propose new methods (with different names) that would eventually replace them. - Move `addTag` or `removeTag` outside of the `Yulp` class ::: Overall, the goal is to create a sketch of your intended design, without actually implementing it. :tada: Therefore, **your tests will not pass--this is expected**! :tada: However, this is enough for us (or, hypothetically, others at your company) to see your design, which is what we want! :::warning **Your design/testing process isn't meant to take a long time**--again, we just want a sketch. If you find yourself taking more than an hour for this part, please feel free to leave a partial implementation and explain the rest in your writeup (for task 2-D)--we'll grade these parts together, so deferring some explanation and ideas to your writeup won't cost you points, so long as we can understand what you're doing. ::: ### Task 2-D: Put the answers to the following questions in `hw3.pdf`: 1. Who was your user pair? (<1 sentence) 2. How did you decide how to manage tags and why? Explain your decisions as if you were reporting to an ethical auditor who will determine whether your design is justified. Highlight and explain what you think is the most compelling reason that supports your design decision (1-2 short paragraphs) 3. If your implementation would require significant additional design sketching beyond the partial implementation you made to write your tests (such as using third-party libraries or work beyond what you could in an hour to sketch out), describe it by giving a plan along with any new fields and methods that would be needed. 4. What are the shortcomings of your design? Who are some short term and/or long term users or scenarios (beyond the ones we’ve asked you to consider) who could be adversely affected by your decision? (1-2 short paragraphs) 5. How might your approach to this assignment change if you were asked to consider the interests of users other than the two that you worked with (1-2 short paragraphs) # Handing in Before handing in your files, check that your solution is compatible with Gradescope. To do this, run `AutograderCompatibility.java`. Make sure that it compiles and runs without any errors. To hand in your files, submit them to Gradescope. - Submit `ChainingHashtable.java`, `Member.java`, `Restaurant.java`, `Review.java`, `Yulp.java`, `YulpTests.java` and a pdf (named `hw3.pdf`) containing your answers to Task 2-D to the **Homework 3: Implementation** submission - Submit `Homework3TestSuite.java` to the **Homework 3: Testing** submission. :::danger :warning: **WARNING:** Do not include any tests for Yulp in your `Homework3TestSuite.java`. Since your tests for Yulp explicitly WON'T pass, this will cause problems for testing part 1! ::: Once you have handed in your homework, you should receive an email, more or less immediately, confirming that fact. If you don’t receive this email, try handing it in again, or ask the TAs what went wrong. :::info <details> <summary> <b><i>Note:</i></b> If your code does not work with the autograder, you will be penalized. If there are any complications, follow these steps: </summary> <ul> <li>Make sure your testing submission passes the wheat. If it doesn’t, you should use the autograder output and the message in the failed autograder test to debug your test suite.</li> <li> If your test suite passes the wheat, run your implementation against your test suite. If this crashes, you should fix your solution code so that it is compatible with your test suite. </li> <li> If you are still having issues, please reach out to us at TA Hours or Ed. </li> </ul> </details> ::: # Grading Here is the breakdown of how this homework is graded: 1. **Implementation (autograded)** (30%): We are running 11 autograder tests on your implementation for Part 1 (`ChainingHashTable`). For this part, focus on fixing the autograder tests and writing and passing your own tests to earn this part of the homework score. <!-- 15 of them are visible to you, and 7 of them are not (this is to encourage you to thoroughly test your own code). --> 2. **Testing (autograded)** (30%): We are grading your assignment using <a href="https://docs.cs200.io/s/wheat-chaff-guide" style="text-decoration: underline">wheat and chaff grading</a>. For this assignment, **you are expected to pass the wheat and catch eight (8) of the twelve (12) chaining chaffs** to get full points on this part of the homework score. We suggest using the results of the wheat/chaff testing to self-assess how thorough your test suite is for running on your own code (**don’t worry if you missed a couple of chaffs, though** – a couple of the chaining chaffs in particular deal with very specific edge cases). 3. **Style checks (autograded)** (5%): We will check your code to ensure it complies with our <a href="https://docs.cs200.io/s/java-style-guide" style="text-decoration: underline">Java Style Guide</a>, most especially on following our conventions for method naming and including Javadocs.  For this part, make sure you’re following our <a href="https://docs.cs200.io/s/java-style-guide" style="text-decoration: underline">Java Style Guide</a>—if something doesn’t match, the autograder will provide feedback. <br><b>Note:</b> On Gradescope, this part is counted with the autograder score for implementation. 4. **Design and code structure** (35%): The TAs will manually grade your work according to some rubrics. To earn the points for this part of the homework score: Follow the design considerations for every task (for example, if a task for choosing a specific data structure says that the goal is “quick lookup,” your choice of data structure should prioritize that goal).<br> The `Yulp` work will graded as part of this item. We will check whether (1) your written response actually engages with the tension between your two assigned users, (2) your design is feasible to implement in code, and (3) your tests and sketch are consistent with your written response. We expect to see you state a position about how tag management should work, to reflect that position between your code and your description of other code that would be needed to realize your design. There is no "correct" answer to this. *** _Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS200 document by filling out our_ [_anonymous feedback form_](https://forms.gle/Myj4XSPx8cBJLxGt5)_!_