#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string.h>
#include <cstring>
using namespace std;

class lista{
    private:
    int key;
    double zmienna;
    char znak;
    lista *next;
    public:
    void dodaj(class lista *&head, int x);
    void wypisz(class lista *head);
    void szukanie(class lista *head,int wartosc);
    void wypisz_klucze(class lista *head,int ilosc);
    int liczenie(class lista *head);
    void sortowanie(class lista *&head);
    void usuwanie(class lista *&head);
    void wstawianieel(class lista *&head,int x);
    void usuwanieel(class lista *&head,int x);
    void wypisz_ostatnie(class lista *head,int ile, int ilosc);
}*head=NULL,*tmp=NULL;   // tmp=ogon

void lista:: dodaj(class lista *&head,int x)
{

  if(x==0)
  {
        head->key=(rand() % (99999 - 99 +1) + 99);
        head->znak='T';
        head->zmienna=(rand() % (9000 - 1000 + 1) - 1000);
        head->next=NULL;
        tmp=head;
  }
  else
  {
        bool test;
        lista *help=head,*help2=head,*help3 = NULL,*nowy=(class lista*)new lista;
        help3=NULL;
		do{
            help2=head;
            test=false;
            nowy->key=(rand() % (99999 - 99 +1) + 99);
            nowy->znak='T';
            nowy->zmienna=(rand() % (9000 - 1000 + 1) - 1000);
            while(help2)
            {
                if(nowy->key==help2->key)
                    {
                        test=true;
                    }
                help2=help2->next;
            }
        }while(test==true);
        while(help)
        {
            if(help->next==NULL)
            {
            	if(nowy->key>help->key)
            	{
            		help->next=nowy;
            		nowy->next=NULL;
            		return;
				}
				else
				{
					if(help3==NULL)
					{
						nowy->next=help;
						head=nowy;
						return;
					}
					else
					{
						help3->next=nowy;
						nowy->next=help;
						return;
					}
				}
			}
			if(nowy->key<help->key&&help3==NULL)
			{
				nowy->next=help;
				head=nowy;
				return;
			}
			if((nowy->key>help->key)&&(nowy->key<help->next->key))
			{
				nowy->next=help->next;
				help->next=nowy;
				return;
			}

        	help3=help;
        	help=help->next;
        }
    }
}

 void lista::wstawianieel(class lista *&head,int x)
{
    lista *help=head, *help2 = NULL, *nowy=new lista;
    nowy->key=x;
    nowy->znak='T';
    nowy->zmienna=(rand() % (9000 - 1000 + 1) - 1000);
    while(help)
        {
            if(help->next==NULL)
            {
            	if(nowy->key>help->key)
            	{
            		help->next=nowy;
            		nowy->next=NULL;
            		return;
				}
				else
				{
					if(help2==NULL)
					{
						nowy->next=help;
						head=nowy;
						return;
					}
					else
					{
						help2->next=nowy;
						nowy->next=help;
						return;
					}
				}
			}
			if(nowy->key<help->key&&help2==NULL)
			{
				nowy->next=help;
				head=nowy;
				return;
			}
			if((nowy->key>help->key)&&(nowy->key<help->next->key))
			{
				nowy->next=help->next;
				help->next=nowy;
				return;
			}

        	help2=help;
        	help=help->next;
        }

}

void lista::usuwanieel(class lista *&head,int x)
{
    class lista *help=head, *help2 = NULL;
    while(help)
    {
        if(help->key==x)
        {
            help2->next=help->next;
        }
        help2 = help;
        help=help->next;
    }
}


void lista::szukanie(class lista *head,int wartosc)
{
    class lista *help=head;
    bool test=false;
    while(help)
    {
        if(help->key==wartosc)
        {
            cout<< "Szukany element----> Klucz:"<<help->key<<"  "<<"zmienna:"<<help->zmienna<<"  "<<"Znak:"<<help->znak<<"  "<<"Adres: " <<help;
            test=true;
            break;
        }
        help=help->next;
    }
    if(test==false)
    {
        cout<<"Nie znalezniono wezla z kluczem "<<wartosc<<" w liscie"<<endl;
    }
}

void lista::wypisz(class lista *head)
{
    class lista *help=head;
    while(help)
    {
        cout<< "Klucz:"<<help->key<<"  "<<"zmienna:"<<help->zmienna<<"  "<<"Znak:"<<help->znak<<"  "<<"Adres: " <<help;
        cout<<endl;
        help=help->next;
    }
}

void lista::wypisz_ostatnie(class lista *head,int ile, int ilosc)
{
    class lista *help=head;
    int licznik2=0,licznik=0;
    int tab[10];
    while(help)
    {
        if(licznik<ilosc-ile)
        {
            help=help->next;
            licznik++;
        }
        else
        {
        	tab[licznik2]=help->key;
        	licznik2++;
        	help=help->next;
        }
    }
    for(int i=10;i>=0;i--)
    {
		cout<< "Klucz:"<<tab[i];
		cout<<endl;
	}
}

void lista::wypisz_klucze(class lista *head,int ilosc)
{
    class lista *help=head;
    for(int i=0;i<ilosc;i++)
    {
        cout<<"Klucz:"<<help->key<<endl;
        help=help->next;
    }
}

int lista::liczenie(class lista *head)
{
    class lista *help=head;
    int licznik=0;
    while(help)
    {
        licznik+=1;
        help=help->next;
    }
    return licznik;
}

void lista::usuwanie(class lista *&head)
{
    lista *help = NULL;
    while(head)
    {
        help = head;
        head = head->next;
        delete help;
    }
    delete head;
}

void pierwsze_20(class lista *head)
{
    cout<<"pierwsze 20:"<<endl;
    head->wypisz_klucze(head,20);
    cout<<endl;
}

int main()
{
    srand( time( NULL ) );
    clock_t begin, end;
    double time_spent;
    begin = clock();

    int ilosc_wezlow=0;
    int x;
    int k1,k2,k3,k4,k5;
    int n;
    ifstream dane("inlab02.txt");
    dane >> x;
    dane >> k1;
    dane >> k2;
    dane >> k3;
    dane >> k4;
    dane >> k5;
    cout <<"klucze: "<<k1<<" "<<k2<<" "<<k3<<" "<<k4<<" "<<k5<< endl;
    cout << endl;

    head= new lista;

    for(int i=0;i<x;i++)
        head->dodaj(head,i);

    head->wypisz(head);
    cout<<endl;

    head->szukanie(head,k1);
    cout<<endl;

    ilosc_wezlow=head->liczenie(head);
    cout<<"ilosc wezlow = "<<ilosc_wezlow<<endl<<endl;

    pierwsze_20(head);
    head->wstawianieel(head,k2);
    pierwsze_20(head);
    head->wstawianieel(head,k3);
    pierwsze_20(head);
    head->wstawianieel(head,k4);
    pierwsze_20(head);
    head->wstawianieel(head,k5);
    head->usuwanieel(head,k3);
    pierwsze_20(head);
    head->usuwanieel(head,k2);
    pierwsze_20(head);
    head->usuwanieel(head,k5);

    ilosc_wezlow=head->liczenie(head);
    cout<<"ilosc wezlow = "<<ilosc_wezlow<<endl<<endl;

    head->szukanie(head,k5);
    cout<<endl;

    cout<<"ostatnie 11:"<<endl;
    ilosc_wezlow=head->liczenie(head);
    head->wypisz_ostatnie(head,11,ilosc_wezlow);
    cout<<endl;

    ilosc_wezlow=head->liczenie(head);
    cout<<"ilosc wezlow = "<<ilosc_wezlow<<endl<<endl;

    head->usuwanie(head);

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    cout << "Czas wykonania: " << time_spent << endl;
    return 0;
}