#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <windows.h>


//ZAD 2. Zaimplementuj jednokierunkową listę. Dodj do listy 1000 losowych elementów. Zmierz średni czas dostępu do tego samego i losowego elementu.
//       Wytłumacz różnicę. Zaimplementuj funkcję megre(lista l1, lista l2) która połączy 2 listy.


typedef struct Node
{
    int el;
    struct Node *next;
} Node;


bool isEmpty(Node **head)
{
    return ((*head) == NULL);
}


void enqueue(int x, Node **head) //wstaw w odpowiednie miejsce do listy
{
    if(head == NULL) return;

    if(isEmpty(head)) //pusta kolejka
    {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->el = x;
        newNode->next = NULL;
        (*head) = newNode;
    }
    else //wstawiamy do posortowanej listy
    {
        Node *newNode = (Node*)malloc(sizeof(Node));
        newNode->el = x;
        newNode->next = NULL;

        Node *tmp = (*head);

        if(x < tmp->el) //wstawiamy przed pierwszym elementem
        {
            newNode->next = tmp;
            (*head) = newNode;
        }
        else //wstawiamy po którymś z kolejnych elementów
        {
            while(tmp->next != NULL && tmp->next->el < x)
                tmp = tmp->next;

            Node *nast = tmp->next;

            tmp->next = newNode;
            newNode->next = nast;
        }
    }
}

void showElements(Node **head)
{
    printf("Kolejne elementy listy: ");
    if(head != NULL && (*head) != NULL)
    {
        Node *tmp = (*head);
        while(tmp != NULL)
        {
            printf("%d ", tmp->el);
            tmp = tmp->next;
        }
        printf("\n");
    }
    else
        printf("lista pusta.\n");
}

void idzDo(int numer, Node **head)
{
    if(head != NULL && (*head) != NULL)
    {
        Node *tmp = (*head);
        int i;
        for(i=0; i<numer; i++)
        {
            if(tmp->next != NULL)
            {
                tmp = tmp->next;
            }
        }
        //printf("Dotarlem do %d elementu\n", i);
    }
    else
    {
        printf("Lista pusta\n");
    }
}

void deleteNode(int key, Node **head)
{
    if(head == NULL || (*head) == NULL) return;

    Node *ptr = (*head);
    Node *tmp;
    if(ptr->el == key) //jezeli już w głowie jest szukany klucz
    {
        while(ptr != NULL && ptr->el == key)
        {
            tmp = ptr;
            ptr = ptr->next;
            free(tmp);
            tmp = NULL;
        }
        (*head) = ptr; //jezeli pusta lista została to wskazuje na NULL, a jak nie to na kolejny rozny element
    }
    else // jezeli szukany klucz jest w innym elemencie niż głowa
    {
        while(ptr->next != NULL && ptr->next->el != key) //zatrzymuje się jeden element przed NULL'em albo przed szukanym elemencie
        {                                                //jezeli przed NULLem to znaczy ze nic nie znalazl
            ptr = ptr->next;
        }

        if(ptr->next == NULL) return; //nic nie znalezlismy
        Node *first = ptr;
        ptr = ptr->next;



        while(ptr != NULL && (ptr->el) == key)
        {
            tmp = ptr;
            ptr = ptr->next;
            free(tmp);
            tmp = NULL;
        }

        first->next = ptr;
    }
}



void megre(Node **lista1, Node **lista2) //poczatek posortowanej listy jest w (*lista1)
{
    if(lista1 == NULL || lista2 == NULL || ((*lista1) == NULL && (*lista2) == NULL) ) return; //łączenie nie ma sensu

    if((*lista1) == NULL) //druga nie jest NULLem z górnego if'a
    {
        (*lista1) = (*lista2); //podczepiamy druga liste, jezeli druga jest nullem to zostaje jak jest
        (*lista2) = NULL;
        free(lista2); //not sure, ale chyba moge zwolnic miejsce na wskazanie na druga liste skoro je polaczylismy
        lista2 = NULL;
    }
    else //obie listy zawieraja posortowane elementy
    {
        Node *tmp1 = (*lista1);
        Node *tmp2 = (*lista2);

        Node *wynik;

        //najpierw ustalmy glowe nowej listy
        if(tmp1->el < tmp2->el)
        {
            tmp1 = tmp1->next; //lista1 wskazuje juz na poprawny pierwszy element
            wynik = (*lista1);
        }
        else
        {
            wynik = (*lista2);
            (*lista1) = tmp2;
            tmp2 = tmp2->next;
        }

        while(tmp1 != NULL && tmp2 != NULL) //dopoki nie dojdziemy do konca którejś z list
        {
            if(tmp1->el < tmp2->el)
            {
                Node *first = tmp1;


                while(tmp1->next != NULL && tmp1->next->el < tmp2->el)
                    tmp1 = tmp1->next;


                (*lista1)->next = first;

                (*lista1) = tmp1;
                tmp1 = tmp1->next;
            }
            else
            {
                Node *first = tmp2;

                while(tmp2->next != NULL && tmp2->next->el < tmp1->el)
                    tmp2 = tmp2->next;


                (*lista1)->next = first;
                (*lista1) = tmp2;
                tmp2 = tmp2->next;
            }
        }

        //teraz któraś z poprzednich list jest już pusta wiec wystarczy podczepić resztę drugiej
        if(tmp1 == NULL)
            (*lista1)->next = tmp2;
        else
            (*lista1)->next = tmp1;

        (*lista1) = wynik;

        (*lista2) = NULL;
        free(lista2);
        lista2 = NULL;

    }
}


int main()
{
    Node *lista1 = (Node*)malloc(sizeof(Node));
    Node *lista2 = (Node*)malloc(sizeof(Node));
    lista1 = NULL;
    lista2 = NULL;

    printf("Czy lista jest pusta?: %s\n", isEmpty(&lista1) ? "tak" : "nie");

    srand(time(NULL));
    int r;
    int i;
  /*  for(i=0; i<10; i++)
    {
        r = rand();
        enqueue(r, &lista1);
    } */

    enqueue(2, &lista1); enqueue(3, &lista1); enqueue(3, &lista1); enqueue(3, &lista1); enqueue(4, &lista1); enqueue(6, &lista1); enqueue(8, &lista1); enqueue(8, &lista1);
    for(i=0; i<10; i++)
    {
        r = rand();
        enqueue(r, &lista2);
    }

    printf("Przed.\n");
    showElements(&lista1);
    //
    deleteNode(3, &lista1);
    showElements(&lista1);

    deleteNode(8, &lista1);
    showElements(&lista1);

    deleteNode(6, &lista1);
    showElements(&lista1);

    deleteNode(2, &lista1);
    showElements(&lista1);
    //
    printf("Po.\n");

    showElements(&lista2);

    megre(&lista1, &lista2);

    showElements(&lista1);
    showElements(&lista2);


    clock_t start_t, end_t;
    double total_t;
    int n;
    int ile = 10000;
   // start_t = GetTickCount();
    start_t = clock();

    for(n=0; n<1000; n++)
    {
        idzDo(9000, &lista1);
    }


  //  end_t = GetTickCount();
    end_t = clock();

    total_t = (double)(end_t - start_t);
    printf("Sredni czas dostepu: %f\n", total_t);


    return 0;
}