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.
    }
    
}