P8: Implementing Set using Linked List

1. Objective

The objective of this assignment is to implement a Set as a linked list. Note that a Set does not have duplicates.

2. Tasks

You are given a class called LinkedList that contains an inner class called Node. You have already seen these classes in your lectures. Download the LinkedList class containing Node here. Note that some of the attribute visibilities were changed to protected and methods were added or changed, so make sure you use the provided code here, and not the code from the lecture.

Your task is to implement a new class called Set that extends the given LinkedList class and implements the given interface called ISet. Download ISet here. You will declare your Set class as follows:

public class Set extends LinkedList implements ISet

The methods in ISet are as follows:

1. public void add(Object item):

   This method adds an item to the set. A duplicate item is not added. Hint: Override the add method defined in the LinkedList class but use its functionality using super.

2. public boolean in(Object item):

   This method returns true if the item is in the set, false otherwise.

3. public Object[] toArray():

   This method returns a new array that contains all the items in the set. If the size of the set is 0, return an empty array. The objects in the set are unique (i.e., no duplicates), so the returned array cannot contain duplicates.

4. public ISet fromArray(Object[] elements):

   This method creates and returns a new set from the items contained in the elements array. The array may contain duplicates, but the Set implementation should not contain duplicates. If the array is empty or null, return a set of size 0 with head referring to null. If duplicates of an item are present in the array, then ignore all the occurrences of this item after the first one.

5. public ISet intersection(ISet other):

   This method returns a new set that contains only those items that are present in both "this" set and the other set. The order of items in the returned set does not matter. The other set and "this" set remain unchanged.

6. public ISet union(ISet other):

   This method returns a new set that contains the union of the items that are present in "this" set and the other set. Obviously common elements should appear only once in the result. The order of items in the returned set does not matter. The other set and "this" set remain unchanged.

3. Preliminary and Final Testing

You cannot change ISet, i.e., no method declarations may be added, deleted, or changed. You cannot change the implementation of LinkedList. Do not copy the methods from LinkedList to Set. You should only implement the new methods declared in ISet in Set. It is okay to add private helper methods to Set.

Test your program with test data in addition to what is already provided in the assignment below. Keep in mind that we will not test your main method -- the methods you implement will be tested directly. However, you should use your main to test the methods that you write. A barebones main for Set can include something like:

    public static void main(String[] args) {
        ISet tester = new Set();
        String[] names = {"Alex", "Hajar", "Asa", "Sudipto", "Koen", "Asa"};
        ISet s1 = tester.fromArray(names);
        System.out.println("After creating set s1 from array:\n" + s1);
        System.out.println("Printing array from s1:\n"+ Arrays.toString(s1.toArray()));    
        String[] otherNames = {"Gareth", "Alex", "Swapnil", "Chris", "Asa"};
        ISet s2 = tester.fromArray(otherNames);
        System.out.println("After creating set s2 from array:\n" + s2);
        ISet s3 = s1.intersection(s2);
        System.out.println("Intersection of s2 and s3:\n" + s3);
        ISet s4 = s1.union(s2);
        System.out.println("Union of s2 and s3:\n" + s4);
    }

We encourage you to write your own tests for each method to test various scenarios. Preliminary testing will be performed on your methods to partially test their functionality. More comprehensive tests will be used during final testing. During preliminary testing, your score equals the number of test cases passed. However, during final testing, certain test cases may be weighted more than others. More difficult methods will be worth more points.

4. Submission

Submit the Set.java file via the online checkin system. This system performs preliminary testing of your program using the examples above. Final grading will be performed using a different set of test inputs. Passing preliminary testing guarantees a 20% on the final grade.