set

//множества
#include <iostream.h>
#include <conio.h>

template <class SetType> class set{
public:
    set(int size);
    set(set<SetType> &ob);
    ~set(){del();};

    //функции
    void init();//вводим множества
    void print();//печатаем множества

    friend set <SetType> operator +(SetType &el, set<SetType> &ob){return ob+el;};//элемент + множество
    set <SetType> operator +(SetType &el);//множество + элемент
    set <SetType> operator +(set<SetType> &ob);//объединение множеств
    set <SetType> operator &(set<SetType> &ob);//пересечение множеств
    set <SetType> operator -(set<SetType> &ob);//разность множеств
    set <SetType> operator ^(set<SetType> &ob);//симметричная разность
    set <SetType> &operator =(const set &ob);//присваивание

    int operator <(set<SetType> &ob);//подмножество
    int operator >(set<SetType> &ob);//надмножество
    int operator <(SetType &el);//принадлежность элемента
    int operator ==(set<SetType> &ob);//эквивалентность множеств
    int operator !=(set<SetType> &ob);//неэквивалентность множеств
    int operator &();//проверка на пустоту
    int operator !();//размер множества

    set <SetType> operator --(int x);//удаление элемента из конца
    set <SetType> operator --();//удаление элемента из начала


    friend ostream &operator << (ostream &cout, set<SetType> &ob);//печать
    //-->
private:
    int sz;//размер множества
    int id;

    struct list{//структура, в которой хранятся элементы множеств
        SetType key;
        list *next;
    };
    list *root;
    list *head;

    //функции для работы со списком
    list *search(SetType key);//поиск элемента в списке
    list *search(set<SetType> &ob, SetType key);//поиск элемента в списке
    list *search_el(SetType id);//проверка множества на уникальность элементов
    void add(SetType id);//добавление элемента в список
    void del();//удаление списка
    void del_el();//удаление элемента
};

//--------------------------------------------------------------------------------------------------------------------------->
//--------------------------------------------------------------------------------------------------------------------------->
template <class SetType> set<SetType>::set(int size){
    sz=size;
    root=head=new list;

    if(sz>1)
        init();//вводим множества

    else if(sz==1){
        cin >> root->key;
        root->next=new list;
        root->next = NULL;
    }
    else if(sz==0)
        root=head=NULL;
}

template <class SetType> void set<SetType>::init(){//вводим множества
    cin >> root->key;//вводим первый элемент множества
    for(int i=0; i<sz-1; i++){//вводим остальные элементы
        root->next=new list;
        cin >> root->next->key;
        root=root->next;
        root->next=NULL;
        //проверка на уникальность элементов
        while(search_el(root->key)!=NULL){
            cout << "error!";
            cin >> root->key;
        }
    }
}

template <class SetType> set<SetType>::set(set<SetType> &ob):sz(0){
    root=head=NULL;
    list *temp=head=ob.head;
    root=new list;

    while(temp){
        add(temp->key);
        temp=temp->next;
    }
}
//--------------------------------------------------------------------------------------------------------------------------->
//функции для работы со списком:
//--------------------------------------------------------------------------------------------------------------------------->
template <class SetType> set<SetType>::list *set<SetType>::search(SetType key){//поиск элемента в списке
    list *tmp=head;
    while (tmp!=NULL){
        if (tmp->key==key)
            break;
        tmp=tmp->next;
    }
    return tmp;
}

template <class SetType> set<SetType>::list *set<SetType>::search(set<SetType> &ob, SetType key){//поиск элемента в списке
    list *tmp=ob.head;
    while (tmp!=NULL){
        if (tmp->key==key)
            break;
        tmp=tmp->next;
    }
    return tmp;
}

template <class SetType> void set<SetType>::add(SetType id){//добавляем элемент
    if(sz==0){
        head=new list;
        head->key=id;
        head->next=NULL;
        root=head;
    }
    else{
        list *tmp=new list;
        tmp->key=id;
        tmp->next=NULL;
        root->next=tmp;
        root=tmp;
    }
    sz++;
}

template <class SetType> void set<SetType>::print(){//печатаем множества
    list *tmp=head;
    while(tmp){
        cout << tmp->key << " ";
        tmp=tmp->next;
    }
    cout <<endl;
}

template <class SetType> void set<SetType>::del(){//удаление списка
    list *tmp;
    while(head){
        tmp=head;
        head=head->next;
        delete[] tmp;
    }
    sz=0;
}

//проверка элементов
template <class SetType> set<SetType>::list *set<SetType>::search_el(SetType id){
    list *tmp=head;

    while (tmp->next){
        if (tmp->key==id)
            return tmp;
        tmp=tmp->next;
    }
    return NULL;
}

//удаление элемента
template <class SetType> void set<SetType>::del_el(){
    list *tmp=head;

    while(tmp->next)
        tmp=tmp->next;
    list *q=tmp;

    tmp=head;
    while(tmp->next->next)
        tmp=tmp->next;
    tmp->next=NULL;
    delete[] q;
}
//--------------------------------------------------------------------------------------------------------------------------->
//перегрузка операторов:
//--------------------------------------------------------------------------------------------------------------------------->
//печать
template <class SetType> ostream &operator << (ostream &cout, set<SetType> &ob){
    ob.root=ob.head;
    while(ob.root){
        cout << ob.root->key << " ";
        ob.root=ob.root->next;
    }
    cout <<endl;

    return cout;
}

//объединение двух множеств /объект + объект/
template <class SetType> set<SetType> set<SetType>::operator +(set<SetType> &ob){
    set<SetType> val=*this;
    list *tmp=ob.head;

    for(int i=0; i<ob.sz; i++){
        val=val+(tmp->key);
        tmp=tmp->next;
    }
    return val;
}

//объединение двух множеств /объект + элемент/
template <class SetType> set<SetType> set<SetType>::operator +(SetType &el){
    set<SetType> val=*this;

    if(search(el)==NULL)//проверяем, нет ли в множестве этого элемента
        val.add(el);//добавляем элемент в список
    return val;
}

//пересечение множеств
template <class SetType> set<SetType> set<SetType>::operator &(set<SetType> &ob){
    set<SetType> newval(0);//пустое множество, в которое будет скопирован результат поиска
    list *tmp=ob.head;

    while(tmp){
        if(search(tmp->key)!=NULL)
            newval.add(tmp->key);
        tmp=tmp->next;
    }

    return newval;
}

//разность множеств
template <class SetType> set<SetType> set<SetType>::operator -(set<SetType> &ob){
    set<SetType> newval(0);//пустое множество, в которое будет скопирован результат поиска
    list *temp=head;

    while(temp){
        if(search(ob, temp->key)==NULL)
            newval.add(temp->key);
        temp=temp->next;
    }
    return newval;
}

//симметричная разность
template <class SetType> set<SetType> set<SetType>::operator ^(set<SetType> &ob){
    set<SetType> newval(0);
    list *temp=head;
    list *tmp=ob.head;

    //копируем элементы из первого множества
    while(temp){
        if(search(ob, temp->key)==NULL)
            newval.add(temp->key);
        temp=temp->next;
    }
    //копируем элементы из второго множества
    while(tmp){
        if(search(tmp->key)==NULL)
            newval.add(tmp->key);
        tmp=tmp->next;
    }
    return newval;
}

//присваивание
template <class SetType> set<SetType> & set<SetType>::operator =(const set &ob){
    if(sz==ob.sz){
        list *tmp=head;
        list *temp=ob.head;

        while(tmp){
            tmp->key=temp->key;
            tmp=tmp->next;
            temp=temp->next;
        }
    }
    else{
        del();
        list *tmp=ob.head;

        while(tmp){
            add(tmp->key);
            tmp=tmp->next;
        }
    }
    return *this;
}

//подмножество
template <class SetType> int set<SetType>::operator <(set<SetType> &ob){
    list *tmp=head;

    while(tmp){
        if(search(ob, tmp->key)==NULL)//ищем отсутствие элементов из 1 множества во 2
            return 0;
        tmp=tmp->next;
    }
    return 1;
}

//надмножество
template <class SetType> int set<SetType>::operator >(set<SetType> &ob){
    list *tmp=ob.head;

    while(tmp){
        if(search(tmp->key)==NULL)//ищем отсутствие элементов из 2 множества в 1
            return 0;
        tmp=tmp->next;
    }
    return 1;
}

//принадлежность элемента
template <class SetType> int set<SetType>::operator <(SetType &el){
    root=head;
    if(search(el)!=NULL)//проверяем наличиe элемента
        return 1;

    return 0;
}

//эквивалентность
template <class SetType> int set<SetType>::operator ==(set<SetType> &ob){
    list *temp=ob.head;

    while(temp){
        if(search(temp->key)==NULL)//если какой-то элемент 2 множества не равен элементам 1, то множества неэквивалентны
            return NULL;
        temp=temp->next;
    }
    return 1;
}

//неэквивалентность
template <class SetType> int set<SetType>::operator !=(set<SetType> &ob){
    return !(*this==ob);
}

//пустое ли
template <class SetType> int set<SetType>::operator &(){
    if(head)
        return 1;
    return NULL;
}

//размер множества
template <class SetType> int set<SetType>::operator !(){
    int i=0;
    list *tmp=head;

    while(tmp){
        tmp=tmp->next;
        i++;
    }
    return i;
}

//удаление элемента из хвоста
template <class SetType> set<SetType> set<SetType>::operator --(int x){
    if(sz>1){
        list *tmp=head;

        while(tmp->next)
            tmp=tmp->next;
        list *q=tmp;

        tmp=head;
        while(tmp->next->next)
            tmp=tmp->next;
        tmp->next=NULL;
        delete[] q;
    }
    else
        cout << "size<1!" <<endl;

    return *this;
}

//удаление элемента из головы
template <class SetType> set<SetType> set<SetType>::operator --(){
    if(sz>1){
        list *temp;
        temp=head;
        head=head->next;
        delete temp;
    }
    else
        cout << "size<1!" <<endl;

    return *this;
}
//--------------------------------------------------------------------------------------------------------------------------->
//--------------------------------------------------------------------------------------------------------------------------->

int main(){
    int sz1, sz2;//размеры для создания объекта
    int size=0;//размер множества

    cout <<"SIZE1: ";//размер множества
    cin >> sz1;
    cout <<"SIZE2: ";
    cin >> sz2;

    cout << "set1(int): " <<endl;//множества целочисленных элементов
    set<int> s_int_1(sz1);
    cout << "set2(int): " <<endl;
    set<int> s_int_2(sz2);

    //================================================================>
    cout << "__________________________" <<endl;
        int el1;
        cout << "el: ";
        cin >> el1;
        cout <<endl;
        s_int_1=el1+s_int_1;//элемент + множество
        cout << "el+s_int_1: ";
        cout << s_int_1;

        int el;
        cout << "el(add): ";
        cin >> el;//вводим элемент, который надо прибавить к множеству
        cout <<endl;
        cout << "set1+el: ";
        s_int_1=s_int_1+el;//добавляем элемент к множеству
        cout << s_int_1;

        if(s_int_1 < s_int_2){//множество 1 является подмножеством множества 2
            cout << "s_int_1 < s_int_2" <<endl;
            cout <<endl;
        }

        if(s_int_1 > s_int_2){//множество 1 является надмножеством множества 2
            cout << "s_int_1 > s_int_2" <<endl;
            cout <<endl;
        }

        int tmp;
        cout << "el: ";
        cin >> tmp;
        cout <<endl;
        if(s_int_1 < tmp)//определяем принадлежность введеного элемента множеству
            cout << "el < set1" <<endl;

        if(s_int_1 == s_int_2){//эквивалентность
            cout << "s_int_1 == s_int_2" <<endl;
            cout << endl;
        }

        if(s_int_1 != s_int_2){//неэквивалентность
            cout << "s_int_1 != s_int_2" <<endl;
            cout << endl;
        }

        if(!(&s_int_1))//пустое ли
            cout <<"s_int_1 == NULL";

        size=(!s_int_1);//размер
        cout << "SIZE: " << size <<endl;

    //================================================================>
    cout << "__________________________" <<endl;
    cout << "set1 ^ set2: ";
    s_int_1=s_int_1^s_int_2;//симметричная разность
    cout << s_int_1;

    cout << "set1 - set2: ";
    s_int_1=s_int_1-s_int_2;//разность
    cout << s_int_1;

    cout << "set1 + set2: ";
    s_int_1=s_int_1+s_int_2;//объединение множеств
    cout << s_int_1;

    cout << "set1 & set2: ";
    s_int_1=s_int_1&s_int_2;//пересечение множеств
    cout << s_int_1;

    s_int_1=s_int_1--;//удаление последнего элемента
    cout << "s_int_1--: ";
    cout << s_int_1;

    s_int_1=--s_int_1;//удаление первого элемента
    cout << "--s_int_1: ";
    cout << s_int_1;

    cout << "Press any key...";
    getch();
}