#include "set.h"





/*quick sort algorithm*/	
void Set::quick_sort(long numbers[], long left, long right)
{
  long pivot, left_hold, right_hold;

  left_hold = left;
  right_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = left_hold;
  right = right_hold;
  if (left < pivot)
    quick_sort(numbers, left, pivot-1);
  if (right > pivot)
    quick_sort(numbers, pivot+1, right);
}


void Set::quickSort(long numbers[], long array_listsize)
{
  quick_sort(numbers, 0, array_listsize - 1);
}


	
	
	/*Default constructor*/
	Set::Set()
	{
          head = new Node; 
	  listsize = 0; 

	}
	/*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*/
	Set::Set(long a, long b, long c )
	{
		long i = 0; 
		long var = a + i * c; 
		listsize = 0; 
		head = new Node; 
		Node *temp = head; 
		while( var <= b)
		{
			temp->value = var; 
			temp->next = new Node; 
			temp = temp->next; 
			var = a + ++i * c;
			++listsize;

		}


	}	

	/*initializes the set to elements
    	 *contained in the array list; the listsize should be listsize of the array
    	 */
	Set::Set(long list[] , long size)
	{
		
		
		/*sorting the list*/
		quickSort(list, size);




		
		/*initialising the list*/
		long i = 0; 
		long j = 0; 
		listsize = 0;
		head = new Node; 
		Node *temp = head;
		if(size > 0){temp->value = list[i++];  ++listsize;}
		while( i < size)
		{
			if(temp->value != list[i])
				{
				
				temp->next = new Node; 
				temp = temp->next; 
				temp->value = list[i]; 
				++listsize;
				}
			++i;
		}
	}


	/*Copy constructor*/
	Set::Set(const Set &s)
	{
	
		long i = 0; 
		listsize = 0;
		head = new Node; 
		Node *temp = head;
		Node *temp2 = s.head; 	
	
		while( i < s.listsize)
		{
		temp->value = temp2->value; 
		temp->next = new Node; 
		temp = temp->next; 
		temp2 = temp2->next; 
		++i;
		++listsize;
		}
		
		
		
		
	}

	/*destructor*/
 	Set::~Set(){ 
   

		long i = 0; 
   		while(i < listsize){
		Node *tmp=head;
  		head=head->next;
 		 delete tmp;
		++i;
		}
   		
	} 
	

	/*the assignment operator*/
	Set  & Set:: operator=(const Set &s)
	{	
		
		Node *x = head->next ; 
		
		/*deleting the old list */	
		long si = 0; 
   		while(si < listsize){
		Node *tmp=head;
  		head=head->next;
 		 delete tmp;
		++si;
		}
		/*deleting the old list complete*/		

	


		head = new Node; 
		Node *temp  = head; 
		Node *temp2 = s.head;
		listsize = s.listsize; 

		long i = 0; 
		/*copying values from set s to this set*/
		while( i < s.listsize)
		{
			temp->value = temp2->value; 
			temp->next = new Node; 
			temp = temp->next;
			if(temp2->next != NULL)
			temp2 = temp2->next;  
			++i;
		
		}
		
		
		return *this;
	} 

	/*returns the number of elements */
	Set:: operator long()const{ return listsize;}
	
	/*returns true if x is an element of the set*/
	bool Set:: operator()(long x) const 
	{ 
	     Node *temp = head; 
	     long i = 0;
	     while( i < listsize)
		{
			if(temp->value == x )
			return true; 
			temp = temp->next;
			i++; 
		}
		return false; 

	} 
	
	/*returns true if s contains the same elements*/
	bool Set:: operator==(const Set &s)const
	{
		
		if(s.listsize != listsize) return false; 
		long i = 0 ; 
		Node *temp = head;
		Node *temp2 = s.head; 	
		while(i < listsize){
			if(temp->value != temp2->value)
				return false; 
		temp = temp->next; 
		temp2 = temp2->next; 
		++i;
		}
		return true; 
				
	

	} 
	/*returns true if this set is a subset of s */
	bool Set::operator <= (const Set &s)const
	{
		
		if(listsize > s.listsize ) return false; 

		long i = 0; 
		long j = 0; 

		Node *temp = head;
		Node *temp2 = s.head; 

		while( i < s.listsize)
		{
			if(temp-> value == temp2->value)	
				{	j++; 
					if(j == listsize)return true; 
					temp = temp->next; 
				}
			temp2 = temp2->next; 
			i++;
		}

	return false; 
	}

	/*returns true if s is a subset of this set*/
	bool Set::operator >= (const Set &s)const
	{

	
		if(listsize < s.listsize ) return false; 

		long i = 0; 
		long j = 0; 

		Node *temp = s.head;
		Node *temp2 = head; 

		while( i < listsize)
		{
			if(temp-> value == temp2->value)	
				{	j++; 
					if(j == s.listsize)return true; 
					temp = temp->next; 
				}
			temp2 = temp2->next; 
			i++;
		}


	return false; 




	}

	Set & Set::operator<<(long x)
	{


	Node *temp = head;
	long i = 0;
	
	/*adding to an empty set*/
	if(listsize == 0)
		{
		head->value = x; 
		listsize++; 
		return *this; 
		}
	/*adding to the beggining of the list*/  
	if(x < head->value)
		{
		Node *temp = new Node; 
		temp->value = x; 
		temp->next = head; 
		head = temp; 
		//head = temp; 
		listsize++; 
		
		return *this; 
		}
	
	 /*adding to the list*/
	while( i < listsize-1)
		{	
		  if(x < temp->next->value )
			{
			  if(x != temp->value){
			  Node *temp2 = temp->next; 
			  temp->next = new Node; 
			  temp->next->value = x; 
			  temp->next->next = temp2;
			  listsize++;
			  }
			  return *this;
				
			}
			temp = temp->next;
			++i;
		}		
		
		  /*adding to the tail of the list*/

		  if(x != temp->value){
		  temp->next = new Node; 
		  temp->next->value = x; 
		  listsize++;
			}
		  return *this; 

	
	}

	Set & Set::operator >> (long x)
	{

	
	if(listsize == 0 ) return *this; 
	Node *temp = head; 
	if(head->value == x)
	{	head = head->next;
		delete temp;
		--listsize; 
		return *this; 
		
	}

	long i = 0; 
	while( i < listsize ) 
	{	
	  if(temp->next == NULL ) return *this; 	
	  
	  if(temp->next->value == x  )
		{
			if(temp->next->next != NULL)
			{

			Node *tem = temp->next;
			
			temp->next = temp->next->next;
			

			delete tem; 
			--listsize;
			return *this;
			}
			else
			{ 
			
			delete temp->next; --listsize;return *this;
			} 
		}
	temp = temp->next;
	i++;
		
	}
	
	return *this;
	}
	

/*returns the union with the set s*/
Set Set::operator + (const Set &s)const
{


	/*temporary variable used to traverse this list*/
	Node *temp1; 
	/*temporary variable used to traverse s list*/
	Node *temp2; 
	/*new set to hold the difference set*/
	Set unionSet = Set(); 
	/*temporary variable polonging to the head of the new list*/
	Node *temp  = unionSet.head; 
	/*temporary variable used to malongain the index of the this list and s list*/
	long i,j;
	i = 0; 
	j = 0; 
	

		/*initialising the temprary variables */
		temp1 = head; 
		temp2 = s.head;

	
	/*traversing the two list in O(listsize + s.listsize) time*/	
	while( i < listsize || j < s.listsize ) 
	{
		
		
		/*traversing list s until the values are equal or greater than the value of the last
		 value traversed of this list*/
		while(temp2->value < temp1->value && j < s.listsize || i >= listsize  && j < s.listsize)
		{
				
				/*adding to the new list the values in list s*/
				temp->value = temp2->value; 
				temp->next = new Node; 
				temp = temp->next; 
				++unionSet.listsize; 
						
		
			if(temp2->next != NULL)
			temp2 = temp2->next; 
			j++;
			
			
		}

		
		/*traversing this list until the values are greater or equal than the last value traversed in 			list s */
		while(temp1->value < temp2->value && i < listsize || j >= s.listsize  && i < listsize)
		{
				
				temp->value = temp1->value; 
				temp->next = new Node; 
				temp = temp->next; 
				++unionSet.listsize; 
					
		
			if(temp1->next != NULL)
			temp1 = temp1->next; 
			i++;	
			
		}
		
		/*adding the equal values in both lists*/
		if(temp1->value == temp2->value  && j < s.listsize && i < listsize)
			{

			 
				temp->value = temp2->value;
				temp->next = new Node; 
				temp = temp->next;
				++unionSet.listsize; 
				
				
				if(temp1->next != NULL)	
					temp1 = temp1->next;  
					
				 if(temp2->next != NULL)	
					temp2 = temp2->next;
				++i; ++j;
				
			}
	
		
	}
		


return unionSet; 	

}
/*adds of the elements of set s */
Set & Set::operator += (const Set &s)
{

	
	Set temp = *this+s; 
	*this = temp; 
	return *this; 
}

/*returns the longersection of this set and set s*/
Set Set::operator * (const Set &s)const
{


	
	/*temporary variable used to traverse this list*/
	Node *temp1; 
	/*temporary variable used to traverse s list*/
	Node *temp2; 
	/*new set to hold the difference set*/
	Set intSet = Set(); 
	/*temporary variable polonging to the head of the new list*/
	Node *temp  = intSet.head; 
	/*temporary variable used to malongain the index of the this list and s list*/
	long i,j;
	i = 0; 
	j = 0; 
	

		/*initialising the temprary variables */
		temp1 = head; 
		temp2 = s.head;


	/*traversing the two list in O(listsize + s.listsize) time*/	
	while( i < listsize || j < s.listsize ) 
	{
	
		/*Skipping the elements that are in Set s but not in this Set*/
		while(temp2->value < temp1->value && j < s.listsize || i >= listsize  && j < s.listsize)
		{			
		
			if(temp2->next != NULL)
			temp2 = temp2->next; 
			j++;
			
		}

		
		/*Skipping the elements that are in this Set but not in Set s*/
		while(temp1->value < temp2->value && i < listsize || j >= s.listsize  && i < listsize)
		{

			if(temp1->next != NULL)
			temp1 = temp1->next; 
			i++;	
		}
		
		/*Adding the longersection*/
		if(temp1->value == temp2->value && j < s.listsize && i < listsize )
			{

			 
				temp->value = temp1->value;
				temp->next = new Node; 
				temp = temp->next;
				++intSet.listsize; 
				
				if(temp1->next != NULL)	
					temp1 = temp1->next;  
					
				 if(temp2->next != NULL)	
					temp2 = temp2->next;
				++i; ++j;
			}
	}
		



return intSet; 	

	



}
/*keeps only those elements that are also in s*/
Set & Set::operator *= (const Set &s)
{

	
	
Set temp = (*this)*s; 

*this = temp; 
return *this; 

}

/*returns the set difference */
Set Set::operator-(const Set &s)const
{
	/*temporary variable used to traverse this list*/
	Node *temp1; 
	/*temporary variable used to traverse s list*/
	Node *temp2; 
	/*new set to hold the difference set*/
	Set diffSet = Set(); 
	/*temporary variable polonging to the head of the new list*/
	Node *temp  = diffSet.head; 
	/*temporary variable used to malongain the index of the this list and s list*/
	long i,j;
	i = 0; 
	j = 0; 
	

		/*initialising the temprary variables */
		temp1 = head; 
		temp2 = s.head;


	/*traversing the two list in O(listsize + s.listsize) time*/	
	while( i < listsize || j < s.listsize ) 
	{
	
		/*Skipping the values in list S but not in this list*/
		while(temp2->value < temp1->value && j < s.listsize || i >= listsize  && j < s.listsize)
		{
				
				/*Skipping the values in list S but not in this list*/
							
		
			if(temp2->next != NULL)
			temp2 = temp2->next; 
			j++;
			
		}

		
		/*adding the elements that are in this list but not in Set s*/
		while(temp1->value < temp2->value && i < listsize || j >= s.listsize  && i < listsize)
		{
				temp->value = temp1->value; 
				temp->next = new Node; 
				temp = temp->next; 
				++diffSet.listsize; 			
		
			if(temp1->next != NULL)
			temp1 = temp1->next; 
			i++;	
		}
		
		/*skipping the equal values in both lists*/
		if(temp1->value == temp2->value && j < s.listsize && i < listsize )
			{
				long loop = 1; 
				
				if(temp1->next != NULL)	
					temp1 = temp1->next;  
					
				 if(temp2->next != NULL)	
					temp2 = temp2->next;
				++i; ++j;
			}
	}
		

return diffSet; 	
}
// remove those elements which are also in s
Set & Set::operator-=(const Set &s)
{

Set temp = *this - s; 

*this = temp; 
return *this;
}	


ostream & operator<<(ostream &os, const Set &s)
{

  //friend ostream & operator<<(ostream &os, const Set &s);
os<<"{";
long i =0; 
Set::Node *temp = s.head; 
while(i < s.listsize)
{
	os<<temp->value; 
	temp = temp->next; 
	++i;
	if(i<s.listsize)
	os<<",";

}
os<<"}";


}