CS231

Java and ArrayLists

The goal of this lab period is to get you started on the current assignment. In particular, you'll finish implementing an ArrayList class to use in the project, and you'll start thinking about implementing a shuffle method for the project.

In this project, you will be using Java's Random class, for which the documentation can be found here.

NOTE: Do not import anything else! You should not use Java's built-in ArrayList class.

Tasks

ArrayList Setup
Create a working directory for today's lab. Remember the folder structure you'll need to submit to Gradescope (see "Submitting Projects" on the main Projects page for a reminder). In that folder, download the following two files: ArrayList.java and ArrayListTests.java. The tester file is complete and is equivalent to what will be used to evaluate your code in Gradescope. The ArrayList class is partially complete, but is missing a few key methods that you will fill in. Remember to compile your code as you go! You can also choose to modify the tester to test only the methods you have written. (I recommend getting into the habit of doing this now! It will help you as we move through the course).

In general, it is very important to back up your work. There are a magnitude of external options to choose from, including Google Drive, Drop Box, etc. I find Google Drive to be the easiest to set up, but GitHub is obviously the 'professional' option.
Comments
First, read and fill in the missing pieces of the file header for the ArrayList class. Any Java file you submit in this class must include a comment header detailing the author and the purpose of the class, eg.
```
/**
* Author: FirstName LastName
* 
* Purpose of the class
*/	
```
This file is a good example of what we expect from you in all future classes you write.

Then take a look at the JavaDoc comments describing each method. This is the format we are asking you to use to write comments for all of the methods you write in this course. Note that each comment describing a method includes the method purpose, and any parameters and return values called out with @param name of the parameter and description, and with @return description of what is being returned, respectively.

We also expect you to write inline comments describing tricky or subtle lines of code. Take a look at line 83 of ArrayList.java for an example.
Fill in methods for the ArrayList class
The ArrayList class should support the following methods (we recommend working on them in this order). The method signatures have been written for you, but you need to fill in the remainder of the code.
- public ArrayList() the default constructor for the ArrayList that calls the existing constructor with initialCapacity set to 1.
- public void add(T item) adds item to the end of the ArrayList. If that would increase size beyond the current ArrayList capacity, first resize the ArrayList to have 2*capacity, then insert the item.
- public T get(int index)Retrieves the element at the specified position in the list.
- public void set(int index, T item) Sets the element at the specified position in the list to item.
Test your ArrayList
Run the supplied ArrayListTester on your ArrayList class and verify that it works. To get the assertions working, you must run the file using the -ea flag. Your command should look like this: java -ea ArrayListTests. Remember to do this for all Testers or the assertions will be ignored!
Create a Shuffle Class
This exercise uses your new ArrayList class and provides scaffolding for writing the Shuffle method that you will need to implement in your Deck class. Work through this exercise and refer back to it when you go to write your shuffle method!

Create a new file named Shuffle.java. In it, create a class named Shuffle that has a main method only. To start a class use the public class keywords followed by the name of the class, then start a block using an open curly bracket {. To define a main function, you can use the following structure:

Import the Random class into your file using the following syntax.
```
import java.util.Random;
```
+ (More Detail)

Similar to Python, Java uses an import statement to get access to standard or user-created libraries. The java.util library contains standard data types, algorithms, and capabilities. You can use wildcards in import statements, e.g. import java.util.*, but that may take more time when compiling your code. Good practice is to import only the packages you need.

public static void main (String[] args) {

+ (More Detail)

Unlike Python, but similar to C/C++, execution of a Java class begins in its main function. The main function must have the structure public static void main(String[] xxx) where xxx can be a name of your choice. Common practice is to use args or argv for the argument to main, following the C/C++ convention. The parameter to main will contain any strings provided on the command line when the program was executed.

Create an ArrayList of 10 Random Numbers
In your main function, declare and allocate a new ArrayList object named arr0 and a new Random object. Then use a for loop to add ten random integers between 0 and 99 to your ArrayList. Look at the documentation for the Random class to figure out how. Have your loop print out the random numbers (as they are generated) using System.out.println().

+ (More Detail)
Unlike Python, in Java you have to declare the type of each variable before you can use it. To declare a variable, use the name of the type and then the name of the variable.
```
ArrayList arr;
```
In Java you have to use the new keyword to allocate a new object. Use new followed by the name of the object you want to create called as a function, similar to Python.
```
arr0 = new ArrayList();
```
Of course, you can do this all on one line and declare and allocate the variable in one step.
```
ArrayList arr0 = new ArrayList();
```
ArrayLists are generic classes, which means they are designed to contain any type of object. The class is defined as ArrayList<T>, where T is a type variable. You will be making an ArrayList that should contain Integers, so you should specify Integer in place of T. For example, the following defines an ArrayList that can hold only things of type Integer.
```
ArrayList<Integer> arr0 = new ArrayList<Integer>();
```
If you leave out the type specifier in an ArrayList declaration, then it will be of type Object, which is the parent class for all classes. An ArrayList of type Object can hold references to any class type.

The ArrayList method add is the analog to the append method for Lists in Python. The following would add the value in x to the end of the ArrayList.
```
arr0.add( x );
```
Standard for loops in Java are different from Python but similar to C/C++. A for loop definition has three parts: initialization, loop condition, and loop action. The initialization step occurs only the first time the loop executes, the loop will continue to execute while the loop condition is true, and the loop action will occur after each loop iteration. The following example shows a loop definition that will execute the contents of the loop block ten times.
```
for(i=0;i<10;i++) {
/* loop block code here */
}
```
You will need to either declare the variable i as an int prior to the loop, or you can declare the loop variable in the initialization step of the for loop itself.
```
for(int i=0;i<10;i++) {
/* loop block code here */
}
```
To create random numbers, you need to use a Random object, which must be declared and allocated.
```
Random ran = new Random();
```
See the documentation for the list of functions the Random object supports. One of those methods is nextInt, which returns a pseudorandom integer. You can specify an upper bound (exclusive) by passing in an integer value. For example, the following returns an integer between 0 and 49.
```
int val = ran.nextInt(50);
```
Print the Values in the ArrayList
Loop through your ArrayList again, get each value in turn and print it out using System.out.println(). (Note: you must use an indexed for loop! There is a way to iterate over ArrayList elements in Java, but our simple ArrayList implementation doesn't support it.)
Remove the Values in Random Order
Loop 10 times and randomly remove one element from the original ArrayList each time, printing out the value that was removed and the remaining values in the list (all on one line). You can use System.out.print() to send something to the command line without a newline. Note that you'll have to select a random number that is always strictly less than the number of elements left in the list.

+ (More Detail)

Use the nextInt method of your Random object to generate random indices. You can use the ArrayList method size to get the number of elements in an ArrayList, which is the upper bound for legal indices.
Strategize about how to implement Shuffle
How can you programatically create a random permutation of a set of elements? In other words, given an ArrayList with elements in order, develop a method of creating an ArrayList with those elements in a randomized order. Here's a hint: take a look at the printed output from the last step. Does that look shuffled? If you want another hint, toggle open the box below.

+ (More Detail)

If you start with a set of numbers in order, you already figured out how to remove the values in a random order. What if you put the values withdrawn from the ArrayList into a new ArrayList?

(Advanced Optional Topic:) If you're looking for a 'cleaner' way to shuffle, check out the Fisher-Yates algorithm.

Note: there's nothing to show for this exercise. Refer back to it to help you write your shuffle code in your Deck class later on.
Lab Check-In
Log into Moodle and complete the quiz titled: "LAB - Lab Check-In 1 -- ArrayList". This closes at 4 pm. Your score on this quiz will count as your lab check-in for this week.

When you are done with this exercise, you can get started on the project.