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; how to write a good test; and how to start thinking about implementing the shuffle method for the project.

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.

Tasks

  1. 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.

  2. Write a 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
    */	
  3. 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.

  4. 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.

  5. 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);
  6. 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);
  7. 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.

  8. 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))
    .

  9. Write a Test for a Shuffle Method

    In the project, you will be writing a shuffle method for your Deck class. In this step of the lab, you will write a first version of a test for the shuffle method based on what you just learned about testing for equality.

    To start this, you should download the file ShuffleTests.java and fill in the skeleton, then download the file DumbShuffle.java and run your test on its methods. Your test should pass for the dumbShuffle method, and fail for the noShuffle method. This is what you should show us for the lab checkpoint!

    Steps: Your test should create an ArrayList of Integers, then insert the numbers 0 to 9 into it in order. It should then call the dumbShuffle method in DumbShuffle.java on your list of numbers, and save its output as a new array list. All of that's your setup! For the verify step, consider printing the contents of the original array and the new, shuffled array with some annotation. For the test itself, your test should use an assertion to check whether the original array list and the new array list have the same values in the same order. Make sure to use the right version of testing for equality!

    A note on assertions: Use the -ea flag when running your program to tell Java to enable assertions! For example: java -ea ShuffleTests

    Run your test and verify that the dumbShuffle method passes it. Then run the same test on the noShuffle method in DumbShuffle.java. (You can do this by commenting out the call to dumbShuffle and commenting in a call to noShuffle, or any other way you choose.) Verify that the noShuffle method does not pass your test.

    Checkpoint: Ok, call us over and show us these 2 things (dumbShuffle passes your test, noShuffle doesn't) and we'll give you credit for the lab!

  10. Reflect on Your Test

    Take a look at what the dumbShuffle method does. Do you think dumbShuffle should pass your test for the shuffle method? For now just think about it (there's nothing for you to show). You'll get a chance to improve on your tests for the shuffle method in reflection question 1!

  11. Remove the Values in Random Order

    This exercise provides scaffolding for writing the Shuffle method. Work through this exercise and refer back to it when you go to write your own shuffle method!

    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.

  12. 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. Come up with a design--you'll implement it in the shuffle method of the Deck class in your project. (There's nothing to show here, this is a warm-up for writing that code).

    Here's a hint: take a look at the printed output from the last step. Does that look shuffled?

    + (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.

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