/*
set.cpp 
should contain the definition and implementation of the Set class.  Set should be 
a templated class that can hold any type of data.  It should hold the data in an array 
with a template type (you will also need a way to resize this array if it becomes full).  
It should contain functions for adding an element in sorted order, printing all set elements, 
and finding the union and intersection between this set and another set.  The union and 
intersection functions should return a new Set object (or reference) that is the result of 
the operation.  Set should also have a constructor to initialize space for the array, and 
a destructor to release the space.

You should model the Set class after the templated Vector class we wrote in lab.  Also, 
recall from lab that malloc and free do not work with templated classes.  Instead, use 
C++-style array allocation.  
For example: 
  int *arr = new int[10];
  delete[] arr;


#include <iostream>
#include <string>
using namespace std;*/

template <class T>
class Set {
    private:
        T *arr;
		int length;
		int pos;
	public:
		Set(void);
		~Set(void);
        void addVal(T);		
        void printVec(void);
		void insertSort(void);
		int getLength(void);
		int getPos(void);
};

template <class T>
Set <T>::Set(void) {
	length = 50;
	pos = 0;
	arr = new T[length];
}

template <class T>
Set <T>::~Set(void) {
	delete [] arr;
}

template <class T>
void Set<T>::addVal(T value) {
	int i;
	T *temp;
	T tval;

	//Resize as needed
	if(pos == length-1){
		temp = new T[length+10];
		for(i=0; i<length-1; i++){
			temp[i]=arr[i];
		}
		arr = temp;
	}

	i = 0;
	while(tval = arr[i++]) {
		if(tval == value) return;
	}	
	arr[pos] = value;
	pos++;

	//sort using insertion sort
	insertSort();
}

template <class T>
void Set<T>::insertSort(void){
	int i, j;
	T index;

	for (i=0; i < pos; i++){
		index = arr[i];
		j = i;
		while ((j > 0) && (arr[j-1] > index)){
			arr[j] = arr[j-1];
			j = j - 1;
		}
		arr[j] = index;
	}
}

template <class T>
void Set<T>::printVec(void){
	int i;
	if(pos < 0){ 
		cout << "There are no values in Vector!" << endl;
	}else{		
		for(i=0; i <= pos; i++){
			cout <<  arr[i] << " ";
		}
		cout << endl;
	}
}


template <class T>
int Set<T> :: getLength(void){return length;}


template <class T>
int Set<T> :: getPos(void){return pos;}