//File Set.h - contains definition of Set class

#ifndef _set_h
#define _set_h

template <class T>
class SetIterator;

template <class T>
class Set {

friend SetIterator<T>;

public:
	Set(int initial_size = 4)						//Taken from last assignment, modified slightly
		: capacity(initial_size), numberOfElements(0){
		elements = new T*[initial_size];
	}
	Set(const Set<T> & s)							//Taken from last assignment, modified slightly
		: numberOfElements(s.numberOfElements), capacity(s.capacity){
		elements = new T*[capacity];
		for(int i=0; i<numberOfElements; i++)
			elements[i] = s.elements[i];
	}
	~Set(void){
		//Delete the memory allocated for the set of elements, not the elements themselves
		delete [] elements;
	}
	Set<T> & operator=(const Set<T> & s){			//Taken from last assignment
		if(this != &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){						//Taken from last assignment
		if(numberOfElements == capacity) {
			capacity *= 2;
            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> & add(const Set<T> & s){
		for(int i=0; i<numberOfElements; i++)
			add(s.elements[i]);
	}
	Set<T> & remove(const T & element){				//Taken from last assignment
		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;
			T** temp = elements;
			elements = new T*[capacity];
			for(int i=0; i<numberOfElements ; i++)
				elements[i] = temp[i];
			delete [] temp;
		}
		return *this;
	}
	Set<T> & clear(){
		for(int i=0; i<numberOfElements; i++)
			remove(*elements[i]);
		numberOfElements = 0;
		return *this;
	}
	bool includes(const T & element) const {		//Taken from last assignment
		for(int i=0; i<numberOfElements; i++){
			if(&element == elements[i])
				return true;
		}
		return false;
	}
	int size()const {								//Taken from last assignment
		return numberOfElements;
	}
	void printOn(ostream & ostr) const {			//Taken from last assignment
		for(int i=0; i<numberOfElements; i++){
			ostr << "\n" << *(elements[i]);
		}
	}

//Iterator Methods
	SetIterator<T> begin() {						//Provided with skeleton code
		return SetIterator<T>(*this);
	}
	SetIterator<T> end() {							//Provided with skeleton code
		return SetIterator<T>(*this, numberOfElements);
	}

private:
	T ** elements; 
	int numberOfElements;							//Number of elements in the set
	int capacity;									//Max number of elements the set can currently hold
};

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

#endif