handout #4
CSE143—Computer Programming II
Programming Assignment #1
due: Friday, 10/7/05, 5 pm
For your first programming assignment you are to
write a class called SortedIntList that is a
variation of the IntList 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 non-constructor
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 IntList class (see the private method
described later in this writeup). We will also slightly change the postcondition of indexOf. The IntList 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 non-constructor methods from IntList 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 IntList
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. If it is limited to unique values, then no
duplicate values are allowed. If it is
not limited to unique values, then the list will allow duplicate values.
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) |
Constructs
a list with given capacity and with 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) |
Constructs
a list with given capacity with unique set to false (duplicates allowed) |
|
SortedIntList(boolean
unique) |
Constructs
a list of default capacity with given setting for unique (true means no
duplicates, false means duplicates are allowed) |
|
SortedIntList() |
Constructs
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() |
Returns
current setting for unique (true means no duplicates, false means duplicates
are allowed) |
|
void
setUnique(boolean value) |
Sets
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 should write your own testing code for this
assignment. A sample testing program
will be provided on the assignments page, but this is only a partial test of
correctness. The sample testing program
also tests extreme cases, so it is not the best testing tool to use for initial
testing. You are not allowed to share
your solution to SortedIntList with other students,
but you are allowed to share your testing code on the class message board.
Below is a private method that you should
include in your class for performing binary search. You should include this method without
modification. You should use it for all
of your location testing (Where is a value?
Where would I insert a new value?).
// pre :
elements low through high of list are in sorted (nondecreasing)
// order
// post: returns the index of
the given key in the list, returns
// (-(insertion point) - 1) otherwise. The insertion point is
// defined as a point at which the key
should be inserted to
// preserve sorted order. If the list contains multiple copies of
// the key, there is no guarantee as to
which index is returned.
private
static int binarySearch(int[] list, int key,
int
low, int high) {
while (low <=
high) {
int
mid = (low + high) / 2;
int
midVal = list[mid];
if (midVal < key) {
low = mid
+ 1;
} else if (midVal
> key) {
high = mid
- 1;
} else {
return
mid; // key found
}
}
return -(low +
1); // key not found.
}
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.