#include <iostream.h>
#include <stdio.h>
#include <conio.h>
#include <math.h>

int menu()
{
    const int nItems = 5;
    const char *menu[nItems] = {
        "Dobavlenie", "Prosmotr", "Sortirovka", "ochistka", "exit"
    };

    int index = 0;
    char ch = '\0';

    while(ch != 13)
    {
        clrscr();
        for(int i = 0; i < nItems; i++)
        {
            if(i == index) { textattr(70); printf("*"); }
            cprintf("%s\r\n", menu[i]);
            textattr(7);
        }

        int delta = 0;
        if((ch = getch()) == 0)
        {
            ch = getch();
            switch(ch)
            {
                case 72:
                    delta = -1; break;
                case 80:
                    delta = +1; break;
            }
            index = (nItems + index + delta) % nItems;
        }
    }
    return index;
}


class List
{
public:
    List()
    {
        head = tail = 0;
    }
    void Append(int);
    void Print();

    void Split(List& lst);
    void Merge(List& lst)
    {
        for(ListItem *p = lst.head; p; p = p->next)
        {
            cout << p-> val << " added ..." << endl;
            Append(p->val);
            Print();
        }
    }
    void Sort()
    {
        for(ListItem *f = head; f->next; f = f->next)
        {
            for(ListItem *s = f->next; s; s = s->next)
            {
                if(f->val > s->val)
                {
                    int T = f->val; f->val = s->val; s->val = T;
                }
            }
        }
    }
    int Contains(const List& lst);

private:
    class ListItem
    {
    public:
        int val;
        ListItem *next;

        ListItem(int value, ListItem *item = 0)
        {
            val = value; next = item;
        }
    };

    ListItem *head, *tail;
    void Remove(ListItem *item)
    {
        if(head == item)
        {
            head = head->next;
            delete item;
        }
        else
          {
              ListItem *p;
              for(p = head; p->next != item; p = p->next);
              p->next = item->next;

              if(p->next == 0) tail = p;
              delete item;
          }

        if(head == 0) tail = 0;
    }
};

void List::Append(int val)
{
    ListItem *p = new ListItem(val);
    if(!head) head = p;
    else tail->next = p;

    tail = p;
}
void List::Print()
{
    for(ListItem *p = head; p; p = p->next)
    {
        cout << p->val << ((p->next == 0) ? "" : ", ");
    }
    cout << endl;
}

void List::Split(List& lst)
{
    for(ListItem *p = head; p; p = p->next)
    {
        if(p->val < 0)
        {
            lst.Append(abs(p->val));
            Remove(p);
        }
    }
}

int List::Contains(const List& list)
{
    for(ListItem *p = head; p; p = p->next)
    {
        if(p->val == list.head->val)
        {
            ListItem *first = p, *second;
            for(second = list.head; first && second; second = second->next)
            {
                if(first->val == second->val) first = first->next;
                else break;
            }
            if(!second) return 1;
        }
    }
    return 0;
}


int main ()
{
    List myList;
    List myList2;

    int index;

    do
    {
        switch(index = menu())
        {
            case 0:
            {
                char ch = '\0';
                int n;

                while(ch != 'n')
                {
                    cout << "Vvedite element spiska" << endl;
                    cin >> n;

                    myList.Append(n);
                    cout << "Prodoljitb vvod? [y/n]" << endl;
                    ch = getch();
                }

                myList.Split(myList2);
                if(myList.Contains(myList2))
                {
                    myList.Merge(myList2);
                    myList.Sort();
                }

                cout << "first list = "; myList.Print();
                cout << "second list = "; myList2.Print();
                getch();
            }
            break;

            case 1:
                myList.Print();
                getch();
                break;

            case 2:
            case 3:
                break;
        }

    }
    while(index < 4);

    return 0;
}