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

  /* Vezane liste - Primjer 9_w (s puno ispisa).
     Sortiranje liste MergeSort algoritmom.
     Raspolavljanje liste koristenjem pokazivaca.
  */

/* ======================================================================== */

    /* Tip za pokazivac na element liste. */

typedef struct _element *lista;

    /* Tip za element liste. */

typedef struct _element {
    int broj;            /* Sadrzaj je broj. */
    lista sljed;         /* Pokazivac na sljedeci element u listi. */
} element;

/* ======================================================================== */

    /* Funkcije za osnovne operacije s listama, koje su potrebne
       za funkciju merge_sort_write. */

/* ======================================================================== */

int broj_elemenata(lista prvi)
{
    lista pom;
    int brojac = 0;

    for (pom = prvi; pom != NULL; pom = pom->sljed)
        ++brojac;

    return brojac;
}

/* ======================================================================== */

void ispisi_listu_short(lista prvi)
{
    lista pom;

    for (pom = prvi; pom != NULL; pom = pom->sljed) {
        printf(" %d ->", pom->broj);
    }
    printf(" NULL\n");

    return;
}

/* ======================================================================== */

lista merge(lista prvi_1, lista prvi_2)
{
        /* Sortirano spaja dvije liste (merge). */

    lista prvi = NULL, zadnji, pom;

        /* Ako je jedna lista prazna, rezultat je ona druga lista. */
    if (prvi_1 == NULL) return prvi_2;
    if (prvi_2 == NULL) return prvi_1;

        /* U nastavku obrade, obje liste sigurno NISU prazne. */

        /* Prolaz po obje liste, sve dok su obje neprazne. */
    while (prvi_1 != NULL && prvi_2 != NULL) {

            /* Nadji manjeg, od prvog iz prve liste i prvog iz
               druge liste. Izbaci ga s pocetka njegove liste,
               tj. skrati pripadnu listu. */
        if (prvi_1->broj <= prvi_2->broj) {
            pom = prvi_1;
            prvi_1 = prvi_1->sljed;
        }
        else {
            pom = prvi_2;
            prvi_2 = prvi_2->sljed;
        }

            /* Ubaci ga na kraj sortirane liste. */
        if (prvi == NULL)
            prvi = pom;
        else
            zadnji->sljed = pom;
        zadnji = pom;
    }

        /* Spoji neprazni ostatak (tocno jedna lista, druga je prazna)
           na kraj sortirane liste. */
    if (prvi_1 == NULL)
        zadnji->sljed = prvi_2;

    if (prvi_2 == NULL)
        zadnji->sljed = prvi_1;

    return prvi;
}

/* ======================================================================== */

    /* Funkcija merge_sort_write. */

/* ======================================================================== */

lista merge_sort_write(lista prvi, int dubina)
{
        /* Sortira listu Merge_Sort algoritmom. */

    lista zadnji, prvi_2;

    printf("\n");
    printf("  Dubina %d, Ulaz:\n", dubina);
    printf("    Ulazna lista - duljina = %d:\n",
           broj_elemenata(prvi));
    printf("        ");
    ispisi_listu_short(prvi);

        /* Test na praznu ili jednoclanu listu. */
    if ((prvi == NULL) || (prvi->sljed == NULL)) {
        printf("  Dubina %d, Izlaz.\n", dubina);
        return prvi;
    }

        /* U nastavku obrade, lista ima bar dva elementa. */

        /* ``Raspolovi'' listu. Pokazivac zadnji pokazuje na zadnjeg
           u prvom dijelu. Pokazivac prvi_2 je trenutno pomocni
           i sluzi za raspolavljanje liste. */
    zadnji = prvi;
    prvi_2 = prvi->sljed;

        /* Pomicemo zadnjeg za JEDNO mjesto, a prvi_2 za DVA mjesta,
           sve dok prvi_2 ne stigne do kraja liste. */
    while ((prvi_2 != NULL) && (prvi_2->sljed != NULL)) {
        zadnji = zadnji->sljed;
        prvi_2 = prvi_2->sljed->sljed;
    }

        /* Pokazivac zadnji sad korektno pokazuje na zadnjeg u prvom
           dijelu. Pokazivac prvi_2 postavljamo na prvog u drugom
           dijelu (prvi iza zadnjeg) i korektno zavrsavamo prvi dio. */
    prvi_2 = zadnji->sljed;
    zadnji->sljed = NULL;

    printf("    Prva lista  - duljina = %d:\n",
           broj_elemenata(prvi));
    printf("        ");
    ispisi_listu_short(prvi);
    printf("    Druga lista - duljina = %d:\n",
           broj_elemenata(prvi_2));
    printf("        ");
    ispisi_listu_short(prvi_2);


        /* Rekurzivno sortiranje obje liste. */
    prvi = merge_sort_write(prvi, dubina + 1);
    prvi_2 = merge_sort_write(prvi_2, dubina + 1);


    printf("\n");
    printf("  Dubina %d, Sort:\n", dubina);
    printf("    Sortirana prva lista  - duljina = %d:\n",
           broj_elemenata(prvi));
    printf("        ");
    ispisi_listu_short(prvi);
    printf("    Sortirana druga lista - duljina = %d:\n",
           broj_elemenata(prvi_2));
    printf("        ");
    ispisi_listu_short(prvi_2);


        /* Sortirano spajanje. */
    prvi = merge(prvi, prvi_2);


    printf("    Sortirana spojena lista - duljina = %d:\n",
           broj_elemenata(prvi));
    printf("        ");
    ispisi_listu_short(prvi);
    printf("  Dubina %d, Izlaz.\n", dubina);

    return prvi;
}

/* ======================================================================== */

    /* Ispod su funkcije za osnovne operacije s listama. */

/* ======================================================================== */

lista kreiraj_straga(lista prvi, lista *p_zadnji, int broj)
{
        /* Vraca zadnji kroz varijabilni argument - pokazivac p_zadnji. */

    lista zadnji = *p_zadnji;
    lista novi = NULL;
/*
    if ((novi = (lista) malloc(sizeof(element))) == NULL)
*/
    novi = (lista) malloc(sizeof(element));
    if (novi == NULL) {
        printf("Alokacija nije uspjela.\n");
        exit(EXIT_FAILURE);    /* exit(1); */
    }

    novi->broj = broj;
    novi->sljed = NULL;

    if (prvi == NULL)
        prvi = novi;
    else
        zadnji->sljed = novi;

/* Ne treba:
    zadnji = novi; *p_zadnji = zadnji;
*/
    *p_zadnji = novi;    /* Vrati novi zadnji! */

    return prvi;
}

/* ======================================================================== */

lista obrisi_listu(lista prvi)
{
    lista pom;
/*
    while (prvi != NULL)
        prvi = obrisi_prvog(prvi);
*/
    while (prvi != NULL) {
        pom = prvi;
        prvi = prvi->sljed;
        free(pom);
    }

    return NULL;    /* <=> return prvi; */
}

/* ======================================================================== */

int main(void)
{
    lista prvi = NULL;    /* Prazna lista! */
    lista zadnji;
    int broj;

        /* Punjenje liste straga. */

        /* Citanje niza brojeva za listu, do broj = 0.
           To je oznaka kraj niza, ali nije clan niza. */
        /* Poredak brojeva u listi je isti kao redoslijed
           citanja, jer dodajemo na kraj liste. */

    printf("Upisite niz cijelih brojeva (0 = kraj).\n");
    do {
        printf("Sljedeci broj:\n");
        scanf("%d", &broj);
        if (broj != 0)
            prvi = kreiraj_straga(prvi, &zadnji, broj);
    } while (broj != 0);

        /* Ispis broja elemenata i cijele liste. */

    printf("\n Polazna lista:\n");
    printf(" Broj elemenata u listi = %d\n",
           broj_elemenata(prvi));
    ispisi_listu_short(prvi);


        /* Sortiranje liste - mergesort. */

    printf("\n MergeSort liste (raspolavljanjem):\n");
    prvi = merge_sort_write(prvi, 1);

        /* Sortirana lista:
           ispis broja elemenata i cijele liste. */

    printf("\n Sortirana lista:\n");
    printf(" Broj elemenata u listi = %d\n",
           broj_elemenata(prvi));
    ispisi_listu_short(prvi);

        /* Obrisi cijelu listu. */

    prvi = obrisi_listu(prvi);

    return 0;
}