Purpose:

This week you will focus on reinforcing what you learned about arrays and Dynamic Lists by building a simple Set class.

Detailed Instructions:

For this assignment, you will be using Generics and your knowledge of Lists to create a Generic Set class. A set is a data structure which does not allow duplicate values. Your task this week is to create your own set class to handle sets of any generic type.

General Directions:

Be sure to use the exact names mentioned for methods, data fields and class names.

Always remember that a set is not allowed to contain duplicate values.

You may not use any methods related to Sets from the Java library.

You may not use ArrayList or any methods from the ArrayList class.

You may not use any built-in Java methods to implement your solution.

You are required to implement this class using Generics.

Please use the exact method names. Also, pay very close attention to whether or not a method accepts certain parameters or returns a certain value.

You must follow all directions exactly.

Recall: capacity refers to actual size of the array. size refers to the number of elements in the array. capacity may be >= size.

Always be thinking about how efficient your code is.

The SortedSet Class:

The name of your class shall exactly be SortedSet.

This will be a generic class which should only allow data types which implement the Comparable interface. (Bounded by Comparable).

Take a look at Homework 02 for how to set this up.

The class shall always keep the values in the set in sorted order.

Data Fields:set:

Your class shall have a data field called set. This data field shall be an array of generic values. This data field shall also be private with no getters or setters.

To initialize the correct generic array for this assignment, use the following: E[] set = (E[])(new Comparable[array size]);

NOTE: Under normal circumstances we cannot instantiate a generic array. What I have above is a work around of sorts see the section on Generics Restrictions from the readings for the Generics Lecture.

size:

Your class shall have a private integer data field called size.

This data field shall represent the number of actual elements in the set. (not the capacity).

Please be aware that size may not necessarily be equal to the length of the array.

NOTE: You will need to manually keep track of the size of your set. When a value is added to the set, the size should increase by 1.

Constructors:SortedSet():

Your class shall have a default constructor which creates an empty set with an initial capacity of 10.

SortedSet(capacity):

Your class shall have a constructor which accepts one integer parameter.

This parameter is the initial capacity of the set and should be used to initialize the size of the internal array.

SortedSet(E ... values):

Your class shall have a constructor which will accept a comma separated list of generic values as a parameter.

This constructor can also accept a generic array.

For this special type of parameter, you will want to review variable-length parameter (argument) lists.

REMINDER: A set cannot contain duplicate values.

HINT: Use your add() method to implement this constructor.

HINT: Consider the order in which you implement the following methods. You should realize that some methods will help you to implement other methods.

Public Methods:public boolean exists(value):

This method shall accept a single value as a parameter.

This method shall return true or false depending on whether or not the given value already exists within your set.

Runtime Requirement:

This method must have a Logarithmic ( O(logn) ) runtime.

O(logn): Since the data will always be sorted, You must implement this method in O(logn) time by implementing a binary search instead of a linear search.

You may not use any binary search methods that already exist in Java.

The pseudocode for Binary Search is given here:

low = lower bound array index of where to start searching high = upper bound array index of where to stop searching key = value to search for array[] = the array to search while key not found if low > high, end search, value not found. compute the midpoint of the search area: mid = (high - low) / 2 if array[mid] < key, update low to (mid + 1) if array[mid] > key, update high to (mid - 1) if array[mid] == key, key value is found end while

public void add(value):

This method shall accept a single value as a parameter.

This method shall add the value to the set, provided that the value does not already exist within the set.

This method shall also consider the size of the set. If there is no more room in the set, this method shall resize the set (see the resize() method below).

Runtime Requirement:

This method must have a Linear( O(n) ) runtime.

Can you use your exists() method to find if the value to add exists and still have a linear runtime? Yes you can!

exists() should be O(logn) and you should implement the insertion part of this add method in linear time. So the total runtime would be O(n + logn) which is still O(n). However, you can technically make the add() method faster if you don't use the exists() method and you check for duplicate values while you are trying to add the new value.

You cannot use nested loops.

To have a linear runtime, we have to do the following:

Iterate through the set.

As you are iterating, look for the insertion point.

EXAMPLE: set = {1, 4, 6, 8, 10} and you want to insert 7. The insertion point would be between 6 and 8.

While you are iterating, if you find that the value already exists, display an appropriate error message, and do not add the duplicate value.

(You only need to look for a duplicate if you didn't use your exists method previously to determine if the new value already exists in the set).

Once you find the insertion point, you need make room by right-shifting all elements from the insertion point to the end.

Finally, add the new value to the insertion point.

public void remove(value):

This method takes a value and removes that value from the set.

Check to see if the value exists first. This can be done with the exists method, or can be more efficient if you check while you are doing your linear pass through the array.

Be sure to display an appropriate error message if the value to remove does not exist in the set.

Runtime Requirement: O(n) Linear Runtime

This method will be similar to add and will involve shifting.

get(index):

This method shall accept an integer parameter which is an index value.

This method will return the value stored at the given index in the set.

You may assume for this assignment that the index will be within bounds.

Runtime Requirement: O(1).

size():

This method shall take no parameters and return the size (number of elements) in the set.

Runtime Requirement O(1).

toString():

This method shall return a String representation of your set.

If the set is empty, you may print out an empty pair of {}.

Your string representation should look something like: {value1, value2, value3, value4, value5, etc...}.

Runtime Requirement: O(n)

Private Methods:resize():

This method shall be responsible for resizing the capacity of the set when the set becomes full.

This method shall resize the set array by creating a new array double the current capacity of the set array.

This method shall copy the values from the old set array to the new array.

This method should be called anywhere in the code where the set could become full.

Runtime: O(n)

Testing:

You should test all functionality of your classes as exhaustively as possible. Write a Main class to show that everything works correctly.

Please make sure the output is nice and organized.

You must demonstrate that ALL features of your SortedSet class are working with the following data types.

Integers

Doubles

Strings

Movie Download MovieObjects

Be sure to download this class and include it in your project.

I will be testing your classes using Integers, Doubles, Strings, and a Custom class that I will create.