A03

Due Date: Thursday, January 29
File(s) to be submitted: KeepSmallInt.java
Sample Output: SampleOutput.html
Starter Files:

• TestKeepSmall.java

KeepSmallInt (Non-recursive Sorting)

Summary

Create a class named KeepSmallInt that uses an array to hold a given number of small integer values. Use the program TestKeepSmall to test your implementation.

Details

Your grading scheme for this course calculates your assignment grade by dropping the three smallest of your ten assignment scores. Naturally I will need to find the three smallest values among all your assignment grades. This week you will create a class that helps me do that.

I will actually do this with a spreadsheet, but in principle I could write a Java program to do it.

Your class is designed to keep track of a (fixed, finite) number of integer values. The class allows any integer values, altho' the testing program restricts itself to grades (integers in the range 0 to 100). The client can add as many values as they like to the KeepSmallInt object, but only the smallest values are kept. (The number of smallest values to keep is set by the constructor.)

For example, if the KeepSmallInt object is set to remember three values, and the client adds 10, 20, 30, 40, 50, 5, -4 and 100 to it, then the object remembers only the -4, 5 and 10.

Your class needs the following contructors and methods:

• KeepSmallInt(int reqCapacity): The constructor specifies how many small values to hold. The requested capacity must, of course, be positive. Otherwise, the constructor throws an IllegalArgumentException.
• int capacity(): Returns the number of elements this container can hold. That is, the size requested from the constructor.
• int size(): Returns the number of elements in this container. That is, the number of values it is currently remembering. (This value will start off at zero, and increase by one with each addition until it reaches the requested size.)
• boolean isEmpty(): Returns true if this container has no elements in it; false otherwise.
• void clear(): Removes all the elements from this container. The size returns to zero, but the capacity remains the same.
• Integer add(int newElement): Considers the given element for addition to this container. If there is space available in this container, then given element will be added and null returned.

  Note that the return type is Integer, not int, so null is a valid value to return.

  If this container is already full, this value will be added only if it is smaller than one of the previously-remembered elements. In this case, the value returned is the value that does not get remembered.

  Which may be newElement itself, if it is larger than all the previously-remembered elements.

• int get(int index): Returns the smallest-but-i element in this container. For example, get(0) returns the smallest element in this container, while get(2) returns the third smallest element (i.e. the one with exactly two elements before it in the sorted order). The method throws a NoSuchElementException if index is not in the range 0..size()-1
• boolean contains(int reqVal): Returns true if reqVal is one of the remembered values; false otherwise.
• int[] toArray(): Returns a sorted array with all and only this container's elements. The length of the returned array is the same as the size() of this KeepSmallInt. (Thus the returned array may have a length of zero.) The returned array must not allow the client to change values inside the KeepSmallInt object.

Hints

It'll be helpful if you make the array one space larger than it "needs" to be. For example, if it's remembering 2 grades, make the array size 3. That'll give you space to enter an extra value, and the value ending up in the last element of the array is the one that gets "bumped out". Just be careful to remember that the element in the "extra" position is (technically) not in the container!

You are not allowed to use a (full) sorting algorithm on your private array. Instead use the insert algorithm described in the course notes. Then even if the container is very large (remembering the 1000 smallest elements it's been presented with, for example), considering an element for insertion will still go (relatively) quickly.