Problem Solving Assignment 3

Part A Due: Thursday of week 5 (4/30/2009) at 11:59pm

Part B Due: Thursday of week 6 (5/7/2009) at 11:59pm

Point total: 25 points

We have seen how ArrayLists are a convenient class for storing data, which remove many of the hassles that come with using arrays. In order to better appreciate that convenience, we will see exactly how much work goes into the implementation of an ArrayList, by making one ourselves! This will illustrate the benefit of Abstract Data Types (ADTs), which are classes that provide a useful service, while hiding the nitty-gritty details under the surface. You interact with an ADT through a set of well-defined methods, and more importantly you do not need to know how it is implemented in order to use the class. As an example, think of your DVD player. You don't know exactly how your DVD player works inside, but you still know how to use it because it has a simple interface - the buttons - and you know abstractly what effect each of them should have on the state of the DVD player. This is a common pattern in programming, and we will design our first ADT in this assignment.

This homework requires skills with arrays and dividing work among subroutines. You will need to write the following classes:

1. SmartArray -- This class will be your own implementation of a data structure much like an ArrayList. It will have most of the same methods as ArrayList, and behave in much the same way.
2. SensorReader, DataProcessor -- For Part B of this assignment, you will be rewriting the previous assignment in terms of the SmartArray, rather than ArrayList. YOU WILL USE THE SAMPLE SOLUTION FOR PSA2 PROVIDED BELOW, NOT YOUR OWN VERSION.

Details

You must put a comment at the top of your code that specifies your: real name, login name, email address, and PID. You must also include a two-to-four sentence description of the program. Use a multi-line comment (/* */). YOU MUST DO THIS FOR EVERY JAVA FILE!

Comments Comments in the style detailed in the book ARE required. Your code must be properly commented to receive full credit.

SmartArray

This class is the bulk of the assignment, and will contain several methods. Since this is a two-part assignment, we explicitly divide this class into two parts. Throughout this assignment, there are many opportunities for reusing code by having one method of SmartArray call another. For each method that could benefit by calling another method, we have put this picture () next to it as a hint.

Part A - Complete in Week 5

1. Object[] array - This field will hold the data inside the SmartArray. By definition, the capacity of your SmartArray should be array.length
2. int size - This field will hold the current number of objects that are in the SmartArray. Note that this is not the same as the capacity. (#1+#2 = 1/2pt)
3. SmartArray() (constructor) - The default constructor should take no parameters, and should initialize the SmartArray to have a capacity of 10 and a size of 0. (1/2pt)
4. SmartArray(int capacity) (constructor) - This constructor will take the capacity as a parameter. If the capacity is negative, then the constructor should throw an IllegalArgumentException with the message "Capacity cannot be negative". If the capacity is not negative, then this constructor should initialize the SmartArray to have a capacity equal to the input parameter, and a size of 0. (1pt)
5. SmartArray(SmartArray other) (constructor) - This constructor is designed to copy the given SmartArray. At the end of this constructor, this SmartArray should contain the same elements as the input SmartArray, in the same order, and have the same size. The input SmartArray should not be changed. (2pt)
6. checkInBounds(int index) - This method is a helper method to check whether a given index is valid. An index is valid if it is greater than or equal to 0, and less than the size of the SmartArray. All that this method does is check to see if the input parameter is a valid index, and if not it will throw an IndexOutOfBoundsException with the message ("Invalid index: " + theInvalidIndex). There is no return value.
   This method is highlighted in blue because it should be declared private. All the other methods should be public. (1pt)
7. ensureCapacity(int capacity) - This method attempts to increase the capacity of the SmartArray to hold at least the amount of the input parameter. If the input parameter is not larger than the current capacity, nothing should happen. If the input parameter is larger than the current capacity, then this method will need to increase the current capacity by creating a new Object[] array and copying the old array into the new one. The value that you pick for the new larger capacity should be the smallest power of 2 that is at least as big as the input parameter. For example:
   

   Input value	New capacity
   10	16
   20	32
   8	8

   You can compute this power of 2 with a loop, by starting with 1 and going to the next power of 2, so long as you haven't exceeded the input value.
   (NOTE: even though this method requires you use a power of 2, the constructors do NOT. When the constructors choose a capacity, they can pick any value that is large enough.)
   Once you are done with the copying, you can simply reassign the array field to hold the new array. This method should have no effect on the size of the SmartArray, nor its contents. This method has no return value. (2pt)
8. get(int index) - This method fetches the item that lives at the given index in the SmartArray and returns it. Before returning the item, you must check to make sure that the given index is valid. If it is not valid, you should throw an IndexOutOfBoundsException with the message ("Invalid index: " + theInvalidIndex). (1pt)
9. set(int index, Object obj) - This method will reset the element at index to be equal to obj. If index is valid, then the element at that index should be reset to equal obj. If index is not valid, then this method should throw an IndexOutOfBoundsException with the message ("Invalid index: " + theInvalidIndex). This method should NOT change the size of the SmartArray. This method has no return value. (1pt)
10. add(Object obj) - This method adds the obj to the end of the SmartArray. This will involve increasing the size of the SmartArray by 1. Once you have ensured that the SmartArray has sufficient capacity for another new element, you can simply put the new element in the correct location in the array, and increase the size. This method has no return value. (1pt)
11. size() - This method returns the current size of the SmartArray. (1/2pt)

Part B - Complete in Week 6

1. add(int index, Object obj) - This method will insert a new element into this SmartArray at the given index. If the index is valid, then each element whose location is greater than or equal to index will get shifted up by 1. Then the new object will get stored at index. If the index is not valid, then this method should throw an IndexOutOfBoundsException with the message ("Invalid index: " + theInvalidIndex). If there is no exception, this method should increase the size of the SmartArray by 1. This method has no return value.
   (NOTE: since this method can only take indexes in the range 0 through (size-1), this method cannot be used to add an element to the end of the SmartArray. So for example, this method cannot be used on an empty SmartArray without causing an exception.) (2pt)
2. clear() - This method resets the SmartArray so that it contains no elements. After this method call, the SmartArray should have a size of 0, but retain the same capacity as before. This method has no return value. (1/2pt)
3. addAll(SmartArray other) - This method will add all of the elements from the other SmartArray to this SmartArray. The elements from other should be added to the end of this SmartArray, in the same order they appeared in other. The end result of this method is that this SmartArray should increase its size by other.size(), and other should be left completely unchanged. This method has no return value.
   (NOTE: for performance reasons, this method should NOT be written by making repeated calls to add. If you write it this way, you will lose points!) (2pt)
4. remove(int index) - This method will remove the object at the given index from the SmartArray. If the index is valid, then the value at that index should be removed and all the values at higher indexes should be shifted down by 1. This will cause the size of the SmartArray to decrease by 1. If the index is not valid, then this method should throw an IndexOutOfBoundsException with the message ("Invalid index: " + theInvalidIndex). This method should return the Object that was removed. Here is an example:
   

   SmartArray before calling remove:	0 1 2 3 "My" "name" "is" "Mike"
   SmartArray after calling remove(2):	0 1 2 "My" "name" "Mike"

   Returns "is"

   (1pt)
5. remove(Object obj) - This method is similar to the other remove method, but it instead searches the SmartArray for the given object and if it is found, it is removed. This method compares obj against each element of the SmartArray using the .equals method. If it finds obj, then it will remove it and shift all the objects at higher indexes down by 1. If obj is in the SmartArray in multiple locations, then only the lowest-index one is removed. If anything is removed, then this method will return true. If nothing is removed, this method will return false. (1pt)
6. indexOf(Object obj) - This method will search for the given object and return the lowest index at which it lives in the SmartArray. The searching will compare obj against the elements in the SmartArray using the .equals method. If the object cannot be found in the list, this method should return -1. (1pt)
7. lastIndexOf(Object obj) - This method will search for the given object and return the highest index at which it lives in the SmartArray. This method behaves just like indexOf, unless the object lives in the SmartArray in multiple places. If so, then this method will return the largest index at which the object lives, whereas indexOf would return the smallest. Again, if the object is not found then this method should return -1. (1pt)
8. contains(Object obj) - This method will search for the given object and return true if it lives anywhere inside this SmartArray. The search will compare obj against the elements in the SmartArray by using the .equals method. If the object is not found in the SmartArray, then this method should return false. (1/2pt)
9. containsAll(SmartArray other) - This method will check to see if ALL of the elements of the given SmartArray are contained inside this SmartArray. If there are any elements in the given SmartArray that are not contained inside this SmartArray, then this method should return false. Otherwise, this method should return true. (1pt)
10. isEmpty() - This method should return true if this SmartArray is empty, and return false otherwise. (1/2pt)
11. EXTRA CREDIT: subList(int startIndex, int endIndex) - This method will return a sublist of this SmartArray, which consists of all the elements from startIndex up to but not including endIndex. Before making the sublist, you must make sure that the input indexes are valid. The indexes are considered valid if all three of the following are true:
    1. 0 <= startIndex
    2. startIndex <= endIndex
    3. endIndex <= size
    (NOTE: you should NOT call checkInBounds to check these conditions)
    If the indexes are not valid, this method should throw an IllegalArgumentException with the message ("Invalid indexes: " + startIndex + " and " + endIndex). If the indexes are valid, then this method will create a new SmartArray and copy the specified range of indexes into it from this SmartArray. Then the new SmartArray is returned. Here is an example:
    

    Original SmartArray:	0 1 2 3 "My" "name" "is" "Mike"
    Result of calling subList(1,3):	0 1 "name" "is"

    (2pt EXTRA CREDIT)

Here are the sample solutions for SensorReader.java and DataProcessor.java and SensorData.java. (2pt)
(NOTE: you will not need to edit or turnin SensorData because it did not use ArrayLists)

Testing/Grading

We have testing programs for both Part A and Part B of this assignment. You can run these testing programs by typing the following commands on ieng6:

testPSA3A SmartArray.class
or
testPSA3B SmartArray.class

NOTE: The tester for part B will test the extra credit method (subList), so if you chose not to do the extra credit then your code will always fail that particular test.

Turning in your homework

Since there are 2 parts to this assignment, there will be 2 separate turnins with two separate bundle scripts.

On ieng6 somewhere under your home directory you need to make a folder called PSA3. All of your files for this assignment must go in this folder.

Part A - Due Thursday Week 5, April 30

• SmartArray.java - your implementation of the SmartArray class.

Part B - Due Thursday Week 6, May 7

• SmartArray.java - your implementation of the SmartArray class.
• SensorReader.java - your rewrite of the sample SensorReader class, which uses SmartArrays instead of ArrayLists.
• DataProcessor.java - your rewrite of the sample DataProcessor class, which uses SmartArrays instead of ArrayLists.