Problem Solving Assignment 3
Part 1 Due: Thursday of week 5 (2/5/2009) at 11:59pm
Part 2 Due: Thursday of week 6 (2/12/2009) at 11:59pm
Point total: 25 points
NOTE (2/6/2009): The tester for part 2 of the
project is now up and working! Go ahead and try it out! One thing to
be aware of is that it will test the extra credit method (subList), so
if you chose not to do the extra credit then you will always fail that
particular test. The description of the testers is here.
NOTE (2/8/2009): The sample solution code for SensorData.java is now
provided along with SensorReader.java and DataProcessor.java. This is
only provided as a convenience, and you DO NOT need to turn in an
edited copy of SensorData.java for part 2 of this assignment.
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:
- 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.
- SensorReader, DataProcessor -- For Part 2 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.
Comments and good style are worth (2pt).
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 1 - Complete in Week 5
- Object[] array - This field will hold the data
inside the SmartArray. By definition, the capacity of
your SmartArray should be array.length
- 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)
- 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)
- 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)
- 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)
- 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)
- 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)
-
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)
-
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)
-
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)
- size() - This method returns the current size of
the SmartArray.
(1/2pt)
Part 2 - Complete in Week 6
-
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)
- 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)
-
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)
-
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):
|
|
Returns "is"
(1pt)
-
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)
- 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)
- 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)
-
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)
-
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)
- isEmpty() - This method should return true if this
SmartArray is empty, and return false otherwise.
(1/2pt)
-
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:
- 0 <= startIndex
- startIndex <= endIndex
- 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):
|
|
(2pt EXTRA CREDIT)
In addition to the above methods, in Part 2 of this assignment you
will also be required to rewrite PSA2 to use
SmartArrays instead of ArrayLists. YOU WILL DO
YOUR EDITS ON THE SAMPLE SOLUTION FOR PSA2, NOT YOUR OWN. 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 will have a testing program for both Part 1 and Part 2 of this assignment.
You can run these testing program by typing the following commands on ieng6:
testPSA3part1 SmartArray.class
or
testPSA3part2 SmartArray.class
These will test your code in several ways and tell you which of your
methods are not working properly.
Turning in your homework
Since there are 2 parts to this assignment, there will be 2 separate
turnins. Both will use the same bundle script.
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 1 - Due Thursday Week 5
The files you need to turn in for Part 1 are:
- SmartArray.java - your implementation of the
SmartArray class.
You should put this file into a folder named PSA3, then cd
into that folder and run the command bundleP3.
Part 2 - Due Thursday Week 6
The files you need to turn in for Part 2 are:
- 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.
(NOTE: you do NOT need to turnin SensorData.java, because it did not use any ArrayLists)
You should put this file into a folder named PSA3, then cd
into that folder and run the command bundleP3.
(You will NOT need bookClasses for either part of this assignment)