//File Set.h

template <class T>

class Set {

public:
	Set(int initial_size = 4){
		elements = new T*[initial_size];
		capacity = initial_size;
		numberOfElements = 0;
		randomIndex = 0;
		iteratorIndex = 0;
	}
	Set(const Set<T> & s){
		numberOfElements = s.numberOfElements;
		capacity = s.capacity;
		for(int i=0; i<numberOfElements)
			elements[i] = s.elements[i];
	}
	~Set(void){
		//Assume elements will be deleted elsewhere
		//(cannot be deleted here if assignment operator or copy constructor is used)
	}
	Set<T> & operator=(const Set<T> & s){
		numberOfElements = s.numberOfElements;
		capacity = s.capacity;
		for(int i=0; i<numberOfElements; i++)
			elements[i] = s.elements[i];
		return *this;
	}
	Set<T> & add(T & element){
		if(numberOfElements == capacity) {
			capacity *= 2;
            //cout << "\n\tExpanding set capacity to " << capacity;
            T** temp = elements;
            elements = new T*[capacity];
            for(int i=0; i<capacity; i++)
				elements[i] = temp[i];
            delete [] temp;
        }
		elements[numberOfElements++] = &element;
		return *this;
	}
	Set<T> & remove(const T & element){
		int indexOfRemoved = -1;
		for(int i=0; i<numberOfElements; i++){
			if(&element == elements[i])
				indexOfRemoved = i;
		}
		if(indexOfRemoved == -1)
			return *this;

		numberOfElements--;

		for(int i = indexOfRemoved; i < numberOfElements; i++){
			elements[i] = elements[i+1];
		}

		if(numberOfElements < capacity/4) {
			capacity/=2;
			//cout << "\n\tDecreasing set capacity to " << capacity;
			T** temp = elements;
			elements = new T*[capacity];
			for(int i=0; i<numberOfElements ; i++)
				elements[i] = temp[i];
			delete [] temp;
		}
		return *this;
	}
	bool includes(const T & element) const {
		for(int i=0; i<numberOfElements; i++){
			if(&element == elements[i])
				return true;
		}
		return false;
	}
	T & someElement() const {
		if(randomIndex >= numberOfElements)
			randomIndex = 0;
		T* anElement = elements[randomIndex];
		randomIndex++;
		return *anElement;
	}

//Iterator Methods
	void reset() const {
		iteratorIndex = 0;
	}
	bool hasMore() const {
		if (iteratorIndex < (numberOfElements - 1))
			return true;
		else
			return false;
	}
	void advance() const {
		iteratorIndex++;
	}
	T & element()const {
		return *elements[iteratorIndex];
	}

	int size()const {
		return numberOfElements;
	}
	void printOn(ostream & ostr) const {
		for(int i=0; i<numberOfElements; i++){
			ostr << "\n" << *(elements[i]);
		}
	}

private:
	T ** elements; 
	int numberOfElements;		//Number of elements in the set
	int capacity;				//Max number of elements the set can currently hold
	mutable int randomIndex;	//Index used for someElement method
	mutable int iteratorIndex;			//Index used for iterator functions

};

template <class T>
ostream & operator<<(ostream & ostr, const Set<T> & s) {
     s.printOn(ostr);
     return ostr;
}