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.