#include "LSet.h"


template <class Object>
Set<Object>::Set( ) : first( NULL ), theSize( 0 )
{
}

template <class Object>
Set<Object>::Set( const Set<Object> & rhs ) : first( NULL ), theSize( 0 )
{
    *this = rhs;
}

template <class Object>
const Set<Object> & Set<Object>::operator= ( const Set<Object> & rhs )
{
    if( this != &rhs )
    {
        makeEmpty( );
        for( Node *p = rhs.first; p != NULL; p = p->next )
            insert( p->data );  // note: order of items will change
    }
    return *this;
}

template <class Object>
Set<Object>::~Set( )
{
    makeEmpty( );
}

template <class Object>
bool Set<Object>::isEmpty( ) const
{
    return getSize( ) == 0;
}


template <class Object>
int Set<Object>::getSize( ) const
{
    return theSize;
}


template <class Object>
void Set<Object>::print( ostream & out ) const
{
    if( isEmpty( ) )
        out << "Empty set";
    else
    {
        out << "{ " << first->data;
        for( Node *p = first->next; p != NULL; p = p->next )
            out << ", " << p->data;
        out << " }";
    }
}

   
template <class Object>
bool Set<Object>::contains( const Object & x ) const
{
    for( Node *p = first; p != NULL; p = p->next )
        if( p->data == x )
            return true;
    return false;
}


template <class Object>
void Set<Object>::insert( const Object & x )
{
    if( !contains( x ) )
    {
        first = new Node( x, first );
        theSize++;
    }
}


template <class Object>
void Set<Object>::remove( const Object & x )
{
    if( isEmpty( ) )
        return;

    if( first->data == x )
    {
        Node *old = first;
        first = first->next;
        delete old;
        theSize--;
        return;
    }

    for( Node *p = first; p->next != NULL; p = p->next )
        if( p->next->data == x )
        {
            Node *old = p->next;
            p->next = p->next->next;
            delete old;
            theSize--;
            return;
        }
}


template <class Object>
void Set<Object>::makeEmpty( )
{
    while( !isEmpty( ) )
        remove( first->data );
}

template <class Object>
Set<Object> Set<Object>::setUnion( const Set<Object> & rhs ) const
{
    Set<Object> result = *this;

    for( Node *p = rhs.first; p != NULL; p = p->next )
        result.insert( p->data );

    return result;
}


template <class Object>
Set<Object> Set<Object>::intersect( const Set<Object> & rhs ) const
{
    Set<Object> result;

    for( Node *p = first; p != NULL; p = p->next )
        if( rhs.contains( p->data ) )
            result.insert( p->data );

    return result;
}