You will be creating a new class called an IntegerSet. Here are the characteristics of the IntegerSet type.

Integers stored are unique. (No duplicates).

The IntegerSets are ordered.

The IntegerSet class is given to you to complete. There are methods that are already finished and there are other methods you must complete. Here are the list of methods in the class.

magnitude()- This one is completed and returns the size of the set.

toString()- This one is completed and returns a string representation of the class.

contains() - You must write the code for this method. This method returns whether or not a value is in the set.

uniqueElements()- You must write the code for this method. It takes an array and creates a new array with the unique elements from the original. For example, [1, 3, 1, 2, 1] will return a new array containing [1, 2, 3].

union() - You must write the code for this method. This is the mathematical union on two sets which creates a new set that contains all the elements from both sets. For example, [1, 2, 3] U [2, 3, 5, 6] results in a new set [1, 2, 3, 5, 6].

Intersection()- You must write the code for this method. This is the mathematical intersection operation on two sets that returns a new set that contains elements that belong to both sets. For example, [1, 2, 3] [2, 3, 4, 5, 6] results in a new set [2, 3].

For each method you need to complete it can be done with a poor O(N²) time, but the methods must at least be O(NlogN) time (So no brute force algorithms). The intersection method can be completed in O(N) time, but this is not a requirement to get full credit. Having the elements sorted is key so make sure to exploit this fact (remember your searches). The union method is a O(N) algorithm unless you intentionally make it poorly optimized.

You are given another file to help you with some actions you may need to perform in a class called IntArrayOperations. The methods in this class are all static (think Math class in Java) so you dont have to create an object to use the methods. Just invoke them by using IntArrayOperations.the_method_you_need(). Here is an explanation of the methods.

truncateArray() - Takes an integer array and a count and creates a new array with elements from the passed array up to count. For example, [1, 2, 3, 4] and count = 2 returns [1, 2].

getCopy() - Returns a copy of an integer array. Useful for preventing functional side effects on an array if you dont want to affect the original.

printArray() -Prints the elements of an integer array nicely.

swap() - Swaps two elements of an array.

fillArray() - Fills the array with integers from 1 to array.length.

randomFillArray() - Takes an integer array, a minimum, and a maximum and fills the array with random elements between minimum and maximum (inclusive).

shuffle()- Shuffles and array.

In addition to the methods provided for you, you may write any additional methods that may help you. Be sure to include these methods in the IntegerSet class so they can stay in one spot and you dont have to worry about sending me several class files.

What you need to complete

Finish the contains, uniqueElements, union, and intersection methods.

contains()

This method returns true or false if a given value is in the set. Here is an example,

IntegerSet iS1 = new IntegerSet([1,2,3,4]); iS1.contains(3); //returns true iS2.contains(6); //returns false

Tips

Remember that your set should be sorted. (See uniqueElements method). What algorithm can you use to complete this contains method?

This method will be handy for you in a later method.

uniqueElements()

This method is called inside the constructor and is used to create the int array that represents an IntegerSet. The int array returned has the characteristics of having only unique elements and, incidentally, being sorted. This method takes an array like [1, 2, 1, 3, 1, 3, 2, 4] and returns an integer that will be [1, 2, 3, 4].

Tips

You should use a temporary array that is the same size as the array being passed in to temporarily store the unique elements (making sure to also keep count) and return a truncated version of the temp array.

intersection()

This method takes another IntegerSet object and intersects it with the calling IntegerSet object. Returns a new IntegerSet object. Here is an example:

IntegerSet iS1 = new IntegerSet([1,2,3,4]); IntegerSet iS2 = new IntegerSet([3,4,5,6,7]); iS1.intersection(iS2) //a new IntegerSet([3, 4]);

Tips

This method is tricky as the sets magnitude (size) may be different. This means that the result can be no bigger than the smallest set. You will still need to truncate your result so keep track of how many intersections are made. Use a temp result just like in uniqueElements().

This one can be completed with a O(N) algorithm but shoot for the O(NlogN) version first. Remember that the sets are sorted so what can you use?

Keep in mind that a linear search can produce the worst case time of O(N²).

union()

The union method takes another IntegerSet object and returns a new IntegerSet object that contains the unique elements of both sets. Returns a new IntegerSet object. Here is an example,

IntegerSet iS1 = new IntegerSet([1,2,3]); IntegerSet iS2 = new IntegerSet([3,6]); iS1.intersection(iS2) //a new IntegerSet([1, 2, 3, 6]);

Tips

What is the maximum possible size of a resulting set? You should create a temporary array of that size.

This one is the easiest, and heres why. If you did your job correctly with uniqueElements you can just shove all the elements in the temporary array and return a new IntegerSet (which will call the uniqueElements method and do the heavy lifting that you already prepared for.)

This one does not require sorting nor searching but is a demonstration on the power of Classes and objects and how a little hard work can allow us to be lazy later.

What you need to turn in

You must submit your completed version of the IntegerSet class. All methods must be at least O(NlogN) time. All methods must return the correct results. Make sure to use the Test class and to add your own tests to verify. I have given example tests that you can change or write your own.

Any additional methods you write should be included in the IntegerSet class.

Integerset class:

public class IntegerSet {

// The array that represents the set. private final int set[];

/** * The constructor for IntegerSet. When an IntegerSet is created it must be * initialized with an integer array. The set will then pull out the duplicated * items and keep the unique integers. * * @param arr * The array to create the set from. */ public IntegerSet(int arr[]) { if (arr == null) { throw new IllegalArgumentException("The array must not be null"); } set = uniqueElements(arr); }

/** * This is the size of the set which, in this case, is just the length of the * array. * * @return The length of the set. */ public int magnitude() { return set.length; }

/** * This method is private and is used to help set up the set array. An integer * set is one in which the elements are unique (no duplicates) and are sorted. * * @param arr * The array that will be used to retrieve the unique elements from. * @return The new integer array that contains the unique elements from arr. */ private int[] uniqueElements(int arr[]) { return null; }

/** * This method returns whether or not value is located in the set. If the value * is in the set then return true otherwise return false.
* Example: *

 * IntegerSet iS1 = new IntegerSet([1,2,3,4]); * iS1.contains(3); //returns true * iS2.contains(6); //returns false * 

* * @param value * The integer to look for. * @return True if value is located in the set otherwise false. */ public boolean contains(int value) { return false; }

/** * A union of two sets is a new set that contains all elements from both sets. * This method takes another set and unions it with the set that calls this * method. A new IntegerSet is returned that contains the union of both sets.
* Example: *

 * IntegerSet is1 = new IntegerSet([1, 2, 3, 4]); * IntegerSet is2 = new IntegerSet([3, 4, 5, 6, 7, 8]); * is1.union(is2) //returns new IntegerSet([1, 2, 3, 4, 5, 6, 7, 8]); * 

* * @param otherSet * The set to be unioned with. * @return A new IntegerSet that is the union of the calling set with the * otherSet. */ public IntegerSet union(IntegerSet otherSet) { return null; }

/** * The intersection of two sets is a new set that contains elements that occur * in both sets. This method takes another set and intersects it with the set * that calls this method. A new IntegerSet is returned that contains the * intersection of the two sets.
* Example: *

 * IntegerSet is1 = new IntegerSet([1,2,3,4]); * IntegerSet is2 = new IntegerSet([3,4,5]); * is1.intersection(is2) //returns new IntegerSet([3, 4]); * 

* * @param otherSet * The set to be intersected with. * @return A new IntegerSet that is the intersection of the calling set with the * otherSet. */ public IntegerSet intersection(IntegerSet otherSet) { return null; }

/** * Returns a string representation of an IntegerSet type. The returned string * will have the following structure. * * set{ elements in the set separated by a comma }. */ public String toString() { StringBuilder sb = new StringBuilder(); sb.append("set{ "); for (int i = 0; i < set.length; i++) { sb.append(set[i]); if (i < set.length - 1) { sb.append(", "); } } sb.append(" }"); return sb.toString(); } }