#include <iostream>
#include <conio.h>
#include <assert.h>

using namespace std;


struct element
{
    int v;
    struct element * next;
};


class set
{
    public:
        set():power(0),rear(NULL){};
        set(const set & s);
        set(int p);
        set(int * a, int sz);
        ~set();
        friend ostream & operator <<(ostream & out, const set & s);
        set & operator --(); //prefix
        set & operator --(int); //postfix
        operator int() { return power; }
        short operator == (const set & s) const;
        set & operator = (const set & s);
        friend set operator +(int el, const set & s);
        set operator & (const set & s2)const;
        set operator ^ (const set & s)const;



    private:
        int power;
        struct element * rear;
        void push(int val);
        struct element * contains(int v) const;
        void delEl(struct element * p);
};


void set::push(int val)
{
    struct element * newEl = new element;
    newEl->v = val;
    power++;
    if (rear)                       //если список не пустой
    {
        newEl->next = rear->next;
        rear->next = newEl;
        rear = newEl;
    }
    else                            //если список пустой, закольцовываем его
    {
        newEl->next = newEl;
        rear = newEl;
    }
}


set set::operator ^(const set &s) const                                                                 //TEST
{
    if (power==0)           //если одно из множеств пустое, симм. разность будет равна другому мн-ву
        return s;
    if (s.power == 0)
        return *this;
    set newS;
    if (*this == s)        //если множества равны, симм.разность равна пустому мн-ву.
        return newS;
    newS = (*this);
    newS = newS + (*this);
    newS^=s;
    return newS;
}

set::set(int * a, int sz):power(0),rear(NULL)           //конструктор, изымающий множество из массива
{
    push(a[0]);
    for (int i=1; i<sz; i++)
    {
        if (!contains(a[i]))
            push(a[i]);
    }
}

struct element * set::contains(int val) const //ищет элемент в множестве и возвращает указатель на него
{
    if (!rear)
        return 0;
    struct element * p = rear;
    do
    {
        if (p->v == val)
            return p;
        p = p->next;
    } while (p != rear);
    return NULL;
}

void set::delEl(struct element * p)
{
    power--;
    delete p;
}

set::set(const set & s):power(0),rear(NULL)     //копирующий конструктор
{
    if (s.rear)
    {
        struct element * p = s.rear->next;
        do
        {                           //почленное копирование
            push(p->v);
            p = p->next;
        } while (p != s.rear->next);
    }
}

set::~set()
{
    if (power)                              //если содержит элементы, значит есть что удалять
    {
        struct element * p;
        do                               //удаляем последовательно все элементы
        {
            p = rear->next;
            rear->next = p->next;
            delEl(p);
        } while (power);
    }
}

ostream & operator <<(ostream & out, const set & s)
{
    if (s.power == 0)           //пусто
    {
        out<<"Empty set"<<endl;
        return out;
    }
    int i;                      //не пусто
    struct element * p = s.rear->next;
    out<<"power["<<s.power<<"]"<<endl;
    do
    {
        out<<p->v<<"   ";          //последовательный вывод значений эл-в мн-ва через пробел
        p = p->next;
    } while (p != s.rear->next);
    out<<endl;
    return out;
}


set & set::operator --()                //удаление первого элемента
{
    struct element * p = rear->next;
    rear->next = p->next;
    delEl(p);
    return (*this);
}

set & set::operator --(int)             //удаление последнего элемента
{
    *this -= rear->v;
    return (*this);
}

short set::operator == (const set & s) const
{
    if (power != s.power)                   //если мощности множеств не равны, множества не равны
        return 0;
    if (power == 0)                         //два пустых множества равны
        return 1;
    struct element * p = s.rear;
    do                                      //пробег по всем элементам одного множества
    {
        if (!contains(p->v))                //если во втором множестве не содержится такого элемента,
            return 0;                       //то множества не равны
        p = p->next;
    } while (p != s.rear);
    return 1;                               //иначе - равны.
}

set & set::operator = (const set & s)                       //присваивание
{
    if (s == *this)
        return *this;
    if (s.power == 0)
    {
        delete this;
        power=0;
        return *this;
    }
    int i = 0, min=(power<s.power?power:s.power);           //i - счетчик, max - минимальная мощность двух множеств.
    struct element *p = (power?rear->next:NULL), *p2 = s.rear->next;                 //р2 - указатель на эл-т присваивоемого мн-ва, р  - указатель на элемент другого мн-ва.
    for (i = 0; i < min; i++)      //копируем все, что влазит
    {
        p->v = p2->v;
        p = p->next;
        p2 = p2->next;

    }
    if (power < s.power)                    //если не влазит, добавляем
    {
        for (;i < s.power; i++)
        {
            push(p2->v);
            p2 = p2->next;
        }
    }
    else                                    //если остается лишнее место, удаляем
    {
        while (power != s.power)
            (*this)--;
    }
    power=s.power;
    return *this;
}

set set::operator & (const set & s2)const               //пересечение множеств
{

    if ((power == s2.power)&&(*this == s2))             //если множества равны, возращаем любое из них
        return *this;
    set spike; set spike2; set newS;
    if ((power == 0) || (s2.power == 0))                //если одно из множеств пусто, возвращаем пустое множество
        return newS;
    struct element *p = rear->next;

    if (power <= s2.power)                     //небольшая оптимизация
    {
        do
        {
            if (s2.contains(p->v))       //если элемент одного множества содержится в другом, добавляем его в результирующее мн-во
                newS.push(p->v);
            p = p->next;
        } while( p != rear->next);
    }
    else
    {
        newS = s2 & *this;
    }
    return newS;
}

set & set::operator -=(const int el) //изъятие эл-та из мн-ва
{
    struct element *p = contains(el);
    if (p==NULL || power == 0)
        return *this;         //из пустого множества не получится изъять. Так же не изъять то, чего нет.
    if ((power == 1) & (p != NULL))        //если единственный элемент
    {
        delEl(rear);
        rear = NULL;
        return *this;
    }
    if (p == rear)                     //если конечный элемент
    {
        do
        {
            p = p->next;                //приходится заморачиваться с изменением указателя на хвост
        } while (p->next != rear);
        p->next = rear->next;
        delEl(rear);
        rear = p;
    }
    else
    {
        struct element *tmp = p->next;
        p->v = p->next->v;
        p->next = p->next->next;        //просто вынимаем элемент из списка
        if (tmp == rear)
            rear = p;
        delEl(tmp);

    }
    return *this;
}

void doSomething()
{
    int ar[]={1,2,3,4},br[]={1,5,6,7,8,9},cr[]={1,4,9};
        set a(ar,4);
        set b(br,6);
        set c(cr,3);
    /*
        cout<<"Enter 4 elements for set a"<<endl;
        set a(4);
        cout<<"Enter 6 elements for set b"<<endl;
        set b(6);
        cout<<"Enter 3 elements for set c"<<endl;
        set c(3);
*/
    cout<<"Set d will be empty"<<endl;
    set d;
    cout<<"Lets make new set j = a"<<endl;
    set j;
    j = a;

    cout<<"---------------------------------------------"<<endl;
    cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d<<"Set j:"<<j;
    cout<<"a+b=";
    cout<<"="<<(a+b);
    cout<<"a+a="<<(a+a);
    cout<<"d+c="<<(d+c);

    cout<<"---------------------------------------------"<<endl;



    cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d;

    cout<<"b-c="<<(b-c);
    cout<<"d-a="<<(d-a);
    cout<<"c-d="<<(c-d);

    cout<<"---------------------------------------------"<<endl;
    cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d;
    cout<<"Enter x. Then we will do b-x, x+a and c+x"<<endl;
    int x;
    cin>>x;
    cout<<"b-"<<x<<"="<<(b-x);
    cout<<x<<"+a"<<"="<<(x+a);
    cout<<"c+"<<x<<"="<<(c+x);

    if (b==b)
        cout<<"b==b"<<endl;
    else
        cout<<"b!=b"<<endl;

    if (d==a)
        cout<<"d==a"<<endl;
    else
        cout<<"d!=a"<<endl;

    cout<<"---------------------------------------------"<<endl;
    cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d;
    cout<<"Now let's do c-- and --c"<<endl;
    cout<<"c-- = "<<(c--);
    cout<<"--c = "<<(--c);
    if (b<x)
        cout<<"b<x"<<endl;
    else
        cout<<"b!<x"<<endl;
    if (c<x)
        cout<<"c<x"<<endl;
    else
        cout<<"c!<x"<<endl;
    if (d<a)
        cout<<"d<a"<<endl;
    else
        cout<<"d!<a"<<endl;
    if (b>c)
        cout<<"b>c"<<endl;
    else
        cout<<"b!>c"<<endl;

    cout<<"---------------------------------------------"<<endl;
    cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d;
    cout<<"Now lets make set e=a&b"<<endl;
    set e = a&b;
    cout<<"Set e:"<<e;
    cout<<"e^a="<<(e^a);

    cout<<"---------------------------------------------"<<endl;
    cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d<<"Set e:"<<e;
    cout<<"Enter new x. We will c+=x; b-=x."<<endl;
    cin>>x;
    cout<<"c+=x = "<<(c+=x);
    cout<<"b-=x = "<<(b-=x);
    cout<<"c+=a = "<<(c+=a);
    cout<<"b-=e = "<<(b-=e);
    cout<<"a^=b = "<<(a^=b);
    cout<<"c&=e = "<<(c&=e);
    cout<<"b&=(a-9) = "<<(b&=(a-9));

    cout<<"---------------------------------------------"<<endl;
    cout<<"Set a:"<<a<<"Set b:"<<b<<"Set c:"<<c<<"Set d:"<<d<<"Set e:"<<e;
    cout<<"a^=a = "<<(a^=a);
    cout<<"That's all."<<endl;
    getch();
}

int main()
{
    //doSomething();
     set a,b;
    a+=1;
    a+=2;
    b+=3;
    b+=2;



    cout<<"+"<< (a + b) <<endl;
    //cout<<"+="<< (a+=b) <<endl;
    cout<<"-"<< (a - b) <<endl;
    cout<<"a:"<<a<<"b:"<<b;
    cout<<"^"<< (a ^ b) <<endl;
    cout<<"&"<< (a & b) <<endl;
    cout<<"end.";
    cout<<"^="<<(b^=a)<<endl;
    getch();
}