CS 211 Lab 7: Finally, ArrayList! Last Updated: 2017-03-07 Tue 19:33 CS 211 Lab 7: Finally, ArrayList! Due: 11:59pm Friday 3/24/2015 Approximately 1% of total grade Submit to code to Blackboard Lab Exercises are open resource/open collaboration Sections marked (TESTED) involve functionality that is tested by the automatic test cases. CODE DISTRIBUTION: distrib-lab07.zip CHANGELOG: Empty Table of Contents 1. Due Date and Midterm Feedback 2. Rationale 3. ALUtils Class 4. Reversal (TESTED) 5. Rotations (TESTED) 1 Due Date and Midterm Feedback The due date for this exercise lab is after spring break. This should give you sufficient time to work on it during or after break. The concepts introduced, use of ArrayList, will be employed in the next project so is important to master to meet with success on the project. In addition to the lab exercises, there will be a midterm feedback survey posted to Blackboard which must be completed to get credit for the lab. Look for a Piazza announcement for this and a link on Blackboard. You must complete the survey in order to receive credit for the lab though your responses will be anonymous: only the fact that you have done the survey will be recorded. 2 Rationale Java's standard arrays are a low-level mechanism to provide contiguous blocks of memory which enables good execution performance. Their tradeoff is that standard arrays are not flexible: the provide a fixed length only and cannot expand. The ArrayList class is the most commonly used alternative. It is an essential tool any self-respecting Java programmer and we will spend some time discussing its implementation in lecture later in the class. The central convenience ArrayLists provide is an add(x) method which allows expansion of the ArrayList to include new elements. A typical usage is to create an empty ArrayList a and repeatedly a.add(x) elements to it to populate the array. ArrayList is a generic class implemented with type parameter so that it can be contain any reference type in Java. ArrayLists are the first class we will encounter which employ generics: many kinds of ArrayList can be created and the kind is indicated in angle brackets: ArrayList as = new ArrayList() A variable as which points to an array list of strings. It is immediately allocated space. ArrayList ai; An array list ai which has not yet been allocated space. Generics provide a powerful mechanism to write flexible code and will be discussed in more detail later in the class. This lab will give you some experience working with ArrayLists as a an alternative to standard arrays. You will need to access and alter elements using methods rather than the standard array square brace syntax. This will also illustrate the general pattern of how to work with generic classes. You will write two static methods to perform operations on ArrayLists of any type which will also illustrate how to write methods which are generic/type independent. Associated Reading Building Java Programs Chapter 10.1 introduces the ArrayList class and covers its essential operations such as appending, getting, setting, and searching. CS 211 Lab Manual Chapter 14 covers generics and briefly discusses ArrayList. This chapter discusses how to define your own generic classes but does not cover too many details of ArrayList. It will assist in understanding how to work with the Pair class which is provided and what the strange looking method signature of mode means. 3 ALUtils Class Fill in the definitions to two ArrayList utility methods in the ALUtils class which is outlined below and included in the code pack for this lab. The methods are described in more detail below. import java.util.*;
public class ALUtils{
// Creates a copy of the parameter a. Reverses the order of elements
// in the copy and returns the reversed copy. Assumes a is non-null.
public static ArrayList reverse(ArrayList a){
// YOUR DEFINITION HERE
}
// Creates a copy of the given ArrayList a and rotates the copy to
// the right by the given shift. Elements at high indicies wrap
// around to lower indices. Assumes parameter a is non-null and
// that shift is a non-negative number. Returns the rotated copy.
public static ArrayList rotate(ArrayList a, int shift){
// YOUR DEFINITION HERE
}
}
4 Reversal (TESTED) In ALUtils, write a method reverse(aL) that takes an ArrayList and creates a reversed copy of it which is returned. The nature of this method is shown in the below demo and should produce the results indicated. You may assume that the parameter aL is non-null. While there are some library methods that exactly implement this functionality, take this as an opportunity to write your own loop to reverse the array list. public static void demo_reverse(){
System.out.println("TESTING REVERSE");
ArrayList sa = new ArrayList();
String [] strings = {"A","B","C","D","E"};
// Use the a for-each to add all strings
for(String s : strings){ sa.add(s); }
// sa == [A, B, C, D, E]
ArrayList sb = ALUtils.reverse(sa);
System.out.println(sb);
// [E, D, C, B, A]
System.out.println(sa);
// [A, B, C, D, E] - sa is not changed
ArrayList ia = new ArrayList();
String [] ints = {"10", "9", "8", "7", "6", "5", "4", "3", "2", "1"};
// Use the addAll() method add all ints from a list
ia.addAll(Arrays.asList(ints));
// ia == [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
ArrayList ib = ALUtils.reverse(ia);
System.out.println(ib);
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
System.out.println(ia);
// [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] - sa not changed
}
5 Rotations (TESTED) In ALUtils.java write a static method rotate(aL, shift) which accepts an ArrayList and creates a rotated copy of it. Rotation means to shift all elements forward in the list to a new position based on the integer parameter shift. If the elements would shift off the end of the list, they wrap around to the beginning. The concept should be familiar based on projects and is best illustrated by examples given below. aL = [ A, B, C, D, E, F] bL = [ A, B, C, D, E, F, G]
cL = rotate(aL, 2) cL = rotate(bL, 7)
cL== [ E, F, A, B, C, D] cL== [ A, B, C, D, E, F, G]
cL = rotate(aL, 7) cL = rotate(bL, 4)
cL== [ F, A, B, C, D, E] cL== [ D, E, F, G, A, B, C]
The rotate(aL,shift) method should take the following approach. Accepts an ArrayList called aL of any type and an integer shift. You may assume shift is a non-negative integer and aL is not null. Creates a new ArrayList and populates its contents with elements of aL shifted in position by shift. This new ArrayList is returned. If aL is empty, the return value is an empty ArrayList. You may assume that the shift parameter is non-negative (zero or larger) and that aL is non-null. Some additional demonstrations of the expected behavior are below. // Demonstrate rotat(a,shift) method
public static void demo_rotate(){
ArrayList intsL;
intsL = new ArrayList();
int [] ints = { 10, 20, 30, 40, 50, 60};
for(Integer i : ints){
intsL.add(i);
}
// intsL = [10, 20, 30, 40, 50, 60]
ArrayList result1;
result1 = ALUtils.rotate(intsL, 2);
// result1== [ 50, 60, 10, 20, 30, 40]
System.out.println(result1);
result1 = ALUtils.rotate(intsL, 7);
// result1== [ 60, 10, 20, 30, 40, 50]
System.out.println(result1);
}
Author: Mark Snyder, Chris Kauffman (msnyde14@gmu.edu, kauffman@cs.gmu.edu) Date: 2017-03-07 Tue 19:33
