handout #3
CSE143—Computer Programming II
Programming Assignment #1
due: Wednesday, 6/29/05, 9 pm
(courtesy of Stuart Reges)
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 #4). 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 all of the same
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 included in 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.
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.
The other 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 try to comment the new
methods in a similar manner.
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 MUST
name your file SortedIntList.java and turn it in
electronically from the “assignments” link on the class web page.