---
# System prepended metadata

title: 'Homework 2: Mutation'
tags: [Homeworks]

---

---
tags: Homeworks
---
# Homework 2: Mutation
### Due: Feb 5, 2021 (Anywhere on Earth)

## Learning Objectives
* Explain tradeoffs between mutable and immutable data structures in the context of a specific problem
* Write programs that can compile and run against a provided interface

## Assignment Link
Here is the [github classrooms link](https://classroom.github.com/a/czP_2AAh).

Please make sure to read [our gradescope submission guide](https://hackmd.io/jC-SEMn_RpiGqMH_EhsDMw) before handing in your assignment!
## Handing In
Begin by cloning the github repository found [here](https://classroom.github.com/a/czP_2AAh). The following files should be in the `sol` directory
* `Ticket.java` containing public class `Ticket`
* `EmptyList.java` containing public class `EmptyList`
* `AbsList.java` containing public abstract class `AbsList`
* `IList.java` containing public interface `IList`
* `NodeList.java` containing public class `NodeList`
* `Homework2TestSuite.java` containing public class `Homework2TestSuite`
* `BoxOffice.java` containing public class `BoxOffice`

After completing this assignment, you should be ready to turn in the following solution files:
* `Ticket.java` containing public class `Ticket`
* `EmptyList.java` containing public class `EmptyList`
* `AbsList.java` containing public abstract class `AbsList`
* `IList.java` containing public interface `IList`
* `NodeList.java` containing public class `NodeList`
* `Homework2TestSuite.java` containing public class `Homework2TestSuite`
* `BoxOffice.java` containing public class `BoxOffice`
* `TicketMemoryLayout.jpg`
* `MutationQuestions.txt`
* `ShallowCopyLayout.jpg`
* `DeepCopyLayout.jpg`

To hand in your files, submit them to Gradescope. Please make sure that `MutationQuestions.txt` is a plain text file, not a rich text file (you can check this by opening your submission in Gradescope and verifying that `MutationQuestons.txt` is readable). 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 in again, or ask the TAs what went wrong.

**Note:** If your code does not work with the autograder, you will be penalized. If Gradescope says that your code doesn’t work with our autograder, please contact the TAs via hours or Piazza.
## Testing
Make sure to test your code iteratively as you work! Testing and good code design make up a lot of your grade for this homework. Put your testing in the file `Homework2TestSuite.java`.

You should submit `Homework2TestSuite.java` to the **Homework 2: Testing** assignment on Gradescope. See [our gradescope submission guide](https://hackmd.io/jC-SEMn_RpiGqMH_EhsDMw) for an explanation on how we are grading your tests, and how you can use the Testing assignment on Gradescope to get a better understanding of the assignment.

# Problems

## Showtime (The Hunt Continues...)
The musical *Blueno and Juliet* by Oscar Orwell Peterson (known to his fans as O.O.P.) is coming to Brown and everyone wants tickets! Due to COVID restrictions, seats are in limited supply. Regular ticket sales have already sold out! Do not fret, because Professor Fisler can also award complimentary tickets to students who show up on time to their labs. Prof. Fisler tracks tickets seperately from regular ticket sales, but complimentary tickets still need to be recorded with the regular ticket sales list, since that data is used to hand out tickets for entry. The folks running the show would like you to implement their ticket system.

You show up on time to your first lab and your lab TA hands you a ticket and the show's playbill. You flip the ticket over to reveal another cryptic Blueno limerick:

*Tonight's players bid Blueno farewell*
*Come see what grim stories they'll tell*
*Of a blue metal bear*
*In a doomed love affair*
*By following the bill's URL*

![](https://i.imgur.com/LcqNQUS.jpg)


(Use tinyurl.com/blueno-and-juliet :))

## Tickets
You remember that Prof. Fisler was just talking about mutation and how data lives in memory. Understanding those concepts seems like a strong start for your ticket system. The box office helps you get the `NodeList` implementation Prof. Fisler used in class. 

A list of ints isn’t very helpful, though, so the first thing to do is modify that. The box office also gives you the `Ticket` class, which contains two fields: name and tier. There are three possible tiers: Platinum, Diamond, and Gold.

**Task:** Modify the `IList`, `AbsList`, `EmptyList`, and `NodeList` files so their elements are `Ticket` objects instead of ints.

**Task:** Now, in the `testLists` method of `Homework2TestSuite`, add more Ticket objects to `list1` and `list2` and draw a diagram representing the layout of these lists in memory. Note that you should only have one diagram containing both lists. Add a photo or scan of your diagram in your directory in a file called `TicketMemoryLayout.jpg`.

:::warning
We will review memory diagrams in class on Monday, 2/1
:::

## Lookup
Now that you understand more about how lists and objects are laid out in memory, you are ready to add more tools to successfully keep up with ticket orders. The box office asks you to modify the NodeList and EmptyList classes with a variety of features to make the attendance system both more effective and more difficult to sabotage.

The box office wants to be able to search the list for individual names, so that they can easily deal with requests

**Task:** Fill in `findTicketByName`. This method should take in the name of the ticket holder we want to find and return the Ticket object associated with that name. 

If it doesn’t find a `Ticket` that matches the input name, it should return throw a `RuntimeException` with the message `"Could not find ticket for [name]"`. For example, if you try `list.findTicketByName("Romeo and Juliet")`, and that ticket is not in the list, you should throw a `RuntimeException` with the message `"Could not find ticket for Romeo and Juliet"`.

## Mutation
:::warning
We will cover this in class on Monday 2/1
:::

People often change their minds, so your system needs the ability to give attendees the ability to change their ticket tier using their name.

**Task** Fill in `updateTierOfTicket`. This method should take in the name of the ticket and the new tier of that ticket. It should update all tickets in the list with the input name. If there are no tickets with that name, nothing should happen (don't throw an error).
- There are three possible tiers of tickets: `"Platinum"`, `"Diamond"`, and `"Gold"`. 

**Task:** In `Homework2TestSuite.java`, Update `lena`’s tier to Diamond using the `setTier` method in the `Ticket` class and write test cases to check the tier value in both of the lists. Then, change the tier of `lena` back to Platinum by using `updateTierofTicket` on `list2` and again write tests to check `lena`’s tier value in both of the lists and the object itself.

**Task:** What changes, if any, did you observe and why did they occur (or not occur)? Did changing one object affect the others? Why or why not? Put your answer to these questions, as well as the rest of the written questions labeled “Task” on this HW, in a plain text file called `MutationQuestions.txt` and upload it to Gradescope along with the rest of your submission.

Consider the following scenario (a continuation of the Showtime section): 

Carrie woke up at 5 in the morning to buy her tickets the moment they opened online. Evan was not so lucky, but he showed up to lab on time, so Prof. Fisler rewarded him with a ticket. Evan was so punctual that Prof. Fisler decided to upgrade his ticket after lab was done. Carrie decides to upgrade her ticket through sales.

When Carrie and Evan are walking in for the show, what ticket levels should Sales and Prof. Fisler see for Carrie and Evan? 

**Task:** Fill in the `buyTicket` and `awardTicket` methods in the `BoxOffice` class. Remember that changes made to tickets awarded should also be reflected in the `fullList` as well. 

**Task:** Why does your implementation of `buyTicket` and `awardTicket` guarantee that the scenario outcome is correct with respect to the levels seen at the end? Put your response into `MutationQuestions.txt`.

## Deletion
**Task:** Fill in `removeTier`. It should take in a tier and return a list that is the same as the original, but with all Ticket objects of the given tier removed. 

**Task:** Write tests that use `removeTier` to remove all Platinum Tickets in the regular sales list. If we call removeTier on the regular ticket list, what changes will happen in the complimentary ticket list? What in your code causes that behavior? Write a sentence or two explaining this behavior and put your response into `MutationQuestions.txt`.

Sometimes, people show up at the wrong time, or simply no longer want to attend the formal. As such, removing entire tiers is sometimes not enough. Your system should also be capable of removing individual tickets.

**Task:** Fill in the `equals` method in the `Ticket` class so that it returns true if the input object is a `Ticket` with the same name and tier as the `Ticket` that `equals` is called on.

**Task:** Using the new equals method that you wrote, fill in `removeTicket` so that it returns a list with all ticket objects equal to the input `Ticket` removed.

## Copying
Sales is excited about your new ticket system, but before they roll it out to students they want to make sure that it works. However, given the volume of complaints they’ve already received about incorrectly deleted names, they want you to test a copy of the ticket list instead of the ticket list itself, so that they don’t accidentally end up breaking it even more.

You will be writing two methods to “clone” the list. One should be a shallow copy, in which you make a copy of the list but do not make copies of the `Ticket` objects in it; the other should be a deep copy, meaning that you make a copy of every individual `Ticket` object.

**Task:** Fill in `shallowCopy` so that it returns a new list with the same `Ticket` objects as the original. Next, fill in `deepCopy` so that it returns a new list with objects that are copies of the `Ticket` objects in the original.

**Task:** Draw a picture of the memory layout after calling `shallowCopy` on `list1`. Next, draw a picture of the memory layout after calling `deepCopy` on `list1`.

Upload photos or scans of your diagrams to your working directory in files called `ShallowCopyLayout.jpg` and `DeepCopyLayout.jpg`, respectively.

## Crisis
**Task:** Write responses to the following questions in `MutationQuestions.txt`

There’s been a system crash and ticket data has been corrupted. We know the data was stable 3 hours ago, so we want to restore the data that existed at that time. What would you have to do in your code to enable this rollback? Which of the following approaches would work given the way your code is currently written?
* Keep a list of the previous versions. Once an hour, we call a function like storeSales(saleslist) that puts the current sales list in some other data structure so we can retrieve it later if needed
* Keep a list of shallow copies of saleslist
* Keep a list of deep copies of saleslist

No changes to your code are required for this question. We're only looking for a written response. 

## Reflection
**Task:** Write responses to the following questions in `MutationQuestions.txt`
* You’ve now implemented a functional version of lists in both Java and one of the functional programming languages that you encounted in an earlier intro course. How does Java’s object mutation affect this homework’s implemenation, as opposed to the implementations of lists that you have done in your earlier intro course?
* What problems might this list implementation create for users used to list implementations written in programming languages that do not support mutation, and what principles did you learn in this homework that help you mitigate those problems?
* In this segment of the course, we are talking about lists that can be changed in two ways: the nodes in the list can be changed, and the contents within the nodes in the list can be changed. For each of the following combinations, describe a situation in which you’d want that combination, and what that combination looks like in your code
    * Modify which nodes are in the list, can’t modify contents of nodes
    * Modify contents of nodes in the list, but can't modify which nodes are in the list
    * Can modify both the contents of nodes in the list and which nodes are in the list
    * Cannot modify either the contents of nodes nor which nodes are in the list

---

Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS 18 document by filling out our [anonymous feedback form](https://forms.gle/ym89rAZyBk8Hg3LNA)