import java.util.ArrayList;
/**
* Set.java
*
* 1) Complete the following implementation of a set class.
* Some of the methods will be very easy (like 1 line of code),
* and others will require a little thought.
*
* 2) Complete all of the javadoc comments and remove all unecessary
* comments (like these ones) and add your name to the files.
*
* 3) Complete the implementation of the testSet class.
*
* @author Charles Cusack, Fall 2008
* Modified, Spring 2009.
*/
// Notice the "<T>" in this class definition. This is making this
// a generic class. Thus, when you instantiate it, you will specify
// what type of object it will store. For example, if you want to
// get a set to store Strings, you will use:
//
// Set mySet = new Set<String>();
//
// Throughout the class, the type "T" is understood to be whatever
// type the user specifies when they instantiate the class.
// If it helps, just imagine "T" is "String"
//
public class Set<T> {
private ArrayList<T> elements;
/**
* Create an empty set.
* (This one is done)
*/
public Set()
{
elements = new ArrayList<T>();
}
/**
* Create a set with elements from the given ArrayList.
* Note: We cannot assume the ArrayList is a set!
* (This method is done)
*/
public Set(ArrayList<T> items)
{
elements = new ArrayList<T>();
for(T item: items)
{
// We use the insert method instead of using
// elements.add because there may be repeated
// elements, and the insert method will deal
// with this.
insert(item);
}
}
/**
* Create a set with elements from the given array.
*/
public Set(T []items)
{
}
/**
* Return true if item is in the set, false otherwise.
*/
public boolean contains(T item)
{
return false; // just so it compiles.
}
/**
* Insert element newItem into the set if it is not already
* in the set. Otherwise, do nothing.
* Return true if successful, false otherwise.
*
* Remember: newItem might already be on the list!
*/
public boolean insert(T newItem)
{
return false;
}
/**
* Remove item theItem from the set, if it is in the set.
* Return true if the element was found and removed, false otherwise.
* (This one is done)
*/
public boolean remove(T theItem)
{
return elements.remove(theItem);
}
/**
* Remove all elements from the set.
*/
public void removeAll()
{
}
/**
* Return the number of items on the set.
* (This one is done)
*/
public int getSize()
{
return elements.size();
}
/**
* Return an array containing the elements in the set.
* (This one is done)
*/
public Object[] getElements()
{
return elements.toArray();
}
/**
* The typical toString method.
* (This one is done.)
*/
public String toString()
{
// A cool class--the StringBuffer allows you to manipulate
// string more efficiently than using the String object.
// Whenever you are appending stuff to strings, you should
// use StringBuffer instead of Strings. There are cases where
// using Strings instead of StringBuffers cause a method that
// would normally take 10 seconds to execute to take 10 minutes
// or more.
StringBuffer buff = new StringBuffer("{");
for(T item: elements)
{
buff.append(item+", ");
}
buff.delete(buff.length() - 2 , buff.length());
buff.append("}");
return buff.toString();
}
/**
* Determines whether this Set is equal to another one
* Two sets are equal if they have the same size, and they both have all of
* the same elements.
* One way to determine that they have the same elements is to iterate over
* every element of this set, and check that it is contained in the other
* set. If they have the same size, and
*
* There are actually several other ways of implementing this method, but
* the advantage of this way is that it does not depend on any of the other
* methods of the set class, which makes testing better--for instance, I can
* implement this by using union, but then if I use the equals method in the
* test of whether or not union works, then we might have a problem.
*
* @param other the object we want to compare to this one.
* @return true if other is a set and this set should be considered equal to other,
* false otherwise
*/
public boolean equals(Set<T> other)
{
if(this.getSize() != other.getSize()) {
return false;
}
for(T item : this.elements) {
if(!other.contains(item)) {
return false;
}
}
return true;
}
//-------------------------------------------------------------------
/**
* Return the union of this set and set B
* (This one is done.)
*/
public Set<T> union(Set<T> B)
{
// First make a copy of the current set. If we do not do
// this, we will modify the current set, and we do not want
// to do that.
Set<T> toReturn = new Set<T>(elements);
// Now iterate over each element of the set B
for(T item: B.elements)
{
// If the item is not already in this set, add it.
// We have to check so we do not get duplicates.
if(!toReturn.contains(item))
{
toReturn.insert(item);
}
}
return toReturn;
}
/**
* Return the intersection of this set and set B
*
* This one is actually really easy. See the retainAll method
* of the ArrayList class. Don't forget to make a copy of
* your ArrayList before using this method, though.
*
* You can also do this the hard way by iterating over elements
* in this list, and seeing if each is in B, and if so, adding
* to a new Set object, then returning that object.
*/
public Set<T> intersect(Set<T> B)
{
return null; // Just so it compiles.
}
/**
* Return the set difference between this set and B.
* That is, all elements in this set that are not in B.
*
* This can be implemented very similarly to the union method.
*/
public Set<T> setDifference(Set<T> B)
{
return null; // Just so it compiles.
}
/**
* Return true if B is a subset of this subset, false otherwise.
*
* Here are two suggestions for how you might implement this:
* 1) Iterate over every element of B, and make sure every element
* is also in this set. If so, return true. If you find that
* an element is not in this set, immediately return false.
* 2) Compute the union of this set and B. If the union has
* more elements than this set, then B isn't a subset.
*/
public boolean isSubset(Set<T> B)
{
return false; // just so it compiles.
}
/**
* Return true if B is a proper subset of this subset, false otherwise.
* (A proper subset is a subset that is not equal to the other set--in
* other words, every element of B is in this set, but B does not contain
* every element that this set contains.)
* You can use isSubset to determine if B is a subset of this set, and
* then make sure it has less elements than this set.
*/
public boolean isProperSubset(Set<T> B)
{
return false; // just so it compiles.
}
/**
* Return true if this set and B are disjoint, false otherwise.
* Two sets are disjoint if they have no elements in common.
* This can be implemented in a way similar to the first suggestion
* in isSubset above.
*/
public boolean areDisjoint(Set<T> B)
{
return false; // just so it compiles.
}
}