handout #4
CSE143—Computer Programming II
Programming Assignment #1
due: Thursday,
For your first programming assignment you are to
write a class called SortedIntList that is a variation of the ArrayIntList
class discussed in lecture (handout #3).
The primary differences are that your new class must maintain the list
of integers in sorted (non-decreasing) order and that it will have an extra
option to specify that the numbers should be unique.
The new class should have the same public
methods as the old class except for the method that adds a value at a
particular index. Because we want to
keep the list in sorted order, we won’t allow the client to specify where
something should go, so this method should not be a public method of the new
class.
Two of the methods should be rewritten. The add method should no longer add at the
end of the list. It should add the value
in an appropriate place to keep the list in sorted (non-decreasing) order. The add method also has to pay attention to
whether the client has requested “unique” values, in which case it has to be
careful not to add any duplicates to the list.
In addition, the indexOf method should be rewritten to take advantage of
the fact that the list is sorted. It
should use the much faster binary search algorithm rather than the sequential
search algorithm that is used in the original ArrayIntList class (see the
private method described later in this writeup). We will also slightly change the postcondition
of indexOf. The ArrayIntList version
promises to return the index of the first occurrence of the search value. Because we are using a binary search, we will
instead guarantee only that the index is for an occurrence of the search value (not necessarily the first one).
The other methods from ArrayIntList like the
remove method can be used without modification in the new class. You should comment each method in your
class. If you borrow the comments from
the ArrayIntList class, then be sure to comment the new methods in a similar
manner.
Your new class will have an extra piece of state
information. Each SortedIntList will
keep track of whether or not it is limited to unique values. Think of it as a sort of on/off switch that
each list has. If the unique switch is
set to off (false), then the list adds everything, even if that leads to
duplicate values. If the unique switch
is set to on (true), then calls on add that pass values already in the list
have no effect (i.e., add ensures that no duplicates are added). For example, if you start with an empty list
that has the unique switch off, then adding three occurrences of the number 42
will generate the list (42, 42, 42). Adding those same three occurrences of 42 to
an empty list that has the unique switch on will
generate the list (42).
This
extra piece of state will require the addition of several new methods. Your class should keep the DEFAULT_CAPACITY
constant and should have a total of four constructors:
|
Method |
Description |
|
SortedIntList(boolean
unique, int capacity) |
This
should construct a list with given capacity and with the given setting for
whether or not to limit the list to unique values (true means no duplicates,
false means duplicates are allowed) |
|
SortedIntList(int
capacity) |
This
should construct a list with the given capacity and with unique set to false
(duplicates allowed) |
|
SortedIntList(boolean
unique) |
This
should construct a list of default capacity with the given setting for unique
(true means no duplicates, false means duplicates are allowed) |
|
SortedIntList() |
This
should construct a list of default capacity with unique set to false
(duplicates allowed) |
Your class should include the following two new
methods:
|
Method |
Description |
|
boolean
getUnique() |
This
method should return the current setting for unique (true means no duplicates,
false means duplicates are allowed) |
|
void
setUnique(boolean value) |
This
method allows the client to set whether or not to allow duplicates (true
means no duplicates, false means duplicates allowed) |
The setUnique method presents a potential problem
for us. Suppose that the client has
constructed a list and has added many values, including duplicates. If the client then tries to set unique to
true, this is supposed to prevent duplicates.
But the duplicates are already there.
In this case, the setUnique method should remove the duplicates and
should guarantee that no additional duplicates are added unless the client
changes the setting back to false. If
the client changes the setting back to false, that will mean that duplicates
can then be added, but this doesn’t have to behave like an “undo” operation
that would put back duplicates that you previously removed.
You are required to use the built-in
Arrays.binarySearch method discussed in section for all of your location
testing (Where is a value? Where would I
insert a new value?). You can find the
documentation for it in the Java API documentation that is the first link under
“useful links” on the class web page.
Keep in mind that because this is a static method, you have to use the
class name in calling it. For example,
to find the location of the value 42 in an array called data when we want to
explore the first twelve elements, you’d say something like:
int index
= Arrays.binarySearch(data, 0, 12, 42);
Remember that the “from index” is inclusive,
which is why we use 0, and the “to index” is exclusive, which is why we use
12. For those of you working on a Mac or
for others who do not have Java 6 on their machine, you can copy a file called
Arrays.java from the class web page that will allow you to write the program.
To get access to the Arrays class, you should
include this line at the beginning of the class (even the Mac users that are
using our Arrays.java should do this so that their programs will execute
properly when we grade them):
import
java.util.*;
In terms of correctness, your class must provide
all of the functionality described above and the execution time for indexOf
must indicate that you are using a binary search rather than a sequential
search. In terms of style, we will be grading
on your use of comments, good variable names, consistent indentation and good
coding style to implement these operations.
You should name your file SortedIntList.java and
you should turn it in electronically from the “assignments” link on the class
web page.
Development
Strategy
One
of the most important techniques for software professionals is to develop code
in stages rather than trying to write it all at once (the technical term is iterative enhancement or stepwise refinement). It is also important to be able to test the
correctness of your solution at each different stage.
We have noticed that many 143 students do not
develop their code in stages and do not have a good idea of how to test their
solutions. As a result, for this
assignment we will provide you with a development strategy and some testing
code. We aren’t going to provide
exhaustive testing code, but we’ll give you some good examples of the kind of
testing code we want you to write.
We are suggesting that you develop the program
in three stages:
1. For this version, we
won’t worry about the issue of unique values.
We just want a basic version of the class that keeps a list in sorted
order and that uses binary search to speed up searching. This stage involves all of the following (not
necessarily in this order):
a. Copy ArrayIntList.java
to SortedIntList.java and change all occurrences of ArrayIntList to
SortedIntList. That way you’ll have a
new class that has the same behavior as the old ArrayIntList class (including
the two constructors).
b. Make sure that the
method to add at an index is no longer a public method.
c. Modify add so that it
preserves sorted order. You may need to
use binary search here as well if your solution involves two steps (first
locate, then insert).
d. Modify indexOf so that
it uses the binary search method.
2. Modify your code so that
it keeps track of whether or not the client wants you to guarantee that the
list has unique values. Add the two
constructors that involve setting unique and modify add so that it doesn’t add
duplicates if unique is set to true.
3. Modify your code to have
getUnique and setUnique. Remember that
if the client calls setUnique and sets the value to true, you have to eliminate
any duplicates that might be in the list.
We will be providing testing code for each of
these three stages and for this program only you are allowed to discuss how to
write testing code with other students. Keep
in mind that the tests are not guaranteed to be exhaustive. They are meant to be examples of the kinds of
tests you should perform. In particular,
you will want to do a lot of simpler testing before you try running any of
these high-powered tests that really push the limits.