P#2: SortedIntList Solution

For your second programming assignment you are to write a class called SortedIntList that is a variation of the ArrayIntList class   discussed   in   lecture.  Turn   in   two   files   named   SortedIntList.java and SortedIntListTest.java on the Homework section of the course web site

 

 

For this assignment you are to write a class called SortedIntList that is a variation of the ArrayIntList

class written in lecture. Your class has two primary differences from the original list:

         A SortedIntList must maintain its list of integers in sorted order (non-decreasing).

         A SortedIntList has an option to specify that its elements should be unique (no duplicates).

 

The new class should have the same public methods as the old class except for the two-parameter add method that adds a value at a particular index and the set method. Because we want to keep the list in sorted order, we won’t allow the client to specify where something should go, so these methods should not be public methods of the new class.

 

Two of the methods should be rewritten.  The single-parameter 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.  Your add method should not re-sort the entire list (either by calling Arrays.sort or something you wrote yourself).  Finding the correct position and inserting the new element at that position is more efficient than resorting the whole 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       (more       on       this       later).  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). If the capacity is negative, an IllegalArgumentException should occur.
SortedIntList(int capacity)
This should construct a list with the given capacity and with unique set to false (duplicates allowed). If the capacity is negative, an IllegalArgumentException should occur.
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 four new methods:

 

Method
Description
int min()
This method should return the smallest element value contained in the list.  For example, in the list [4, 4, 17, 39, 58], the min is 4. If the list is empty, it has no minimum element, so you should throw a NoSuchElementException.
int max()
This method should return the largest element value contained in the list. For example, in the list [4, 4, 17, 39, 58], the max is 58. If the list is empty, it has no largest element, so you should throw a NoSuchElementException.
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 “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.

 

To get access to the Arrays class, you should include this line at the beginning of your class:

 

import java.util.*;

 

 

 

 

Testing Program (SortedIntListTest.java):

Along  with  your  SortedIntList, turn  in  a  short  testing  file  named  SortedIntListTest.java.   This program should test your implementation of SortedIntList by creating at least two lists, adding some elements to them, calling various methods, and checking the expected results.  This part of the assignment is worth only a few points, but we want you to practice testing your own code.  For full credit, your testing file must contain at least 2 test methods, and you must call at least 3 of the different methods on the list(s) you create.

There are also several provided testing programs on the course web site.  You may ask, "Why do I need to write my own testing program when these testing programs are already provided?"  Our testing programs are large and complex.   It can be good to have a smaller test that runs just a few methods that you are working on.   We encourage you to add to this program as you develop your SortedIntList.   If you want to write a more complex test, that is fine, but not required.

 

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 two-argument add method is no longer a public method.

c.   Modify the one-argument add method so that it preserves sorted order.  You may need to use binary search if your solution involves two steps (first locate, then insert).

d.   Modify indexOf so that it uses the binary search method. e.   Add the min and max methods.

 

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.

References

Textbook Chapter 15 covers the implementation of ArrayIntList in detail.

Textbook sections 13.1 and 13.3 discuss the binary search algorithm in more detail.   13.3 discusses how it is implemented and its return values in detail.  Seeing how it is implemented may help you understand how to use it appropriately.

 

Style Guidelines and Grading

You may not use any features from Java's collection framework on this assignment, such as ArrayList or other pre-existing collection classes.  You also may not use the Arrays.sort method to sort your list.

A major focus of our style grading is redundancy.   As much as possible you should avoid redundancy and repeated logic within your code, such as by factoring out common code from if/else statements, creating "helper" methods to capture repeated code, or having some of your methods/constructors call others if their behaviors are related.  Any additional methods you add to SortedIntList beyond those specified should be private so that outside code cannot call them.  Note that even constructors can be redundant; if two or more constructors in your class (or the superclass) contain similar or identical code, you should find a way to reduce this redundancy by making them call each other as appropriate.

Properly encapsulate your objects by making any data fields in your class private.  Avoid unnecessary fields; use fields to store important data of your objects but not to store temporary values only used within a single call to one method.  Fields should always be initialized inside a constructor or method, never at declaration.

You should follow good general style guidelines such as: appropriately using control structures like loops and if/else statements; avoiding redundancy using techniques such as methods, loops, and if/else factoring; properly using indentation, good variable names, and proper types; and not having any lines of code longer than

100 characters.

Commenting will be more of a style focus on this program (and future programs) than it was in 142.  You should comment your code with a heading at the top of your class with your name, section, and a description of the overall program.  Also place a comment heading atop each method, and a comment on any complex sections of your code.

Not only will we look for the existence of comments on this assignment, but we also have stricter expectations about the quality of their content.  Comment headings should use descriptive complete sentences and should be written in your own words, explaining each method's behavior, parameters, return values, and pre/post-conditions as appropriate.  If the method potentially throws any exceptions, comment this and explain what exceptions it throws and under what conditions it will throw them.   Be concise but specific in your comments.   The ArrayIntList class is a good example of appropriate commenting style for this assignment.  (Your test program should have an overall descriptive comment header at the top of the class, but it does not need commenting on each testing method or otherwise throughout the code.)

For  reference,  our  SortedIntList.java is  around   175  lines  long  including  comments  (and  has   80 "substantive" lines according to our Indenter tool on the course web site).  But you do not have to match this; it's just listed as a sanity check.