CS231

Java and ArrayLists

The goal of this lab period is to get you started on the current assignment. In particular, we'll look at how to import and use the ArrayList class, one of the abstract data types provided by the standard library.

An ArrayList is a flexible array type similar to a Python list. An element of an ArrayList can be accessed by using the get or set method with an index, and you can modify, append, insert, or remove elements of the array. You can see all the details of ArrayLists in the Java ArrayList documentation. Additionally, we'll be using Java's Random class, for which the documentation can be found here.

The main task for the lab is to develop an algorithm that shuffles the elements of an array to put them into a random order.

Tasks

Project Setup
Create a working directory for today's lab. Then start a Java file called Shuffle.java.

-
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. For this class, since you'll be submitting your work on Google Drive anyway, I recommend using it for backup. You can download a desktop-app for it from here. If you really want to be cool, you can look into creating repositories for your work on Github, Gitlab, etc. Another alternative we'll give instructions for below is the use of Colby's own Filer system, which is easiest to use if you live on Campus. The instructions for saving work on Filer are below.
- Mount your network drive on Personal. In the Finder, use the Go::Connect To Server menu option to mount smb://filer.colby.edu the Personal volume.
- Navigate to your folder on the Personal volume and create a folder for the current project.
- Using an editor of your choice, e.g. Notepad++ or VSCode, create a new Java file and save it in your new working directory.
- Open the Terminal, then cd to your working directory. You can use the Finder shortcut of first typing cd and a space in the terminal and then dragging and dropping your working directory folder into the Terminal window to get the path.
File Header
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
*/	
```
-

The above is an example of a block comment, a capability not available in Python. A block comment starts with /** and ends with */.
Import Packages
Import the ArrayList and Random classes into your file using the following syntax.
```
import java.util.ArrayList;
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.
Create a Shuffle Class
Create a class 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:
```
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 and the ArrayList 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<E>, where E is a type variable. You will be making an ArrayList that should contain Integers, so you should specify Integer in place of E. 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 declearation, 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().

+ (More Detail)
As specified in the documentation for an ArrayList, to get a value from position i in an ArrayList you need to use the get method. The get method takes the index as the argument and returns the value at that position in the ArrayList. It will throw an error if the index is out of bounds. Like Python, Java is 0-indexed, so index 0 is the first position in the list. The following gets the ith value from the ArrayList arr and assigns it to an Integer variable x.
```
Integer x = arr0.get(i);
```
Create a second ArrayList with the same items in the same order as the first
Declare and initialize a second ArrayList object named arr1 and add in the same items from the first list in the same order, so that both lists contain precisely the same numbers in precisely the same order. Create a third variable (arr2) and set it to literally be the first (ArrayList<Integer> arr2 = arr0). Confirm that the lists stored in each variable all seem equal by printing the three variables.
Comparing two Objects in Java
After this, compare the three variables using the == operator (so you might write something like:
```
System.out.println("arr0 == arr1: " + (arr0 == arr1) + "\narr1 == arr2: " + (arr1 == arr2) + "\narr2 == arr0: " + (arr2 == arr0))
```
The result printed might differ from your expectations; these two lists look identical, why shouldn't they be ==?

This discrepancy comes from how Java chooses to interpret the == operator. With the == operator, Java tests to see if the objects are stored in the same memory location. When we created the third variable to store the list stored in the first, we ensured that both variables pointed to the same list in memory. By creating a second entirely new list, no matter the contents it will always sit in a different location in memory from the original list.

Since we still want a method to determine if two objects are equal in a 'contents' sense, this can be done by using the equals method. Test this out by writing
```
System.out.println("arr0.equals(arr1): " + (arr0.equals(arr1)) + "\narr1.equals(arr2): " + (arr1.equals(arr2)) + "\narr2.equals(arr0): " + (arr2.equals(arr0))
```
.
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.
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. Come up with a design and implement it. In this week's assignment, shuffling a deck of playing cards involves creating a random permutation of the set of cards in the deck, so this is basically the warm-up for that.

+ (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.
Submit Lab
Most labs this semester you won't turn in. If you would like to do a test submission, you can follow these steps to turn in your code from today. If you do so, come show me when you are done I can confirm for you whether everything looks good.

+ Create a report and export to pdf
- Create a report in your favorite text editor. For this lab, include a document with your name in it.
- Print to PDF (Windows)
  - Open a file in a Windows application.
  - Choose "File > Print".
  - Choose "Adobe PDF" as the printer in the Print dialog box.
  - Click Print. Type a name for your file, and click Save.
- Print to PDF (Mac OS)
  - Open a file in a Mac OS application.
  - Click the "PDF" button and choose "Save As Adobe PDF".
  - Choose the "Adobe PDF Settings" and click "Continue".
  - Type a name for your file, and click "Save".
- Export to PDF Google Drive
  - Choose "File" > "Download" > "PDF Document (.pdf)"
+ Prepare your project folder
- In Finder, move your lab folder inside your project folder. For example, if you have Lab01 and project_01 folders both on your Desktop, drag the Lab01 folder inside project_01.
+ Submit your project on Google Drive
- On Google Drive, locate the folder named with your Colby username that was shared with you earlier.
- Upload the relevant files into the matching project folder. you can ‘drag and drop’ the files into the project folder on Drive. (".class" files are not relevant)

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