public void testDifference() {
//Create two sets
LinkedSet<Integer> mySet = new LinkedSet<Integer>();
LinkedSet<Integer> yourSet = new LinkedSet<Integer>();
//Ensure the sets are empty
assertTrue(mySet.isEmpty());
assertTrue(yourSet.isEmpty());
//Add Integers 1-4 into mySet
for (int i=1; i<5; i++)
mySet.add(new Integer(i));
//Add Integers 3-8 into yourSet
for (int i=3; i<9; i++)
yourSet.add(new Integer(i));
if (ramble) { //If we want to see what's inside...
System.out.println("(DiffTest) My Set: "+mySet.toString());
System.out.println("(DiffTest) Your Set: "+yourSet.toString());
}
//THIS Line throws the error:
SetADT<Integer> diff = mySet.difference(yourSet);
//Type mismatch: cannot convert from SetADT<Integer> to SetADT<Integer>
if (ramble) System.out.println("Difference: "+diff.toString());
//diff contains {1, 2}
assertTrue(diff.contains(new Integer(1)));
assertTrue(diff.contains(new Integer(2)));
//diff does not contain 3
assertTrue(!diff.contains(new Integer(3)));
}
//********************************************************************
// LinkedSet.java Authors: Lewis/Chase
//
// Represents a linked implementation of a set.
//********************************************************************
package Linked;
import java.util.*;
public class LinkedSet<T> implements SetADT<T>, Iterable<T> {
private static Random rand = new Random();
private int count; // the current number of elements in the set
private LinearNode<T> contents;
/***************************************************************************
* Creates an empty set.
**************************************************************************/
public LinkedSet() {
count = 0;
contents = null;
}
/***************************************************************************
* Adds the specified element to this set if it is not already present.
**************************************************************************/
public void add(T element) {
if (!(contains(element))) {
LinearNode<T> node = new LinearNode<T>(element);
node.setNext(contents);
contents = node;
count++;
}
}
/*
* Adds the contents of the parameter to this set.
* @param set The set to add to the current set
*/
public void addAll(SetADT<T> set) {
Iterator<T> scan = set.iterator();
while (scan.hasNext())
add(scan.next());
}
/***************************************************************************
* Removes and returns a random element from this set. Throws an
* EmptySetException if the set contains no elements.
**************************************************************************/
public T removeRandom() throws EmptySetException {
LinearNode<T> previous, current;
T result = null;
if (isEmpty())
throw new EmptySetException();
int choice = rand.nextInt(count) + 1;
if (choice == 1) {
result = contents.getElement();
contents = contents.getNext();
} else {
previous = contents;
for (int skip = 2; skip < choice; skip++)
previous = previous.getNext();
current = previous.getNext();
result = current.getElement();
previous.setNext(current.getNext());
}
count--;
return result;
}
/***************************************************************************
* Removes and returns the specified element from this set. Throws an
* EmptySetException if the set is empty and a NoSuchElemetnException if the
* target is not in the set.
**************************************************************************/
public T remove(T target) throws EmptySetException, NoSuchElementException {
boolean found = false;
LinearNode<T> previous, current;
T result = null;
if (isEmpty())
throw new EmptySetException();
if (contents.getElement().equals(target)) {
result = contents.getElement();
contents = contents.getNext();
} else {
previous = contents;
current = contents.getNext();
for (int look = 0; look < count && !found; look++)
if (current.getElement().equals(target))
found = true;
else {
previous = current;
current = current.getNext();
}
if (!found)
throw new NoSuchElementException();
result = current.getElement();
previous.setNext(current.getNext());
}
count--;
return result;
}
/*
* Returns a new set that is the union of this set and the parameter.
* @param set The Secondary set
* @return A LinkedSet containing both the current and parameter sets
*/
public SetADT<T> union(SetADT<T> set) {
if (set.isEmpty() || isEmpty())
throw new EmptySetException();
LinkedSet<T> both = new LinkedSet<T>();
both.addAll(this);
both.addAll(set);
return both;
}
/*
* Returns true if this set contains the specified target element.
* @param target The element being searched for
* @return True if the set contains the element, false otherwise
*/
public boolean contains(T target) {
if (isEmpty())
return false;
Iterator<T> scan = iterator();
while (scan.hasNext())
if (scan.next().equals(target))
return true;
return false;
}
/*
* Returns true if this set contains exactly the same elements as the
* parameter. @param set Comparison Set @return True is the sets are the
* same, false otherwise
*/
public boolean equals(SetADT<T> set) {
if (isEmpty() || set.isEmpty())
throw new EmptySetException();
if (set.size() != size())
return false;
Iterator<T> scan = iterator();
while (scan.hasNext())
if (!set.contains(scan.next()))
return false;
return true;
}
/*
* Returns true if this set is empty and false otherwise. @return True if
* the set is empty, false otherwise.
*/
public boolean isEmpty() {
return (contents == null);
}
/*
* Returns the number of elements currently in this set. @return The number
* of elements in the set
*/
public int size() {
if (isEmpty())
throw new EmptySetException();
int count = 1;
LinearNode<T> temp = contents;
while (temp.getNext() != null) {
count++;
temp = temp.getNext();
}
return count;
}
/*
* Returns an iterator for the elements currently in this set.
*/
public Iterator<T> iterator() {
return new LinkedIterator<T>(contents, count);
}
/*
* Returns a string representation of this set. @return The string
* representation of the set
*/
public String toString() {
Iterator<T> scan = iterator();
String result = "";
while (scan.hasNext())
result += scan.next().toString() + " ";
return result;
}
/*
* Returns a Linked Set containing the elements of the current set that do
* not exist in the parameter set.
*
* @param set Comparison Set @return The Linked set of the difference
* between the sets
*/
public SetADT<T> difference(SetADT<T> set) throws EmptySetException {
if (set.isEmpty() || this.isEmpty())
throw new EmptySetException();
LinkedSet<T> diff = new LinkedSet<T>();
T obj;
Iterator<T> scan = this.iterator();
while (scan.hasNext()) {
obj = scan.next();
if (!set.contains(obj))
diff.add(obj);
}
return diff;
}
/*
* Returns a Linked Set that contains the elements found in both the current
* set and parameter set
*
* @param set Comparison set @return A Linked Set containing elements found
* in both sets
*/
public SetADT<T> intersection(SetADT<T> set) throws EmptySetException {
if (set.isEmpty() || this.isEmpty())
throw new EmptySetException();
T obj;
LinkedSet<T> comb = new LinkedSet<T>();
Iterator<T> scan = this.iterator();
while (scan.hasNext()) {
obj = scan.next();
if (set.contains(obj))
comb.add(obj);
}
return comb;
}
/*
* Counts the number of a certain element in the set @param target The
* object being counted @return The number of times the element appears in
* the set
*/
public int count(T target) throws EmptySetException {
if (this.isEmpty())
throw new EmptySetException();
int cou = 0;
Iterator<T> scan = this.iterator();
while (scan.hasNext())
if (scan.next().equals(target))
cou++;
return cou;
}
}