#include <stdio.h>
#include <stdlib.h>
#include "list.h"

int List_Push(List** p_list, int value)
/*
Co robi: Dodaje element na początek listy
Pobiera: wskaźnik do wskaźnika początku listy, wartość do wstawienia.
*/
{
    List *new_element = malloc(sizeof(List));//rezerwuj pamięć
    if(!new_element)
        return 1;//malloc fail
    new_element-> data = value;//dodaj wartość
    new_element->next = *p_list;//ustaw wskaźnik next na początek starej listy
    *p_list=new_element;//ustaw adres przekazanej listy na nowy element
    return 0;
}

int List_Add(List** p_list, int value)
/*
Co robi: Dodaje element na koniec listy
Pobiera: wskaźnik do wskaźnika początku listy, wartość do wstawienia.
*/
{
    List *element =*p_list; //pobierz adres
    if(element==NULL) //jeśli pusta lista
    {
        List_Push(p_list, value);//wywołaj dodawanie na początek
        return 0;
    }
    while(element->next!=NULL) //szukaj wskazania na koniec (NULL terminator)
    {
        element=element->next;//przeskakuj po liście
    }
    element->next = malloc(sizeof(List));//rezerwuj pamięć i zapisz ten adres zamiast NULL
    if(element->next==NULL)//malloc fail
        return 1;
    element=element->next;//przesuwamy się na nowy, ostatni element
    element->next=NULL;//dodajemy terminator
    element->data=value;//wpisujemy wartość
    return 0;
}
int List_Add_List(List** p_list_p, List** p_list_s, int index)
/*
Co robi: Dodaje listę (p_list_s) pod index innej listy (p_list_p)
Pobiera: wskaźnik do wskaźnika początku listy bazowej, wskaźnik do wskaźnika początku listy wstawianej, index pod który wstawiamy
*/
{
    int i=0;
    List *base =*p_list_p; //początek bazowej
    List *put =*p_list_s; //początek wstawianej
    while(put->next!=NULL) //poruszamy się na koniec listy wstawianej
    {
        put =put->next;
    }
    if(index==0) //jeśli wstawiamy na początek
    {

        put->next=*p_list_p;//początek listy bazowej staje się ostatnim elementem wstawianej
        *p_list_p=*p_list_s;//nowy początek listy staje się początkiem listy wstawianej
        return 0;
    }
    for(i=0; i<index-1; ++i) //przesuwamy się pod index na liście bazowej
    {
        base=base->next;
    }
    put->next=base->next;//pod końcem listy wstawianej wstawiamy adres elementu zapisanego jako "następny"
    base->next=*p_list_s;//pod "następnym" w liście bazowej o zadanym indeksie wstawiamy adres początku listy wstawianej
    return 0;
}

int List_Add_At(List** p_list, int value, int index)
/*
Co robi: Dodaje element w wyznaczonym indeksie
Pobiera: wskaźnik do wskaźnika początku listy, wartość do wstawienia, index
*/
{
    int i=0;
    List *element =*p_list;//pobierz adres
    List *next_element;
    if(index==0)//jeśli wstaw na początek
    {
        List_Push(p_list, value);
        return 0;
    }

    for(i=0; i<index-1; ++i) //przesuń się pod wskazany index
    {
        element=element->next;
    }
    next_element=element->next;//zapamiętaj element następujący
    element->next= malloc(sizeof(List));//rezerwuj pamięć i przypisz do wskaźnika poprzedzającego
    if(element==NULL)//malloc fail
        return 1;
    element=element->next;//przesuń się na element wstawiany
    element->next=next_element;//wstaw adres następującego
    element->data=value;//wstaw wartość
    return 0;
}

int List_Count(List* p_list)
/*
Co robi: Liczy ilość elementów listy
Pobiera: wskaźnik początku listy
*/
{
    int count=0;
    List *element =p_list->next;
    if(p_list==NULL)//jeśli pusta
        return 0;
    while(element!=NULL)//szukaj końca i zliczaj elementy
    {
        element =element->next;
        count++;
    }
    count++;
    return count; //zwróć licznik
}

int List_Get(List* p_list, int index)
/*
Co robi: zwraca dane z wyznaczonego indeksu listy
Pobiera: wskaźnik początku listy, index
*/
{
    int i=0;
    for(i=0; i<index; ++i) //szukaj indeksu
    {
        p_list=p_list->next;
    }
    return p_list->data;//zwróć wartość
}

void List_Print_All(List* p_list)
/*
Co robi: drukuje wszystkie elementy listy
Pobiera: wskaźnik początku listy
*/
{
    while(p_list!=NULL)//przesuwaj się do końca
    {
        printf("%d\t",p_list->data);//drukuje dane
        p_list=p_list->next;
    }
    printf("\n");
}

int List_Del(List** p_list, int index)
{
    /*
    Co robi: usuwa element spod wybranego indeksu
    Pobiera: wskaźnik do wskaźnika początku listy, index
    */
    int i;
    List *element =*p_list;
    List *previous_element;
    List *next_element;
    if(index==0)//jeśli kasujemy pierwszy
    {
        *p_list=element->next;//nowy początek listy to teraz element o indeksie 1
        free(element);//uwolnij pamięć spod elementu o indeksie 0
        return 0;
    }
    for(i=0; i<index-1; ++i) //szukaj indeksu
    {
        element=element->next;
    }
    previous_element=element;//zapamiętaj poprzedzający element
    element=element->next;//przesuń się o jeden
    next_element=element->next;//zapamiętaj następny element
    previous_element->next=next_element;//połącz poprzedzający i następny
    free(element);//uwolnij pamięć spod elementu o zadanym indeksie
    return 0;
}

int List_Del_All(List** p_list)
/*
Co robi: usuwa całą listę i ustawia wskaźnik do niej na terminator NULL
Pobiera:  wskaźnik do wskaźnika początku listy
*/
{
    List *element =*p_list;//bieżący element
    List *temp;
    while(element!=NULL)//przesuwaj się do końca
    {
        temp=element;//zapamiętaj adres
        element=element->next;//przesuń się na następny
        free(temp);//skasuj spod zapisanego adresu
    }
    *p_list=NULL; //pod listę wpisz NULL
    return 0;
}
int List_Add_ToSorted(List** p_list, int value, int sort_direction)
/*
Co robi: wstawia wartość w odpowiednie miejsce na posortowanej liście
Pobiera:  wskaźnik do wskaźnika początku listy, wartość, kierunek sortowania (1 dla malejącego, 0 dla rosnącego)
*/
{
    List *element =*p_list;
    List *next_element;
    if(element==NULL || (element->data>=value)^sort_direction) //jeśli pusta lub wstawianie przed pierwszy element
    {
        List_Push(p_list, value);
        return 0;
    }
    while((element->next) && (element->next->data<value)^sort_direction) //jeśli nie osiągnie końca lub wartość z indeksem jeden do przodu nie będzie spełniała nierówności
        element=element->next;//przesuwanie
    next_element=element->next;//zapamiętaj element następujący
    element->next= malloc(sizeof(List));//rezerwuj pamięć i przypisz do wskaźnika poprzedzającego
    if(element==NULL)//malloc fail
        return 1;
    element=element->next;//przesuń się na element wstawiany
    element->next=next_element;//wstaw adres następującego
    element->data=value;//wstaw wartość
    return 0;
}

int List_Sort_Selection_Sort(List** p_list, int sort_direction)
/*
Co robi: sortuje listę poprzez proste wybieranie, mało wydajne.
Pobiera:  wskaźnik do wskaźnika początku listy, kierunek sortowania (1 dla malejącego, 0 dla rosnącego)
*/
{
    List *element =*p_list;//pobierz początek starej listy
    List *new_list=NULL;//nowa lista
    List *temp=NULL;//temp
    while(element->next)//przesuwanie się po liście
    {
        List_Add_ToSorted(&new_list,element->data,sort_direction);//dodaj element ze starej do nowej
        temp=element; //zapamiętaj adres bieżącego elementu
        element=element->next;//przesuń się o jeden do przodu
        free(temp);//uwolnij pamięć z wykorzystanego elementu
    }
    List_Add_ToSorted(&new_list,element->data,sort_direction);//dodaj ostatni element
    free(element);//zwolnij ten element
    *p_list=new_list;//podstaw nową listę w miejsce starej
    return 0;
}
List* List_GetRange(List* p_list, int start, int count)
/*
Co robi: zwraca wybrany zakres jako nową tablicę
Pobiera:  wskaźnik do początku listy, indeks startowy i długość kopiowanego fragmentu
*/
{
    int i;
    List *new_list=NULL;
    for(i=0; i<start; ++i)
        p_list=p_list->next; //przesuń się pod adres startu
    for(i=0; i<count; ++i)
    {
        List_Add(&new_list,p_list->data);//kopiuj dane
        p_list=p_list->next;
    }
    return new_list;//zwróc skopiowany fragment
}
int List_Merge(List** p_list_a,List** p_list_b, int sort_direction)
/*
Co robi: łączy dwie listy posortowane w tym samym kierunku i zwraca adres we wskaźniku pierwszej listy
Pobiera:  wskaźnik do wskaźnika początku listy 1, wskaźnik do wskaźnika początku listy 2, kierunek sortowania (1 dla malejącego, 0 dla rosnącego)
*/
{
    List *new_list=NULL;
    List *a=*p_list_a;
    List *b=*p_list_b;
    while (a&&b)
    {
        if ((a->data < b->data)^sort_direction)
        {
            List_Add(&new_list,a->data);
            a=a->next;
        }
        else
        {
            List_Add(&new_list,b->data);
            b=b->next;
        }
    }
    if(a)
        while(a)
        {
            List_Add(&new_list,a->data);
            a=a->next;
        }
    else
        while(b)
        {
            List_Add(&new_list,b->data);
            b=b->next;
        }
    List_Del_All(p_list_a);
    List_Del_All(p_list_b);
    *p_list_a=new_list;
    return 0;
}
List* List_MergeSort(List** p_list, int sort_direction)
/*
Co robi: Sortuje listy rekurencyjną metodą mergesort
Pobiera:  wskaźnik do wskaźnika początku listy, kierunek sortowania (1 dla malejącego, 0 dla rosnącego)
*/
{
    {
        int N, k;
        List * A=NULL;
        List * B=NULL;
        N = List_Count(*p_list);
        if (N > 1)
        {
            k = N / 2;
            A=List_GetRange(*p_list, 0, k);
            B=List_GetRange(*p_list, k, N-k);
            A=List_MergeSort(&A, sort_direction);
            B=List_MergeSort(&B, sort_direction);
            List_Del_All(p_list);
            List_Merge(&A, &B, sort_direction);
            return A;
        }
        else
        {
            return *p_list;
        }

    }
}