handout #4
CSE143—Computer Programming II
Programming Assignment #1
due: Friday,
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 inclusive of list are in sorted
// (nondecreasing) order
// post: returns the index of the given key in the list within the range
// low through high inclusive, 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 in the given range, 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. For all cse143
assignments you should be thoroughly testing your solution. For this assignment, two sample testing
programs are being provided called SortedIntListTest.java
and SortedIntListTest2.java. The first
produces a large amount of output that you would have to inspect to make sure
that your implementation is correct. The
second throws exceptions when tests fail.
These are two examples of how to do testing. They do not represent an exhaustive test
suite.
Sample
Testing Program SortedIntListTest.java
// Stuart Reges
// 1/6/06
//
// Short program that calls
many methods of the SortedIntList class,
// displaying the state of
the list as it goes.
import
java.util.*;
public class SortedIntListTest {
public static
final int MAX = 5;
// program will add numbers in the
// range
of -MAX to +MAX
public static void
main(String[] args) {
SortedIntList
list = new SortedIntList();
Random r = new Random();
// add a few elements
addElements(list, r, MAX);
// check the indexOf
method for a range of values
checkIndexOf(list);
// check the remove method by emptying
the list
checkRemove(list, r);
// now fill the list back up
addElements(list, r, 2 * MAX);
// and see whether setting unique to
true eliminates duplicates
list.setUnique(true);
System.out.println("after setting unique to true, list = " + list);
System.out.println();
// now bombard the list to make sure no
duplicates appear
addElements(list, r, 5 * MAX);
// and check the indexOf
and remove methods in this mode
checkIndexOf(list);
checkRemove(list, r);
}
// adds given number of elements to the
list, reporting the result.
public static void
addElements(SortedIntList
list, Random r, int number) {
System.out.println("initially list = " + list);
for (int i = 0; i
< number; i++) {
int next = r.nextInt(2 *
MAX + 1) - MAX;
list.add(next);
System.out.println("adding
" + next + ", list = " + list);
}
System.out.println();
}
// checks the index of values from -(2 * Max) to +(2 * MAX); obviously
// many of these should yield -1 when indexOf is called
public static void
checkIndexOf(SortedIntList
list) {
System.out.println("testing indexOf with list =
" + list);
for (int i = -2 * MAX; i <= 2 * MAX; i++) {
System.out.println("indexOf " + i + " =
" + list.indexOf(i));
}
System.out.println();
}
// empties the list in random order,
reporting the result as it goes
public static void
checkRemove(SortedIntList
list, Random r) {
System.out.println("testing remove with list = " + list);
while (list.size() > 0) {
int index = r.nextInt(list.size());
list.remove(index);
System.out.println("removing
at " + index + ", list = " + list);
}
System.out.println();
}
}