Project 1: Implementing the Set Class using a List class Implement the functionalities of the Set Class, as given below, in Java by using a private data member of type ListReferenceBased. The code for testing your Set implementation, SetTest.java, as well as the modied ListReferenceBased class. You should rst dene an interface, SetInterface, for the following Set ADT operations in the le SetInterface.java and then implement that interface in Set.java

Constructors: a default constructor, a constructor that takes a single argument of type E and initializing the set to contain that object, and a copy constructor,

setSize: a method that returns the number of elements in the set as an int value,

print: a method that prints out the contents of the set,

insert: a method that takes an element of type E and inserts it into the set,

arrayInsert: a method that takes an array of elements of type E and inserts them into the set,

union: a method that takes a Set as an argument and returns a new Set that is the union of the current set and the argument,

intersection: a method that takes a Set as an argument and returns a new Set that is the intersection of the current set and the argument,

dierence: a method that takes a Set as an argument and returns a new Set that is the dierence of the current set and the argument,

in: a method that takes an element of type E and returns a boolean value depending on whether the given E is contained in the current set or not.

You are required to provide comments in javadoc format for each method and the class variables.

public class SetTest { // Simple main function to test ADT Set public static void main(String[] args) { Integer[] M ={2,3,5,7,11,13,17,19,23}; Integer[] N = {1,3,6,8,9,11,12,17,19,23,24,25,3}; Set A = new Set(); A.insert(10); A.arrayInsert(M); System.out.println(" Set A Follows:"); A.print();

Set B = new Set(); B.arrayInsert(N); B.insert(11); System.out.println(" Set B Follows:"); B.print();

Set C = A.union(B); Set D = A.intersection(B); System.out.println(" Set C which is (A Union B) Follows:"); C.print(); System.out.println(" Set D which is (A intersect B) Follows:"); D.print();

Set E = A.difference(B); Set F = B.difference(A); System.out.println(" Set E which is (A - B) Follows:"); E.print(); System.out.println(" Set F which is (B - A) Follows:"); F.print(); E.in(2); F.in(2); } // end main } //end class SetTest

/** class Node for the implementation of simple linked list. The node * contains only an item and a reference to the following Node*/

public class Node {

private E item; private Node next;

public Node(E newItem) { item = newItem; next = null; } // end constructor

public Node(E newItem, Node nextNode ) { item = newItem; next = nextNode; } // end constructor

public void setItem(E newItem) { item = newItem; } // end setItem

public E getItem() { return item; } // end getItem public void setNext(Node nextNode) { next = nextNode; } // end setNext

public Node getNext() { return next; } // end getNext

} // end class Node

* Reference-based implementation of ADT list. * Modify the code to implement a doubly linked list.

import java.util.Iterator;

public class ListReferenceBased implements ListInterface, Iterable{

private Node head; private int numItems; public ListReferenceBased() { numItems = 0; head = null; } // end default constructor /** Constructor that creates a list containing the specified element. * @param elt: element that is inserted in this new list. */ public ListReferenceBased(E elt){ numItems =0; append(elt); }

public ListReferenceBased(ListReferenceBased lst){ numItems=0; for (E item:lst) append(item); }

/** Tests if this list has no elements. * @return true if this list has no elements; * false otherwise. */public boolean isEmpty() {

return numItems == 0; } // end isEmpty

public int size() { return numItems; } // end size

private Node find(int index) { Node curr = head; for (int skip = 1; skip < index; skip++) { curr = curr.getNext(); } // end for return curr; } // end find

public E get(int index) throws ListIndexOutOfBoundsException { if (index >= 1 && index <= numItems) { // get reference to node, then data in node Node curr = find(index); E dataItem = curr.getItem(); return dataItem; } else { throw new ListIndexOutOfBoundsException( "List index out of bounds exception on get"); } // end if } // end get public void add(int index, E item) throws ListIndexOutOfBoundsException { if (index >= 1 && index <= numItems+1) { if (index == 1) { // insert the new node containing item at // beginning of list Node newNode = new Node(item, head); head = newNode; } else{ Node prev = find(index-1); // insert the new node containing item after // the node that prev references Node newNode = new Node(item, prev.getNext()); prev.setNext(newNode); } // end if numItems++; } else { throw new ListIndexOutOfBoundsException( "List index out of bounds exception on add"); } // end if } // end add

public void append(E item) { add(numItems+1, item); }//end append

public void remove(int index) throws ListIndexOutOfBoundsException { if (index >= 1 && index <= numItems) { if (index == 1) { // delete the first node from the list head = head.getNext(); } else{ Node prev = find(index-1); // delete the node after the node that prev // references, save reference to node Node curr = prev.getNext(); prev.setNext(curr.getNext()); } // end if numItems--; } // end if else { throw new ListIndexOutOfBoundsException( "List index out of bounds exception on remove"); } // end if } // end remove public void removeAll() { head = null; numItems = 0; } // end removeAll

public void delete(E item){ int index = contains(item); if (index == -1) System.out.println("Try to delete " + item + " but it is not in the list"); else remove(index); } public int contains(E elt){ Node current = head; int index=1; while (index <= numItems && !current.getItem().equals(elt)){ index ++; current = current.getNext(); } if (index <= numItems)// item found return index; else return -1; } public void display(){ for (E item: this) System.out.print(item+" "); System.out.println(); }

public ListReferenceBasedIterator iterator(){ return new ListReferenceBasedIterator(head); }

public class ListReferenceBasedIterator implements Iterator{ Node current;

public ListReferenceBasedIterator(Node node){ current=node; } public boolean hasNext(){ return (current!=null); }

public E next(){ E elt = current.getItem(); current = current.getNext(); return elt;}

public void remove(){} }

} // end ListReferenceBased

public interface BasicListInterface {

public boolean isEmpty(); public int size(); public void removeAll();

public E get(int index) throws ListIndexOutOfBoundsException;

} // end BasicListInterface

----------------------------------------------------------------------------

/** * Interface ListInterface for the ADT list. */

public interface ListInterface extends BasicListerface{ public void add(int index, E item) throws ListIndexOutOfBoundsException, ListException;

public void append(E elt);

public void remove(int index) throws ListIndexOutOfBoundsException; public void delete(E elt);

public int contains(E elt);

public void display();

} // end ListInterface

------------------------------------------------------------------------------------------

public class ListException extends RuntimeException { public ListException(String s) { super(s); } // end constructor } // end ListException

----------------------------------------------------------------------------------------------

public class ListIndexOutOfBoundsException extends IndexOutOfBoundsException { public ListIndexOutOfBoundsException(String s) { super(s); } // end constructor } // end ListIndexOutOfBoundsException