## CSE 131 Module 8: Abstract Data Types

Important!

Before beginning any work, do a Team...Pull in your repository.

### Exercises

In the repository you are using for this course, look inside the exercises source folder, and you will see assignments organized by name. Before continuing on to the next portion of the asynchronous material, spend some time on the exercise. When you are finished, commit your code so that credit for the exercise can be given.

It is not so important that you get the exercise exactly right. It is important to work through it as best you can before you look at the solution or continue with other work in this module.

Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

### Thinking about how to use lists

You do not write code in this exercise. Instead, consider each numbered question below and write down some responses that come to mind. You are at this point quite new to lists, so take your time and try to think of the best responses you can.
To record your work here, create and edit a new Java class ThinkingAboutLists in the exercises8 package of your exercises folder. You can enter the text in comments there.
1. What are some examples of lists? In the introductory video, I spoke about a list of books that I read this summer and a list of temperature readings. Those might be declared ast List<String> and List<Double>, respectively. The String could repesent the title of each book I read, and the Double could represent each temperature reading.

Think of possible applications of the other two types of lists covered in the video:

• List<Color>
• List<Account>
For each of the above, try to find an example where at least one of the following is true:
• The order of elements in the list is important.
• There can be duplicates in the list.
2. Suppose we spin a Roulette wheel some number of times, and we must report the numbers that show on the wheel when it stops. Note that:
• The same number may appear multiple times.
• The order of the numbers' appearance is important.
Thus, we need a List<?>, but what type of element should be in this list?
3. Can you think of a problem where having List<Boolean> would be useful?
4. Suppose we have some kind of a List. What kinds of operations might we want to perform on that List?
After completing this exercise:
Commit and push any files you have changed so that you receive credit for your work!

Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

### Use a List<String>

Let's try using the code from the end of the video. If you get stuck, look at the solution video, but only as far as it takes you to get unstuck, then try going forward on your own again.

To get started, open the UsingLists class in the exercises8 package of the exercises folder.

Some important points:

• We declare the list using the abstract type List.
• We instantiate it using a concrete type, such as LinkedList or ArrayList.
For now, use LinkedList.
• Eclipse will say it doesnt know what those types are. You have to mouse-over the offensive code and allow eclipse to suggest what you should do.
The classes you want are found in java.util so be sure to choose those.
• The List needs a type parameter, which in this case should be String.
• Using your list, add the following:
• "open mouth"
• "insert food"
• "chew"
• "chew"
• "swallow"
• Print the list and verify that it's right
• Add some more things to the list and print it again
• Delete one thing and print it again
Once you are done, change the implementation from LinkedList to ArrayList, and verify that you see no difference in the program's behavior (this part is not on the video).
After completing this exercise:
Commit and push any files you have changed so that you receive credit for your work!

Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

### Investigating the Set interface

Often in designing or writing software, it helps to use code that others have written. We have done exactly that with the List interface and its LinkedList implementation.

In this exercise you will investigate the Set interface using Javadoc documentation. You will then write code to use the Set interface via its HashSet implementation, and observe what happens with the eating example from the previous exercise.

You will no doubt find some of the documentation confusing, as it refers to concepts we have not studied. Nonetheless, browsing such documentation is commonplace at all levels when searching for code that may be of use as you develop software.

Try to skim over the confusing parts to pick up the essential parts of the documentation:

• What methods does this interface or class offer?
• What parameters do those methods need?
• What kind of return result can be expected?
The methods are listed alphabetically, which does not necessarily cover the most important methods first. Skim to get what you need.
1. Browse this documentation for the Set interface.
• Find methods that resemble those you used for List.
It is no accident that the same methods are here: Java implements its collection objects with great consistency.

Can you find the Javadoc documentation for the List interface on your own, using Google?

Such documentation is usually found by searching for the fully qualified class, as: java util list.
• Remind yourself of the differences between a Set and a List:
• Order is important in a List. The elements of a Set occur in no particular order.
• A List can have duplicates. Attempts to add an already present element to a Set do not succeed.
2. In the documentation, find the list of All Known Implementing Classes. All of these implement the Set interface, but:
• The method of implementation will vary
• The performance of the implementation will vary
• Some implementations may exceed the Set interface by offering additional functionality.
3. Browse the documentation for HashSet, an implementation of the Set interface.
4. Open the UsingSet class of the exercises8 package in the exercises folder.
• Copy and paste the code from UsingList, but change the type of the collection
• from List to Set
• from LinkedList to HashSet
After completing this exercise:
Commit and push any files you have changed so that you receive credit for your work!

Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

### Generating hashCode and equals for an object you design

In this exercise, you use eclipse to auto-generate useful parts of a class. Try this on your own, but as you need help, run the solution video only as far as necessary for you to move forward again on your own.
1. Find and open the Point class in the exercises8 package of the exercises folder.
2. Based on the comment you see there concerning has-a, declare the instance variables for this class, calling them x and y.
3. Auto-generate the constructor by choosing Source and then Generate Constructor using Fields….
4. Choose the fields x and y, and finish to generate the constructor.
Admire the work eclipse just did for you.
5. These fields will be immutable, so edit the declarations for x and y and add the final attribute.
This ensures that the values of x and y can be set only by the constructor.
6. Now use eclipse to generate the getters for x and y.
Usually the menu you are presented would also offer to generate setters but eclipse knows the relevant variables are final and cannot be set after construction.
7. In the main() method, construct and print a Point or two and verify that things look good.
They should not look so good. When you print a Point, you get an ugly and uninformative String. To get something better, we must override the toString() method.
8. Use eclipse similarly to generate a simple toString() method.
This, and the subsequent work below, is accomplished also via the Source menu.
9. OK we are ready to make a Set of some points. Put the following code in the main method:
```Set<Point> set = new HashSet<Point>();
System.out.println("Set has " + set);
```
• Recalling that sets should have no duplicates, you the output from the above code should show the set having the same point twice.
• This is because Java is using its built-in notion of equality: are two objects exactly the same object (as in, the same reference in memory)?
• We need to change this behavior, so read on.
10. Now let's use eclipse to generate hashCode() and equals(Object other) methods.
You must pick the attributes (instance variable names) upon which you wish equality to be based.
11. Rerun your code and make sure that two Point objects with the same coordinates cannot both be contained in the same set.

#### Further exploration

1. What happens if hashCode() returns a random integer? Try:
```public int hashCode() {
return (int)(Math.random()*100000);
}
```
• What behavior do you see in the set?
• Why do you see that behavior?
The above code makes hashCode() inconsistent, breaking a portion of the contract concerning object equality.
2. What happens if hashCode() always returns the same result? Try:
```public int hashCode() {
return 0;
}
```
• Does this work?
• What impact does the above hashCode() have on performance?

#### Now try lists

Go back and change the Set and HashSet of your code to use List and LinkedList, respectively.

1. You should see duplicates. But that's OK for lists.
2. Intentionally break KBD>.equals(Object other) by returning false always.
What aspect of the contract does this break for .equals(Object other)?
3. What behavior do you see?
Adding to a list does not consult .equals(Other object), so you should see no difference.
4. Now ask whether the list .contains(new Point(131,132)).
Nothing should be found in the list with the broken .equals(Object other).
5. Revert the code back to its proper hashCode and .equals(Object other).
After completing this exercise:
Commit and push any files you have changed so that you receive credit for your work!

Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

### Implementing a StockHolding object

OK now you are pretty much on your own:
• I will tell you a story.
• You will design an object.
• Create this object from scratch in the exercises8 package of the exercises folder.
As usual, if stuck, consult portions of the solutions video.

#### The story

A StockHolding object:
has-a
• immutable String identifying its name (e.g., IBM)
• immutable String identifying its owner (e.g., Ari)
• number of share (int) that can change over time
• price per share (int) that can change over time
and it needs:
• A constructor
• A toString()
• hashCode() and equals(Object other)
You should generate the above automatically, not by hand!
After completing this exercise:
Commit and push any files you have changed so that you receive credit for your work!

Before starting this exercise:
Be sure to update your repository before beginning this assignment, so that you receive any code you need.

### Applying an interface

Do your work in the exercises8 package of the exercises folder.

#### The story

Define a PersonalProperty object:
has-a
• immutable int for its initial value
• immutable int representing the years since its initial value was established
and it needs:
• A constructor that takes in values for the two instance variables
• A method int depreciatedValue() that returns the value of the property according to the formula:
initiaValue × 0.80yearsOld
• A toString()

After defining the above class, adapt it to implement the Valuable interface:
```public interface Valuable {
public int getLiquidValue();
}
```
After completing this exercise:
Commit and push any files you have changed so that you receive credit for your work!
```

```
```

```
```

```
```

```