Problem Overview This assignment requires you to implement a set collection using a doubly-linked list as the underlying data structure. You are provided with the Set interface and a shell of the LinkedSet implementing class. You must not change anything in the Set interface, but you must create correct implementations of the methods in the LinkedSet class. In doing so you are allowed to add any number of private methods and nested classes that you need, but you may not create or use any other top-level class and you may not create any public method. You must also use without modification the existing fields of the LinkedSet class. The Set interface is generic and makes no restrictions on the type that it can contain. The LinkedSet class is also generic, but it does make a restriction on the type variableany type bound by a client to T must be a class that implements the Comparable interface for that type. Thus, there is a natural order on the values stored in an LinkedSet, but not (necessarily) on those stored in a Set. This is an important distinction, so pause here long enough to make sure you understand this point. The following sections describe each method to be implemented, organized according to the methods appearing in the Set interface and those specific to the LinkedSet class.

Each method from the Set interface that you must implement in the LinkedSet class is described below and in comments in the provided source code. You must read both. Note that in addition to correctness, your code will also be graded on the stated performance requirements.

add(T element) The add method ensures that this set contains the specified element. Neither duplicates nor null values are allowed. The method returns true if this set was modified (i.e., the element was added) and false otherwise. Note that the constraint on the generic type parameter T of the LinkedSet class ensures that there is a natural order on the values stored in an LinkedSet. You must maintain the internal doubly-linked list in ascending natural order at all times. The time complexity of the add method must be O(N), where N is the number of elements in the set.

remove(T element) The remove method ensures that this set does not contain the specified element. The method returns true if this set was modified (i.e., an existing element was removed) and false otherwise. The remove method must maintain the ascending natural order of the doubly-linked list. The time complexity of the remove method must be O(N), where N is the number of elements in the set.

size() The size method returns the number of elements in this set. This method is provided for you and must not be changed. The time complexity of the size method is O(1).

isEmpty() The isEmpty method returns true if there are no elements in this set and false otherwise. This method is provided for you and must not be changed. The time complexity of the isEmpty method is O(1). Any set for which isEmpty() returns true is considered the empty set () for purposes of union, intersection, and complement described below.

equals(Set s) Two sets are equal if and only if they contain exactly the same elements, regardless of order. If A = {1, 2, 3}, B = {3, 1, 2}, and C = {1, 2, 3, 4}, then A = B and A 6= C. The equals method returns true if this set contains exactly the same elements as the parameter set, and false otherwise. The time complexity of the equals method must be O(N2 ) where N is the size of each set.

union(Set s) The union of set A with set B, denoted A B, is defined as {x | x A or x B}. Note that A B = B A and A = A. The union method returns a set that is the union of this set and the parameter set; that is, the set that contains the elements of both this set and the parameter set. The result set must be in ascending natural order. The time complexity of the union method must be O(N M) where N is the size of this set and M is the size of the parameter set.

intersection(Set s) The intersection of set A with set B, denoted A B, is defined as {x | x A and x B}. Note that A B = B A and A = . The intersection method returns a set that is the intersection of this set and the parameter set; that is, the set that contains the elements of this set that are also in the parameter set. The result set must be in ascending natural order. The time complexity of the intersection method must be O(N M) where N is the size of this set and M is the size of the parameter set.

complement(Set s) The relative complement of set B with respect to set A, denoted A\B, is defined as {x | x A and x / B}. Note that A\B 6= B\A, A\ = A, and \A = . The complement method returns a set that is the relative complement of the parameter set with respect to this set; that is, the set that contains the elements of this set that are not in the parameter set. The result set must be in ascending natural order. The time complexity of the complement method must be O(N M) where N is the size of this set and M is the size of the parameter set.

iterator() The iterator method returns an Iterator over the elements in this set. Although the interface specifies that no particular order can be assume (by a client), the LinkedSet implementation must ensure that the resulting iterator returns the elements in ascending natural order. The associated performance constraints are as follows: iterator(): O(1); hasNext(): O(1); next(): O(1); required space: O(1).

public class LinkedSet> implements Set

{

//////////////////////////////////////////////////////////

// Do not change the following three fields in any way. //

//////////////////////////////////////////////////////////

/** References to the first and last node of the list. */

Node front;

Node rear;

/** The number of nodes in the list. */

int size;

/////////////////////////////////////////////////////////

// Do not change the following constructor in any way. //

/////////////////////////////////////////////////////////

/**

* Instantiates an empty LinkedSet.

*/

public LinkedSet() {

front = null;

rear = null;

size = 0;

}

//////////////////////////////////////////////////

// Public interface and class-specific methods. //

//////////////////////////////////////////////////

///////////////////////////////////////

// DO NOT CHANGE THE TOSTRING METHOD //

///////////////////////////////////////

/**

* Return a string representation of this LinkedSet.

*

* @return a string representation of this LinkedSet

*/

@Override

public String toString() {

if (isEmpty()) {

return "[]";

}

StringBuilder result = new StringBuilder();

result.append("[");

for (T element : this) {

result.append(element + ", ");

}

result.delete(result.length() - 2, result.length());

result.append("]");

return result.toString();

}

///////////////////////////////////

// DO NOT CHANGE THE SIZE METHOD //

///////////////////////////////////

/**

* Returns the current size of this collection.

*

* @return the number of elements in this collection.

*/

public int size() {

return size;

}

//////////////////////////////////////

// DO NOT CHANGE THE ISEMPTY METHOD //

//////////////////////////////////////

/**

* Tests to see if this collection is empty.

*

* @return true if this collection contains no elements, false

otherwise.

*/

public boolean isEmpty() {

return (size == 0);

}

/**

* Ensures the collection contains the specified element. Neither

duplicate

* nor null values are allowed. This method ensures that the elements

in the

* linked list are maintained in ascending natural order.

*

* @param element The element whose presence is to be ensured.

* @return true if collection is changed, false otherwise.

*/

public boolean add(T element) {

return false;

}

/**

* Ensures the collection does not contain the specified element.

* If the specified element is present, this method removes it

* from the collection. This method, consistent with add, ensures

* that the elements in the linked lists are maintained in ascending

* natural order.

*

* @param element The element to be removed.

* @return true if collection is changed, false otherwise.

*/

public boolean remove(T element) {

return false;

}

/**

* Searches for specified element in this collection.

*

* @param element The element whose presence in this collection is

to be tested.

* @return true if this collection contains the specified element,

false otherwise.

*/

public boolean contains(T element) {

return false;

}

/**

* Tests for equality between this set and the parameter set.

* Returns true if this set contains exactly the same elements

* as the parameter set, regardless of order.

*

* @return true if this set contains exactly the same elements as

* the parameter set, false otherwise

*/

public boolean equals(Set s) {

return false;

}

/**

* Tests for equality between this set and the parameter set.

* Returns true if this set contains exactly the same elements

* as the parameter set, regardless of order.

*

* @return true if this set contains exactly the same elements as

* the parameter set, false otherwise

*/

public boolean equals(LinkedSet s) {

return false;

}

/**

* Returns a set that is the union of this set and the parameter set.

*

* @return a set that contains all the elements of this set and the

parameter set

*/

public Set union(Set s){

return null;

}

/**

* Returns a set that is the union of this set and the parameter set.

*

* @return a set that contains all the elements of this set and the

parameter set

*/

public Set union(LinkedSet s){

return null;

}

/**

* Returns a set that is the intersection of this set and the

parameter set.

*

* @return a set that contains elements that are in both this set

and the parameter set

*/

public Set intersection(Set s) {

return null;

}

/**

* Returns a set that is the intersection of this set and

* the parameter set.

*

* @return a set that contains elements that are in both

* this set and the parameter set

*/

public Set intersection(LinkedSet s) {

return null;

}

/**

* Returns a set that is the complement of this set and the parameter

set.

*

* @return a set that contains elements that are in this set but not

the parameter set

*/

public Set complement(Set s) {

return null;

}

/**

* Returns a set that is the complement of this set and

* the parameter set.

*

* @return a set that contains elements that are in this

* set but not the parameter set

*/

public Set complement(LinkedSet s) {

return null;

}

/**

* Returns an iterator over the elements in this LinkedSet.

* Elements are returned in ascending natural order.

*

* @return an iterator over the elements in this LinkedSet

*/

public Iterator iterator() {

return null;

}