#include <iostream>
#include <string>
#include <vector>
#include <sstream>
using namespace std;

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


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


    ~Set( )
    {
        clear( );
    }


    const 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 size( ) const
    { return theSize; }

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

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


    bool 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 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;
    }


    bool 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;
    }


  private:
    struct Node
    {
        string data;
        Node  *next;

        Node( const string & d = "", Node *n = NULL )
          : data( d ), next( n ) { }
    };

    Node *first;
    int   theSize;   // Needed so size() is efficient.

};

const int PRIME1 = 11;
const int PRIME2 = 13;
const int SIZE = 37;

string makeString( int x )
{
    ostringstream os;
    os << x;
    return os.str( );
}

int main( )
{
    Set s1;

    for( int i = PRIME1; i != 0; i =  (i + PRIME1 ) % SIZE )
    {
        s1.add( makeString( i ) );
    }

    cout << boolalpha;
    cout << "Size is: " << s1.size( ) << endl;

    for( int i = 1; i < SIZE; i++ )
        if( !s1.contains( makeString( i ) ) )
            cout << "OOPS #1 " << i << endl;

    if( s1.contains( makeString( SIZE ) )  )
        cout << "OOPS #2 " << s1.size( ) << endl;

    Set s2 = s1;
    Set s3;

    s3 = s1;

    for( int i = PRIME2; i != 0; i = ( i + PRIME2 ) % SIZE )
        s1.remove( makeString( i ) );

    for( int i = 0; i < SIZE; i++ )
        if( s1.contains( makeString( i ) ) )
            cout << "OOPS #3 " << i << endl;

    cout << "s1 Size is: " << s1.size( ) << endl;
    cout << "s2 Size is: " << s2.size( ) << endl;
    cout << "s3 Size is: " << s3.size( ) << endl;

    return 0;
}