# Sets

A set is an unordered collection of unique elements, typically with support for efficient membership tests

• Like keys of a map, but with no associated value

Sets also provide for traditional mathematical set operations: Union, Intersection, and Subtraction/Difference.

public interface Set<E>{
void remove(E e); //remove element e from set if present
boolean contains(E e); //test if element e is in set
Iterator<E> iterator(); //returns an iterator over the elements
//updates the set to include all elements of set T
// union
//updates the set to include only the elements of the set that are also in T
//intersection
void retainAll(Set<E> T);
//updates the set to remove any elements that are also in T
//difference
void removeAll(Set<E> T);
}


## Generic Merging

Generic merge is a generalised merge of two sorted lists A and B to implement set operations. Uses a template method merge and 3 auxillary methods that describe what happens in each case:

• aIsLess
• Called when the element of A is less than the element of B
• bIsLess
• Called when the element of B is less than the element of A
• bothEqual
• Called when the element of A is equal to the element of B
public static Set<E> merge(Set<E> A, Set<E> B){
Set<E> S = new Set<>();
while (!A.isEmpty() && !B.isEmpty()){
a = A.firstElement();
b = B.firstElement();
if(a < b){
aIsLess(a,S);
A.remove(a);
}
else if (b < a){
bIsLess(b,S);
B.remove(b);
}
else{ //b == a
bothEqual(a,b,S);
A.remove(a);
B.remove(b);
}
while(!A.isEmpty()){
aIsLess(a,S);
A.remove(a);
}
while(!B.isEmpty()){
bIsLess(b,S);
B.remove(b);
}
}
return S;
}

• Any set operation can be implemented using generic merge
• Union
• aIsLess adds a into S
• bIsLess adds b into S
• bothEqual adds a (or b) into S
• Intersection
• aIsLess and bIsLess do nothing
• bothEqual adds a (or b) into S
• Difference
• aIsLess adds a into S
• bIsLess and bothEqual do nothing
• Runs in linear time, , provided the auxillary methods are