#include <iostream>
#include <conio.h>
#include <fstream>
#include <time.h>
using namespace std;

struct elem{
        int val;        //wartosc elementu listy
        elem *next;     //wskaznik na nastepny element listy
};

void elem_add(struct elem *lista,int num){
        while(lista->next)
                if(num>lista->next->val)        lista=lista->next;
                else                            break;  //Po tej petli lista zawiera element za ktorym
        struct elem *add=new struct elem;               //trzeba dodoac nowy element
        struct elem *tmp=lista->next;
        lista->next=add;
        add->next=tmp;                                  //Zabawa w przestawianie adresow
        add->val=num;
        return;
}

void elem_erase(struct elem *lista,int num){		//Lepiej podac wlasciwy num (0 ; n-1). else Acces violation murowany :)
        for(int i=0;i<num;i++)  lista=lista->next;      //Petla znajduje element,
        struct elem *tmp;                               //poprzedzajacy ten, ktory bedzie usuniety
        tmp=lista->next->next;
        delete lista->next;                             //Zabawa w przestawianie adresow
        lista->next=tmp;
        return;
}

struct elem *lista_init(int n){
        struct elem *first;
        first=new struct elem;
        first->val=n;
        first->next=NULL;
        return first;
}

void list_delete(struct elem *lista){
	struct elem *tmp;
        int i=0;
	while(lista){
		tmp=lista->next;
		delete lista;
                lista=tmp;
	}
        return;
}

struct elem *elem_find(struct elem *lista,int n){
        lista=lista->next;
        while(lista&&lista->val!=n)     lista=lista->next;
        return lista;
}

int *dane(int n){
        int index1;
        int index2;
        int tmp;
        int *tab=new int[n];
        for(int i=0;i<n;i++)    tab[i]=i;
        for(int i=0;i<n*10;i++){
                index1=rand()%n;
                index2=rand()%n;
                tmp=tab[index1];
                tab[index1]=tab[index2];
                tab[index2]=tmp;
        }
        return tab;
}

int main(){
        struct elem *first;
        ofstream plik;
        plik.open(".\\elu.txt");
        plik.close();
        plik.open(".\\elu.txt",ios::out);
        int k;
        clock_t start;
        int *tab;
        int a[10];
        int b[10];
        int c[10];
        plik<<"SERIA DANYCH OX\n";
        for(int i=10000;i<=55000;i=i+5000)  plik<<i<<" ";
        plik<<endl;
        for(int i=10000;i<=55000;i=i+5000){
                tab=dane(i);
                first=lista_init(-1);

                start=clock();
                for(int j=0;j<i;j++)    elem_add(first,tab[j]);
                a[k]=clock()-start;

                start=clock();
                for(int j=0;j<i/10;j++)    elem_find(first,tab[j]);
                b[k]=clock()-start;

                start=clock();
                list_delete(first);
                c[k]=clock()-start;

                k++;
                delete []tab;
        }
        plik<<"\nDODAWANIE ELEMENTOW DO LISTY (N)\n";
        for(int i=0;i<10;i++)   plik<<a[i]<<" ";
        plik<<"\nWYSZUKIWANIE ELEMENTU W LISCIE (N)\n";
        for(int i=0;i<10;i++)   plik<<b[i]<<" ";
        plik<<"\nUSUWANIE LISTY (N)\n";
        for(int i=0;i<10;i++)   plik<<b[i]<<" ";
        return 0;
}