#include "set.h"

/*
Craig Mustard's Set Class.
Notes:
- When given an array to seed the Set with, we'll first try to create an array of twice that size, to avoid resizing later.
- in many functions, such as operator<=, operator-=, I'm using an algoritm that takes advantage of the sorted property of both sets.
	- given that: a[0] < a[1] < ... < a[n], b[0] < b[1] < ... < b[k]
	- if a[i] is greater than b[i], then we can assume that everything in b[0...i] is less than a[i].
	- if a[i] is less than b[i], then we can assume that everything in a[0...i] is less then b[i].
	- Using these two assumptions, we can compare the contents of two sets in O(n) time.
*/

long Set::findElement(const long x) const{
	//findElement will do a binary search for a given element in the set.
	
	long start = 0, end = numElements-1;
	long mid = (end)/2;
	
	//check edge cases first.
	if(set[0] == x) return 0;
	if(set[end] == x) return end;
	
	while(mid != start && mid != end){
		if(set[mid] == x){
			return mid;
		} else if(set[mid] > x){
			end = mid;
			mid = start + (end-start) / 2;
		} else if(set[mid] < x){
			start = mid;
			mid = start + (end-start) / 2;
		}
	}
	
	return -1;
}

void Set::increaseArray(){
	//resize the array to 2 times it's original size.
	arraySize = arraySize*2;
	long *newSet = new long[arraySize];
	
	for(long i = 0; i < numElements; i++){
		newSet[i] = set[i];
	}
	
	delete [] set; //delete the old set.
	set = newSet;
}

Set::Set(){
	//default constructor, use the initialArraySize constant as the size of the default array
	set = new long[Set::initialArraySize];
	arraySize = Set::initialArraySize;
	numElements = 0;
}

Set::Set(long a, long b, long c){
	// initializes the set to the set
	// containing the elements a, a+c, a+2*c, a+3*c, ...
	// which are smaller or equal to b
	
	arraySize = ((b-a)/c + 1)*2;
	numElements = (b-a)/c + 1;
	
	try {
		set = new long[arraySize];
	}catch( bad_alloc z) {
		//oops, multiplying by two was probably too much, lets stick to the original size.
		arraySize = ((b-a)/c + 1);
		set = new long[arraySize];
    	}

	set = new long[arraySize];
	
	for(long i=0; (a + i*c) <= b; i++){
		//we can simply insert, since these are being generated in 'sorted order'
		this->set[i] = a + i*c;
	}
}

Set::Set(long list[], long size){
	// initializes the set to elements
	// contained in the array list; the size should be size of the array
	// (note: you cannot assume that elements in list are all distinct)
	arraySize = size * 2;
	try {
		set = new long[arraySize];
	}catch( bad_alloc a) {
		//oops, multiplying by two was probably too much, lets stick to the original size.
		arraySize = size;
		set = new long[arraySize];
    	}
	
	//use the append operator so that we can check for duplicates upon each insertion.
	for(long i=0; i < size; i++){
		*this << list[i];
	}
}

Set::Set(const Set &s){
	arraySize = s.arraySize*2;
	
	try {
		set = new long[arraySize];
	}catch( bad_alloc a) {
		//oops, multiplying by two was probably too much, lets stick to the original size.
		arraySize = s.arraySize;
		set = new long[arraySize];
    	}

	numElements = s.numElements;
	
	for(long i = 0; i < s.numElements; i++){
		set[i] = s.set[i];
	}
}

Set::~Set(){
	delete [] set;
}

Set & Set::operator=(const Set &s){
	// the assignment operator
	if(this == &s) return *this;

	delete [] set; //delete the old set.
	arraySize = s.arraySize; //used to be s.arraySize*2
	
	try {
		set = new long[arraySize];
	}catch( bad_alloc a) {
		//oops, multiplying by two was probably too much, lets stick to the original size.
		arraySize = s.arraySize;
		set = new long[arraySize];
    	}

	numElements = s.numElements;
	
	for(long i = 0; i < s.numElements; i++){
		set[i] = s.set[i];
	}

	return *this;
}

Set::operator long() const{
	// return the number of elements
	return numElements;
}

bool Set::operator()(long x) const{
	// return true if x is an element of the set}
	// basic search for now.
	if(findElement(x) != -1) return true;
	return false;
}

bool Set::operator==(const Set &s) const{
	// return true if s contains the same elements
	// if s contains the same elements, they should be in the same order.
	if(numElements != s.numElements) return false;
	
	for(long i=0; i<s.numElements; i++){
		if(set[i] != s.set[i]) return false;
	}
	
	return true;
}

bool Set::operator<=(const Set &s) const{
	// return true if this object is subset of s
	// if s is a subset, the elements may or may not be in the same order, so we need to search for each one.
	
	if(numElements > s.numElements) return false; //couldn't possibly be a subset
	
	//old algorithm
	/*for(long i=0; i<numElements; i++){
		if(!s(set[i])){ //if s does not contain this element.
			return false;
		}
	}*/
	
	//see explanation at the top of this file for a reason as to why this algorithm works.
	int a=0, b=0;
	while(a < numElements && b < s.numElements){
		if(set[a] < s.set[b]){
			//means set[a] isn't contained in set[b], so we're done.
			return false;
		} else if(set[a] > s.set[b]){
			a++;
		} else if(set[a] == s.set[b]){
			a++;
			b++;
		}
		
	}
	
	return true;
}

bool Set::operator>=(const Set &s) const{
	// return true if s is subset of this object
	if(numElements < s.numElements) return false; //couldn't possibly be a subset
	
	//old algorithm.
	/* for(long i=0; i<s.numElements; i++){
		if(! operator()(s.set[i]) ){ //if this does not contain this element.
			return false;
		}
	} */
	
	//see explanation at the top of this file for a reason as to why this algorithm works.
	int a=0, b=0;
	while(a < numElements && b < s.numElements){
		if(set[a] > s.set[b]){
			//skipping b;
			return false;
			b++;
		} else if(set[a] < s.set[b]){
			a++;
		} else if(set[a] == s.set[b]){
			a++;
			b++;
		}
		
	}
	
	return true;
}

Set & Set::operator<<(long x){
	// add x to the set
	if(numElements+1 > arraySize) increaseArray(); //resize array
	
	if(numElements == 0){
		set[0] = x;
		numElements++;
		return *this;
	}
	
	int insertionPoint = -1;

	//find smallest number that is greater than x using a binary search.
	//check boundary cases first before we search
	long start = 0, end = numElements-1;
	long mid = end/2;
	if(x < set[start]){
		insertionPoint = start;
	} else if (x > set[end]){
		insertionPoint = end+1;
	} else { 
		while(mid != start || mid != end){
			if(set[mid] == x || set[mid+1] == x){
				//element already in array, skip insertion.
				return *this;
			} else if (x > set[mid] && x < set[mid+1]){
				break; //will set insertionPoint after loop.
			} else if (x < set[mid]){
				end = mid;
				mid = mid/2;
			} else if (x > set[mid]){
				start = mid;
				mid = start + (end-start)/2;
			}
		}
		insertionPoint = mid+1;
	}
	
	//move every element forward one, do this backwards to avoid temporary variables.
	for(int i=numElements; i>insertionPoint; i--){
		set[i] = set[i-1];
	}
	set[insertionPoint] = x;
	numElements++;
	
	return *this;
}

Set & Set::operator>>(long x){
	// remove x from the set
	// (if x is not in the set, do nothing
	
	long removePoint = findElement(x);
	if(removePoint == -1) return *this;
	
	for(long i=removePoint; i<numElements; i++){
		set[i] = set[i+1];
	}
	set[numElements-1] = 0;
	numElements--;
	
	return *this;
}

Set Set::operator+(const Set &s) const{
	// return the union with the set s
	Set newSet(*this); //clone this set.
	
	for(long i=0; i<s.numElements; i++){
		newSet << s.set[i];
	}
	
	return newSet;
}

Set & Set::operator+=(const Set &s){
	// add all elements of the set s
	for(long i=0; i<s.numElements; i++){
		*this << s.set[i];
	}
	
	return *this;
}

Set Set::operator*(const Set &s) const{
	// return the intersection with the set s
	Set newSet;
	
	for(long i=0; i<s.numElements; i++){
		if(findElement(s.set[i]) != -1){
			//found in both sets.
			newSet << s.set[i];
		}
	}

	return newSet;
}

Set & Set::operator*=(const Set &s){
	// keep only those elements which are also in s
	Set newSet;
	
	//See explanation at the top of this file for why this algorithm works.
	long a=0, b=0;
	while(a < numElements && b < s.numElements){
		if(set[a] == s.set[b]){
			newSet << set[a];
			a++;
			b++;
		} else if(set[a] > s.set[b]){
			b++;
		} else if(set[a] < s.set[b]){
			a++;
		}
	}
	*this = newSet;
	return *this;
}

Set Set::operator-(const Set &s) const{
	// return the set difference with the set s
	Set newSet;
	
	long a=0, b=0;
	while(a < numElements && b < s.numElements){
		if(set[a] == s.set[b]){
			a++;
			b++;
		} else if(set[a] > s.set[b]){
			//only in b
			//newSet << s.set[b];
			b++;
		} else if(set[a] < s.set[b]){
			//only in a
			newSet << set[a];
			a++;
		}
	}
	
	while(a < numElements){
		newSet << set[a];
		a++;
	}
	
	return newSet;
}

Set & Set::operator-=(const Set &s){
	// remove those elements which are also in s
	//long *toRemove = new long[arraySize];
	long *newSet = new long[arraySize];
	
	//See explanation at the top of this file for why this algorithm works.
	long a=0, b=0, deletedElements=0, newSetI=0;
	while(a < numElements && b < s.numElements){
		if(set[a] == s.set[b]){
			//skip this element
			a++;
			b++;
			deletedElements++;
		} else if(set[a] > s.set[b]){
			b++;
		} else if(set[a] < s.set[b]){
			//a is not in s.set, add it to the new set.
			newSet[newSetI] = set[a];
			newSetI++;
			a++;
		}
	}
	
	//finish copying elements that we missed in the above loop
	for(long i=a; i<numElements; i++){
		newSet[newSetI] = set[i];
		newSetI++;
	}
	
	delete [] set;
	set = newSet;
	numElements -= deletedElements;
	return *this;
}

ostream & operator<<(ostream &os, const Set &s){
	os << "{";
	for(long i=0; i<s.numElements; i++){
		os << s.set[i];
		if(i < s.numElements-1) os << ",";
	}
	os << "}";

	return os;
}