#include "SetL.h"

Set::Set( ): first( NULL ), theSize( 0 )
{
}


Set::Set( const Set & rhs ) : first( NULL ), theSize( 0 )
{
    *this = rhs;
}


Set::~Set( )
{
    clear( );
}


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


int Set::size( ) const
{ return theSize; }

bool Set::isEmpty( ) const
{ return size( ) == 0; }

void Set::clear( )
{
    while( !isEmpty( ) )
        remove( first->data );
}


vector<string> Set::toVector( ) const
{
    vector<string> result;

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

    return result;
}

bool Set::operator==( const Set & rhs ) const
{
    if( size( ) != rhs.size( ) )
        return false;

    for( Node *p = first, *q = rhs.first; p != NULL; p = p->next, q = q->next )
         if( p->data != q->data )
             return false;

    return true;
}

bool Set::add( const string & x )
{
    if( first == NULL || first->data > x )
    {
        first = new Node( x, first );
        theSize++;
        return true;
    }

    Node *p;
    for( p = first; p->next != NULL && p->next->data <= x; p = p->next )
    {
        if( p->next->data == x )
            return false;
    }

    // Invariant p->data < x && p->next->data > x 
    p->next = new Node( x, p->next );
    theSize++;
    return true;
}


bool Set::remove( const string & x )
{
    if( isEmpty( ) )
        return false;

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

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

    return false;
}


const Set & Set::operator+= ( const string & rhs )
{
    add( rhs );
    return *this;
}

const Set & Set::operator-= ( const string & rhs )
{
    remove( rhs );
    return *this;
}

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