#define _CRT_SECURE_NO_WARNINGS

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

int* generiraj(int n);
void shuffle(int *niz, int n);
int* presjek(int *skupA, int *skupB, int n);
int* presjek_jedan_sortiran(int *skupA, int* skupB, int n);
int* presjek_oba_sortirana(int *skupA, int *skupB, int n);
int compare(const void * a, const void * b) {
    return (*(int*)a - *(int*)b);
}

int main(int argc, char *argv[])
{
    double total;
    clock_t start, end;

    for (int n = 100000; n < 30000000; n += 300000)
    {
        int *skupA = generiraj(n);
        int *skupB = generiraj(n);
        shuffle(skupA, n), shuffle(skupB, n);

        //PRESJEK

        start = clock();
        int *p = presjek(skupA, skupB, n);
        end = clock();

        printf("PRESJEK\n\n");

        printf("Start: %d\n", start);
        printf("End: %d\n", end);
        total = (((double)end - (double)start) / CLOCKS_PER_SEC);
        printf("Total: %f\n\n", total);

        //PRESJEK_JEDAN_SORTIRAN

        start = clock();
        int *pjs = presjek_jedan_sortiran(skupA, skupB, n);
        end = clock();

        printf("PRESJEK_JEDAN_SORTIRAN\n\n");

        printf("Start: %d\n", start);
        printf("End: %d\n", end);
        total = (((double)end - (double)start) / CLOCKS_PER_SEC);
        printf("Total: %f\n\n", total);

        //PRESJEK_OBA_SORTIRANA

        start = clock();
        int *pos = presjek_oba_sortirana(skupA, skupB, n);
        end = clock();

        printf("PRESJEK_OBA_SORTIRANA\n\n");

        printf("Start: %d\n", start);
        printf("End: %d\n", end);
        total = (((double)end - (double)start) / CLOCKS_PER_SEC);
        printf("Total: %f\n\n", total);

        free(p);
        free(pjs);
        free(pos);
    }

    return 0;
}

int* generiraj(int n) {
    int* niz = (int*)malloc(sizeof(int) * n);
    niz[0] = rand() % 5;
    int i;
    for (i = 1; i < n; i++) {
        niz[i] = niz[i - 1] + 1 + rand() % 5;
    }
    return niz;
}

void shuffle(int *niz, int n) {
    int i;
    for (i = 0; i < n; i++) {
        int j = (rand() * rand()) % n;
        int tmp = niz[i];
        niz[i] = niz[j];
        niz[j] = tmp;
    }
}

int* presjek(int *skupA, int *skupB, int n)
{
    int counter, k;
    counter = 0, k = 0;
    int *p = (int *)malloc(n * sizeof(int));
    if (p != NULL)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (skupA[i] = skupB[j])
                {
                    counter++;
                }
            }
            if (counter);
            {
                p[k] = skupA[i];
                k++;
            }
        }
        p = (int *)realloc(p, k * sizeof(int));
        return p;
    }
    return -1;
}

int* presjek_jedan_sortiran(int *skupA, int* skupB, int n)
{
    int *pjs = (int *)malloc(n * sizeof(int));
    int k = 0;
    qsort(skupB, n, sizeof(int), compare);
    if (pjs != NULL)
    {
        for (int i = 0; i < n; i++)
        {
            if (bsearch(&skupA[i], skupB, n, sizeof(int), compare) != NULL)
            {
                pjs[k] = skupA[i];
                k++;
            }
        }
        pjs = (int *)realloc(pjs, k * sizeof(int));
        return pjs;
    }

    return -2;
}

int* presjek_oba_sortirana(int *skupA, int *skupB, int n)
{
    int *pos = (int *)malloc(n * sizeof(int));
    int i, j, k;
    i = 0, j = 0, k = 0;
    qsort(skupA, n, sizeof(int), compare);
    qsort(skupB, n, sizeof(int), compare);

    if (pos != NULL)
    {
        while (i < n && j < n)
        {
            if (skupA[i] < skupB[j])
            {
                i++;
            }
            else if (skupA[i] > skupB[j])
            {
                j++;
            }
            else if (skupA[i] == skupB[j])
            {
                pos[k] = skupA[i];
                i++;
                j++;
                k++;
            }
        }
        return pos;
    }
    return -3;
}