Class Set

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

using namespace std;

/*
 *  Реализация класса множеств, перегрузка операторов.
 *
 *  *****
 *  29.05.2011
**/

//Формат комментариев функций: [возвращаемая информация] [входящая информация] [задача функции]

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 int el) const;
        set operator +(const set & s)const;
        set operator -(const int el) const;
        set operator -(const set & s2) const;
        set operator & (const set & s2)const;
        set operator ^ (const set & s)const;
        short operator < (const set & s) const;
        short operator > (const set & s) const { return (s < *this);}
        short operator < (int el) const;
        set & operator += (const int el);
        set & operator += (const set & s);
        set & operator -= (const set & s);
        set & operator -= (const int el);
        set & operator &= (const set & s);
        set & operator ^= (const set & s);

    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 operator +(int el, const set & s)                       //элемент+множество
{
    set newS(s);                    //копируем множество
    if (!newS.contains(el))
    {
        newS.push(el);                  //добавляем в конец
        struct element *p = newS.rear;  //и притворяемся, что это - начало.
        while(p->next != newS.rear)
            p = p->next;
        newS.rear = p;
    }
    return newS;
}

set set::operator +(const int el)const
{
    set newS = *this;
    if (!newS.contains(el))
        newS.push(el);
    return newS;
}

set set::operator +(const set & s)const         //сложение(объединение)множеств
{
    if (*this == s || s.power == 0)
        return *this;
    if (power == 0)
        return s;
    set newS;
    struct element *p2 = s.rear->next;        //р2 - указатель на правое множество ((левое_множество+правое_множество))
    int i = 0;
    if (power >= s.power)            //маленькая оптимизация
    {
        newS = *this;                   //копируем большее множество
        do                              //и добавляем в него элементы меньшего
        {
            newS+=p2->v;
            p2 = p2->next;
        } while (p2 != s.rear->next);
    }
    else
    {
        return (s+(*this));
    }
    return newS;
}


set set::operator -(const int el) const
{
    set newS;                       //создаем пустое множество
    struct element *p = rear->next;
    do                            //и копируем внего все элементы множества-уменьшаемого
    {                               //за исключением эквивалентного элементу
        if (p->v != el)
            newS.push(p->v);
        p = p->next;
    } while (p != rear->next);
    return newS;
}

set set::operator -(const set & s2) const                //разность множеств
{
    if (s2.power == 0)              //если вычитаемое пусто, разность равна вычитаемому
        return *this;
    set newS;
    if (((power == s2.power) && (*this == s2)) || power == 0) //если мн-ва равны (или уменьшаемое пусто), возвращаем пустое множество
    {
        return newS;
    }
    struct element *p = rear->next;
    int i;
    do              //Для всех элементов уменьшаемого множества:
    {

        if (!s2.contains(p->v))      //если эл-т не содержится в вычитаемом множестве, добавляем его в разность.
            newS.push(p->v);
        p = p->next;
    } while (p != rear->next);
    return newS;
}

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)
{
    if (power == 0 || !contains(el))   //добавляем эл-т в мн-во
        push(el);
    return *this;
}

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

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

set & set::operator -=(const set & s) //вычесть множество из множества
{
    if (s.power == 0)              //из пустого множества не вычесть
        return *this;
    struct element *p = s.rear->next;
    do   //вычесть каждый член вычитаемого множества из уменьшаемого множества
    {
        *this-=p->v;
        p = p->next;
    } while (p != s.rear->next);
    return *this;
}

set & set::operator &= (const set & s)       //пересечение с изменением
{
     if (s.power == 0 || power == 0 || (power == s.power && *this == s)) //если изменений нет, возвратить без изменений
        return *this;
     if (*this < s)         //если является подмножеством, изменений нет
        return *this;
    int i = 0;
    struct element *p = rear->next,*res,*tmp,*del;  //res - результирующий список элементов
    res = NULL;                                     //tmp - для swap'a;
    del = NULL;                                     //del - удаляемые элементы
    do                              //проверяем все элементы изменяемого множества по очереди
    {
        if (s.contains(p->v))       //если элемент содержится во втором множестве
        {                           //то он идет в результирующий список
            tmp = res;
            res = p;
            p = p->next;
            res->next = tmp;
            i++;
        }
        else
        {
            tmp = del;          //иначе - удаляется
            del = p;
            p = p->next;
            del->next = tmp;
        }
        power--;
    } while (power && p);
    p = del;
    while (p && p->next)         //удаляем все неводшедшие в пересечение элементы
    {
        tmp = p->next;
        delEl(p);
        p = tmp;
    }
    delEl(p);
    p = res;
    power = i;
    if (p)
    {
        while (p->next)     //находим конец результирующего списка - и замыкаем его.
            p = p->next;
        p->next = res;
    }
    rear = p;           //и обновляем данные в результирующем множестве.
    return *this;
}

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


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

short set::operator < (int el) const    //принадлежность элемента множеству
{
    if (contains(el))
        return 1;
    else
        return 0;
}

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();
}