// © Copyright 1995. Joseph Bergin. All rights reserved.

#ifndef __Set__
#define __Set__

#include <iostream.h>
#include <fstream.h>
#include "Array.h"
#include "Boolean.h"

// Sets are implemented here as dynamic arrays.  They start with a
// small number of slots and they grow as needed.  They don't shrink,
// however (potential improvement). 

//template <class E> class SetIterator;

template <class E>
class Set
{	public:
		Set()
		:	_elements(ArrayDefaultLength),
			 _cardinality(0),
		 	_size(ArrayDefaultLength)
		{
		}
// not needed
/*		
		Set(const Set<E> & s)
		:	_elements(s._cardinality + 10),
			 _cardinality(0),
		 	_size(s._cardinality + 10)
		{	for(int i = 0; i< s._cardinality; i++)
				insert(s._elements[i]);
		}
*/
		Set(const Array<E> &A) // Initialize with elements of Array A
		:	_elements(A.length()),
			_cardinality(0),
			_size(A.length())
		{	unsigned int i,j;
			for(i = 0; i < A.length(); ++i)
			{	Boolean here = false;
				for(j = 0; j < _cardinality; j++)
					if(_elements[j] == A[i])
					{	here = true;
						break;
					}
				if(!here)
					_elements[_cardinality++] = A[i];
			}
		}
// not needed	
/*	
		~Set()
		{	// Nothing. The dynamic storage is within th Array
		}
//not needed		
		Set & operator = (const Set & s) // set assignment
		{	if(this != &s)
			{	_cardinality = 0;
				for(int i = 0; i< s._cardinality; i++)
					insert(s._elements[i]);
			}
			return *this;
		}
*/		
		void insert(const E& e)
		{	if(!element(e)){
				if(_cardinality >= _size) 
				{	_elements.extendBy(10);
					_size += 10;
				}
				_elements[_cardinality++] = e;
			}
		}
		
		void remove(const E& e)
		{	int i = 0;
			while(i<_cardinality && !(_elements[i] == e)) i++;
			if(i<_cardinality) _elements[i] = _elements[--_cardinality];
		}
				
		int operator < (const Set & s) const// subset
		{	for(int i = 0; i<_cardinality; ++i)
				if(!(s.element(_elements[i]))) return 0;
			return 1;
		}

		int operator == (const Set& s)const // set equality
		{	return (*this < s) && (s < *this);
		}

		Set operator - (const Set& s)const // set difference
		{	Set<E> result;
			for(int i = 0; i<_cardinality; ++i)
				if(!(s.element(_elements[i])))
					result.insert(_elements[i]);
			return result;
		}

		Set operator % (const Set& s)const // Symmetric set difference
		{	return ((*this)-s) + (s-*this);
		} // Note that the precidence of ^ is wrong for this operation.

		Set<E> operator +(const Set<E>& s)const // union
		{	int i = 0;
			Set<E> result(s);
			while (i<_cardinality)
			{	result.insert(_elements[i]);
				i +=1;
			}
			return result;
		}
		
		Set operator *(const  Set<E>& s) // intersection
		{	Set<E> result;
			for(int i = 0; i < _cardinality; i++) 
				{	E e = _elements[i];
					if(s.element(e)) result.insert(e);
				}
			return result;		
		}
		
		Array<E> asArray() const
		{	Array<E> result(_cardinality);
			for(int i=0; i<_cardinality; i++)
				result[i] = _elements[i];
			return result;
		}
		
		int cardinality()const // Number of elements. 
		{	return _cardinality;
		}
		
		Boolean element(const E& e)const
		{	for(int i = 0; i< _cardinality; i++)
				if (_elements[i] == e) return true;
			return false;
		}

/*		void dump(void)const
		{	if(_cardinality==0)cout<<"empty ";
			else
				for(int i = 0; i< _cardinality;i++)
					cout << _elements[i] << ' ';
			cout << endl;
		}
*/
// ************************ nested class Iterator ******************************
	//template <class E>
	class Iterator
	{	public:
			Iterator(Set<E> &S)
			:	_set(S),
				_here(0),
				_done(true)
			{
			}
	
			E current()const
			{	if(_done || _here >= _set._cardinality) userERROR("Set Iterator limit check.");
				return _set._elements[_here];
			}
			
			void advance()
			{	if(_done) userERROR("Illegal Iterator advance.");
				if(_here < _set._cardinality-1) _here++;
				else _done = true;
			}
	
			Set<E>::Iterator & operator++()	// Returns this. 
			{	advance();
				return *this;
			}
			
			Set<E>::Iterator  operator++(int) // Returns a different iterator--pointing to old position.  
			{	if(_done || _here >= _set._cardinality) userERROR("Set Iterator limit check.");
				Set<E>::Iterator temp(*this);
				advance();
				return temp;
			}
	
			E & operator*()
			{	if(_done || _here >= _set._cardinality) userERROR("Set Iterator limit check.");
				return _set._elements[_here];
			}
	
			void reset()
			{	_done = Boolean(_set._cardinality==0);
				_here = 0;
			}
			
			Boolean atEnd() const
			{	return Boolean(_done == true || _here >= _set._cardinality);
			}
			
		private:
			unsigned int _here;
			Set<E> &_set;
			Boolean _done;
		friend class Set<E>;
	};
// ********************* END nested class Iterator *****************************

		Iterator iterator()
		{	return Iterator(*this);
		}

	protected:
		Array<E> _elements;
		unsigned int _cardinality; // Current number of elements.
		unsigned int _size; // Physical size
	friend class Iterator;
};


template <class E>
ostream& operator <<(ostream& os, const Set<E>& s)
	{	Array<E> elements = s.asArray();
		for(int i = 0; i<s.cardinality(); i++)
			os << elements[i]<<' ';
		return os;
	}

#endif