import java.util.*;

/* This class implements the Clonable, Collection, and Comparable interfaces.
   A StringSet is a Collection of java Strings represented as an array. */
public class StringSet implements Cloneable, Collection, Comparable {
    
    //Fields (notice that all the data is private)
    private int setSize;  // elements in the set
    private final int maxSize;  // maximal number of elements in the set
    private String[] stringSetArray;  // array holding the set

    //Constructors
    public StringSet() {
	stringSetArray = new String[Integer.MAX_VALUE];
	maxSize = Integer.MAX_VALUE;
    }
    
    public StringSet(final int max) {
	stringSetArray = new String[max];
	maxSize = max;
    }
    
    //Collection Inrterface Implemenation
    public int size() {
	return setSize;
    }

    public boolean isEmpty() {
	return setSize == 0;
    }

    public boolean contains(Object elem) {
	String e = (String)elem;
	for (int i=0; i < setSize; ++i) {
	    if (stringSetArray[i].compareTo(e) == 0) {
		return true;
	    }
	}
	return false;
    }

    public boolean containsAll(Collection coll) {
	Iterator it = coll.iterator();
	while (it.hasNext()) {
	    if (contains(it.next()) == false) {
		return false;
	    }
	}
	return true;
    }
    
    public Iterator iterator() {
	/* Note-the code from StringSetIterator.java can be cut and pasted here
	   so that StringSetIterator is a local inner class.  This would limit
	   the scope of that class to this method and eliminate the extra file. */
	return new StringSetIterator(this, stringSetArray);
    }
    
    public Object[] toArray() {
	Object[] resultArray = new String[setSize];
	for (int i=0; i < setSize; ++i) {
	    resultArray[i] = stringSetArray[i];
	}
	return resultArray;
    }

    public Object[] toArray(Object[] dest) {
	if (dest.length <= stringSetArray.length) {
	    for (int i=0; i < size(); ++i) {
		dest[i] = stringSetArray[i];
	    }
	    for (int i=size(); i < dest.length; ++i) {
		dest[i] = null;
	    }
	} else {
	    throw new ArrayStoreException();
	}
	return dest;
    }

    public boolean add (Object elem) {
	if (setSize < maxSize) {
	    stringSetArray[setSize++] = (String)elem;
	    return true;
	} else {
	    return false;
	}
    }

    public boolean addAll(Collection coll) {
	Iterator it = coll.iterator();
	while (it.hasNext()) {
	    add(it.next());
	}
	return false;
    }
	
    public boolean remove(Object elem) {
	String e = (String)elem;
	for (int i=0; i<setSize; ++i) {
	    if (stringSetArray[i].compareTo(e) == 0) {
		stringSetArray[i] = stringSetArray[--setSize];
		stringSetArray[setSize] = null;
		return true;
	    }
	}
	return false;
    }

    public boolean removeAll(Collection coll) {
	Iterator it = coll.iterator();
	while (it.hasNext()) {
	    remove(it.next());
	}
	return false;
    }

    public boolean retainAll(Collection coll) {
	for (int i=0; i < setSize; ++i) {
	    if (coll.contains(stringSetArray[i]) == false) {
		remove(stringSetArray[i]);
	    }
	}
	return false;
    }

    public void clear() {
	for (int i=0; i < maxSize; ++i) {
	    stringSetArray[i] = null;
	}
	setSize = 0;
    }
    
    //Comparable Interface Implementation
    public int compareTo(Object other) {
	StringSet o = (StringSet)other;
	return setSize - o.size();
    }

    //Override Object.clone()
    public Object clone() throws CloneNotSupportedException {
	StringSet c = new StringSet(maxSize);
	for(int i=0; i<setSize; ++i) {
	    c.add(new String(stringSetArray[i]));
	}
	return c;
    }

    //Method to print the StringSet
    public String toString() {
	String output = new String();
	for (int i=0; i < setSize; ++i) {
	    output += (stringSetArray[i] + " ");
	}
	return output;
    }
}