#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define D_CRT_NONSTDC_NO_WARNINGS_GLOBALS
#pragma warning(disable : 4996)

typedef struct _cvor* Position;
typedef struct _cvor
{
    int broj;
    Position next;
}Cvor;

void FreeAlocatedData(Position);
int PopuniListu(Position);
void IspisListe(Position);
int NapraviUniju(Position prvaLista, Position drugaLista, Position unija);
int NapraviPresjek(Position prvaLista, Position drugaLista, Position presjek);
int GenerirajSlucajniBroj(int min, int max);
int DodajSortirano(Position, Position);
Position KreirajCvor(int);
int DodajIzaTrenutnog(Position lista, Position newItem);

int main(int argc, char* argv[])
{
    Cvor prvaLista;
    Cvor drugaLista;
    Cvor unija;
    Cvor presjek;

    prvaLista.next = NULL;
    drugaLista.next = NULL;
    unija.next = NULL;
    presjek.next = NULL;

    srand((unsigned)time(NULL));

    PopuniListu(&prvaLista);
    PopuniListu(&drugaLista);
    IspisListe(prvaLista.next);
    IspisListe(drugaLista.next);

    NapraviUniju(&prvaLista, &drugaLista, &unija);
    NapraviPresjek(&prvaLista, &drugaLista, &presjek);

    IspisListe(unija.next);
    IspisListe(presjek.next);

    FreeAlocatedData(&prvaLista);
    FreeAlocatedData(&drugaLista);
    FreeAlocatedData(&unija);
    FreeAlocatedData(&presjek);

    return 0;
}

int PopuniListu(Position head)
{
    int brojClanova = 0;
    int i = 0;
    int slucajniBroj = 0;
    Position noviCvor = NULL;

    printf("Koliko ce bit clanova u listi? ");
    scanf(" %d", &brojClanova);

    for (i = 0; i < brojClanova; i++)
    {
        slucajniBroj = GenerirajSlucajniBroj(0,9);
        noviCvor = KreirajCvor(slucajniBroj);
        DodajSortirano(head, noviCvor);
    }

    return 0;
}
void IspisListe(Position position)
{
    while (position != NULL)
    {
        printf("%d ", position->broj);
        position = position->next;
    }
    printf("\n");
}
int GenerirajSlucajniBroj(int min, int max)
{
    int broj = 0;

    broj = rand() % (max - min + 1) + min;

    return broj;
}
Position KreirajCvor(int broj)
{
    Position noviCvor = NULL;

    noviCvor = (Position)malloc(sizeof(Cvor));

    noviCvor->broj = broj;
    noviCvor->next = NULL;

    return noviCvor;
}
int DodajIzaTrenutnog(Position lista, Position newItem)
{
    newItem->next = lista->next;
    lista->next = newItem;

    return 0;
}

int DodajSortirano(Position head, Position newItem)
{
    while (head->next != NULL)
    {
        if (newItem->broj == head->next->broj)
        {
            free(newItem);
            return 0;
        }

        if (newItem->broj < head->next->broj)
        {
            break;
        }

        head = head->next;
    }

    DodajIzaTrenutnog(head, newItem);
    return 0;
}
int NapraviUniju(Position prvaLista, Position drugaLista, Position unija)
{
    Position p1 = NULL;
    Position p2 = NULL;
    Position p3 = NULL;
    Position temp = NULL;

    p1 = prvaLista->next;
    p2 = drugaLista->next;

    while ((p1 != NULL) && (p2 != NULL))
    {
        if (p1->broj < p2->broj)
        {
            p3 = KreirajCvor(p1->broj);
            DodajIzaTrenutnog(unija, p3);
            unija = unija->next;
            p1 = p1->next;
        }
        else if (p1->broj > p2->broj)
        {
            p3 = KreirajCvor(p2->broj);
            DodajIzaTrenutnog(unija, p3);
            unija = unija->next;
            p2 = p2->next;
        }
        else
        {
            p3 = KreirajCvor(p2->broj);
            DodajIzaTrenutnog(unija, p3);
            unija = unija->next;
            p2 = p2->next;
            p1 = p1->next;
        }
    }

    if (p1 == NULL)
        temp = p2;
    if (p2 == NULL)
        temp = p1;

    while (temp != NULL)
    {
        p3 = KreirajCvor(temp->broj);
        DodajIzaTrenutnog(unija, p3);
        unija = unija->next;
        temp = temp->next;
    }
    return 0;
}
void FreeAlocatedData(Position position)
{
    Position temp = NULL;

    while (position->next != NULL)
    {
        temp = position->next;
        free(temp);
        position = position->next->next;
    }
}
int NapraviPresjek(Position prvaLista, Position drugaLista, Position presjek)
{
    Position p1 = NULL;
    Position p2 = NULL;
    Position p3 = NULL;

    p1 = prvaLista->next;
    p2 = drugaLista->next;

    while ((p1 != NULL) && (p2 != NULL))
    {
        if (p1->broj < p2->broj)
            p1 = p1->next;
        else if (p1->broj > p2->broj)
            p2 = p2->next;
        else
        {
            p3 = KreirajCvor(p1->broj);
            DodajIzaTrenutnog(presjek, p3);
            presjek = presjek->next;
            p1 = p1->next;
            p2 = p2->next;
        }
    }

    return 0;
}