#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=100;//(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,*nowy=(class lista*)new lista;
		do{
			bool 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(help->key>nowy->key)
				{
				  	nowy->next=help;
				  	help=nowy;
				 	return;
				}
				else
				{
					help->next=nowy;
					nowy->next=NULL;
					return;
				}
			}
			if(help->key>nowy->key)
			{
				nowy->next=help;
				help=nowy;
				return;
			}
			else
			{
				if(help->key<nowy->key && help->next->key>nowy->key)
        		{
        			nowy->next=help->next;
        			help->next=nowy;
					return;
				}
			}
        	help=help->next;
		}
	}
}


void lista::wstawianieel(class lista *head,int x)
{
	lista *help=head, *help2 = NULL, *help3=new lista;
	help3->key=x;
	help3->znak='T';
	help3->zmienna=(rand() % (9000 - 1000 + 1) - 1000);
	while(help)
	{
		if(help2 == NULL)
		{
			if(help3->key<help->key)
			{
				help3->next=help;
				head=help3;
			}
		}
		if(help->next=NULL)
		{
			help3->next=NULL;
			help->next=help3;
		}
		if(help->key<help3->key && help3->key<help2->key)
        {
			help3->next=help2->next;
			help->next=help3;
		}
		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;
			delete help;
		}
		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 licznik=0;
    while(help)
    {
    	if(licznik<ilosc-ile)
    	{
    		help=help->next;
    		licznik++;
		}
		else
        {
        	cout<< "Klucz:"<<help->key;
        	cout<<endl;
        	help=help->next;
		}
    }
}

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)
{
	while(head)
    {
        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=(class lista*)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;
}