In this module, we have seen how an ArrayList works by performing operations using an underlying array. In this assignment, you will modify the implementation of an ArrayList so that it uses Java Generics and has additional functionality.

Learning Objectives

In completing this assignment, you will:

●  Understand the implementation of an ArrayList in Java

●  Gain familiarity with reading and modifying existing code

●  Be sure that you can submit code to the course’s autograding platform

Setup

Download the MyArrayList.java file, which contains the unimplemented methods for the code that you will write in this assignment.  Be sure that you are able to compile this code, and review the implementation before proceeding.

As you work on this assignment, please do not change the signatures of any of the methods (their parameter lists, names, and return value types) except where required to convert to generics, and do not create any additional  .java files for your solution.  Additionally, please be sure that your MyArrayList class is in the default package, i.e. there is no “package” declaration at the top of the source code.

Development Environment

For this and all other assignments in this course, we recommend that you work on your local com- puter using a development environment such as Eclipse, IntelliJ, Visual Studio Code, or whichever IDE you used for any prior Java courses.

Although you will need to upload your solution to Codio for grading (see “How to Submit” below) and could develop your solution on that platform, we recommend using industry standard tools such as Eclipse or IntelliJ so that you become more used to them and can take advantage of their features.

If you have trouble setting up your IDE or cannot get the starter code to compile, please post a note in the discussion forum and a member of the instruction staff will try to help you get started.

The Codio environment uses Java 11. You may use JDK version 11 or greater on your machine, as long as you set the Java language level to 11.

Activity

In this assignment, you will modify the MyArrayList class to give it some extra functionality.

Step 1.  Use Java Generics

Modify the MyArrayList class so that it uses Java Generics instead of Strings.  That is, it should be possible to create an instance of the class like this:

MyArrayList<I n t e g e r >  l i s t  = new  MyArrayList <>();

You will need to make changes throughout the class definition. Make sure that all methods accept or return objects of the parameterized type, and not just Strings.

This step is a bit tricky, so here is some recommended reading:

● Generics: How They Work and Why They Are Important

● Generics: The Fine Print

We don’t expect you to suddenly become an expert on all of Java’s quirks.   For now you just need to know what a generic type is, how it’s used in terms of concrete syntax, and the restriction (particular to Java) that the type of arrays is erased at runtime, so you cannot have arrays of a generic or parameterized type.

Specifically, note that the underlying array should not be of type E[], and you should NOT write: this . data  =  (E [ ] )   new  Object [ INITIAL_CAPACITY ] ;

We know the above line is what was recommended in the textbook and lectures, but this  is a mistake, even if it seems to work in this case.  In real code, trying to cast Object[] to E[] leads to ClassCastExceptions under many circumstances and is considered bad practice.

Instead, declare your underlying array (data) to be of type Object[]. There are some implications of this:

● When you have a method that takes an element of variable type E and modifies your underlying array, you can safely store it in the array since Object is the parent class of all other classes.

● When you have a method that returns an element of type E out of the underlying array, you will be typecasting the element from Object to E, e.g. return  (E)  obj;.

● Your IDE may warn you about unsafe casts, and it will likely offer to insert an annotation (@SuppressWarnings("unchecked")) to ignore unsafe casts. You need to manually check that all of your casting is safe before inserting this annotation. Such annotations must be used very carefully and wisely as they can destroy the type safety of your program if used incorrectly! Note however that this is actually one of the good uses for SuppressWarnings.

Step 2. Implement remove method

Implement the remove method so that it takes an object of the parameterized type (from Step 1) as its parameter, and removes the first instance of an equivalent element in the underlying array, i.e. for which the  .equals method returns true.

Once the object has been removed, the elements following it should be shifted over to fill the empty space, and the method should return true; if the object does not exist in the underlying array, the method should simply return false.

For instance, assume the underlying array contained these values in this order:

If the method remove("Banana") were called, then the array should look like this:

And the method should return true.

Step 3.  Shrink array when it is too large

Modify the two remove methods (the one we provided and the one from Step 2) so that they shrink the length of the underlying array when, after removing an element, the number of elements in the array is less than or equal to 25% of the array’s length.  In this case, the underlying array should be shrunk to half its current length.

For instance, assume the underlying array contains these values in this order:

And assume that “Bat” was removed, either by its index or its value.  Then the array should look like this:

Because the number of elements (2) is now less than or equal to 25% of the length of the array (8), the array should be cut in half, and should then look like this:

That is, the elements should stay the same, but the underlying array should now have a length of 4 instead of 8.

Hint: Review the code that is used to grow the underlying array and think about how you can write similar code to shrink it.

Step 4. Implement set(index,  value) method

Implement the set method so that it takes an integer index and a value of the parameterized type (from Step 1) as its parameters and replaces the element in the underlying array at that index with

the new value. The method should then return the old value, i.e. the one that was replaced. For instance, assume the underlying array contained these values in this order:

If the method set(1,  "Monkey") were called, then the array should look like this:

And the method should return “Dog” since that is what was replaced.

If the index is out of range, then the method should throw an IndexOutOfBoundsException.

Step 5.  Create constructor to initialize underlying array

Create a constructor for this class that takes an array of the parameterized type (from Step 1) as its parameter and initializes the values in MyArrayList’s underlying array.

If the argument to the constructor is null, or if it is a non-null array of length 0, then the MyArrayList constructor should behave exactly the same as the default (no-argument) constructor does.

Otherwise,  MyArrayList’s size field must then be equal to the length of the input array.   The length, however, of MyArrayList’s underlying array must be max(arr .length, INITIAL_CAPACITY).

Initializing the MyArrayList elements sounds relatively straightforward, but note that it should be possible for the caller of this constructor to modify the elements of the input array argument without changing what’s in the MyArrayList and vice-versa.

For instance, consider the following code:

S t r i n g [ ]   data  =  {" cat " ,   "dog" ,   " elephant " } ;                  MyArrayList<String >  l i s t  = new  MyArrayList<>(data ) ;

If the caller then invokes

data [ 1 ]  =  " bat " ;

this should not change what’s in list.

Likewise, if the caller invokes

l i s t . s e t ( 0 ,   "mouse" ) ;

this should not change what’s in data.

Before You Submit

Please be sure that:

● your MyArrayList class is in the default package, i.e. there is no “package” declaration at the top of the source code

● your MyArrayList class compiles and you have not changed the signature of the methods we have provided, except to convert to generics

● you have not created any additional  .java files

● You have filled out the required academic integrity signature in the comment block at the top of your submission file

How to Submit

After you have finished implementing the MyArrayList class, go to the “Module 1 Programming Assignment Submission” item and click the “Open Tool” button to go to the Codio platform.

Once you are logged into Codio, read the submission instructions in the README file. Be sure you upload your code to the “submit” folder.

To test your code before submitting, click the “Run Test Cases” button in the Codio toolbar; this will run the tests that are used to grade your code.

You’ll see quite a bit of output, even if all tests pass, but at the bottom of the output you will see the number of successful test cases and the number of failed test cases.

You can see the name and error messages of any failing test cases by scrolling up a little to the “Failures” section.

If all tests are successful, then you would earn 100% on this assignment; there are no “hidden tests.” Note, though, that this will not be the case in subsequent assignments, which will have “hidden tests.”

Assessment

This assignment is scored out of a total of 45 points.

Step 1 is worth a total of 10 points, based on whether your implementation correctly implements generics using the guidance given above.

Step 2 is worth a total of 12 points, based on whether your implementation correctly removes the element, updates the size, and moves other elements as a result.

Step 3 is worth a total of 6 points, based on whether your implementation correctly modifies the size of the underlying array.

Step 4 is worth a total of 7 points, based on whether your implementation correctly sets the element and handles error cases.

Step 5 is worth a total of 10 points, based on whether your implementation correctly initializes the underlying array and handles error cases.

Optional Challenges

These are ungraded optional challenges you can do if you want to dive deeper.

Implement indexOf

This method takes an object and returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.

If you are certain your implementation is correct, see if any of the class’s methods can be simplified by using it.

Minimize use of @SuppressWarnings

Take a look at your code. In how many places are you using @SuppressWarnings("unchecked") to suppress the unsafe cast warning? It turns out, you can reduce this down to just one single place.

Try to figure out how to do this.

Implement toArray(T[])

This method returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.  The length of the returned array should be equal to the siXe of your array list, not its underlying array length.

The complete method signature is:

<T> T [ ]   toArray (T [ ]   a )

This challenge will require an intermediate to advanced understanding of the language.  It is not for  Java beginners,  unless you’re willing to spend some time going down a rabbit hole!   As a hint, if you have defined MyArrayList<Integer>  ints, then you could call this method like so: ints .toArray(Integer[]::new) .

Implement circular dynamic arrays

Warning:  do not attempt to submit this challenge as, being a significant variant on the assigned data structure, it would be marked incorrect!

In this assignment you have implemented a dynamic array, also known as an array list or a vector. This data structure is very good for use cases where you often add to the end of the list, but rarely to the beginning or middle.

It is also possible to write a “circular” dynamic array in which the end of the array wraps around to the front under some circumstances. This would be useful if you wanted a list that is reasonably fast both at adding to the front of the list and at adding to the back of the list.  (Thus it would be a candidate implementation of a double-ended queue, an abstract datatype you will learn about in a later module.)

For a graphical visualization and hint at how to do this, see page 242 of the textbook.

Note that this would be a complete re-write just for your own practice that you absolutely should NOT submit, but you would still want your array list to expose the same basic interface as given in the starter code for this assignment.

Frequently Asked Questions

Are nulls valid values in a MyArrayList?

First, it’s perfectly valid to add the value null to a list of objects. This is because in Java all objects are “nullable”, meaning any object can either be null (un-instantiated) or non-null (instantiated).

In other words:

I n t e g e r  x  =  null ;

x  =  5 ;

is valid because Integer is an object type, thus both null and 5 typecheck as Integers. However if we used int, the first line would not be valid because an int is not an object, but a primitive value.

Second, suppose the underlying array is:

[  "Ant", null, null, null, null, null,  "Cow", null  ]

Assuming “Ant” and “Cow” are intended elements, the logical list must either be  ["Ant", null, null, null, null, null,  "Cow"] or  ["Ant", null, null, null, null, null,  "Cow", null] depending on whether size is 7 or 8.

The only thing that distinguishes size from an empty cell is whether it is before or after the end of the list, as determined by the size of the MyArrayList.

I’m confused about the difference between size and length.

The length refers to the physical space on the machine taken up by an array.  The size refers to the number of elements in the abstract “array list” that is exposed to the user.  Thus the size will always be less than or equal to the length, because it’s impossible for there to be more elements in an array list than physical space in the underlying array.

How to implement generics without modifying method signatures?

This is the only assignment where you are asked to modify method signatures. Your modifications to method signatures should be the absolute minimum required to implement generics correctly, per our guidance above. So, definitely don’t rename methods, or change the number of parameters they take.