#include<malloc.h>
#include <math.h>
#include<stdio.h>
#include <stdlib.h>
#include <time.h>
#include "hdr.h"

int main()
{
    Set *a, *b, *c;
    OverlapFlags of;

    srand(time(0));
    a = set(52);
    print(a);

    b = set(19);
    print(b);

    findOverlap(a, b, &of);

    printf("\n\nSECHENIE:");
    c = Intersection(a, b, &of);
    print(c);
    freeSet(c);

    printf("\n\nRAZLIKA:");
    c = Difference(a, b, &of);
    print(c);
    freeSet(c);

    printf("\n\nOBEDINENIE:");
    c = Union(a, b, &of);
    print(c);
    freeSet(c);

    printf("\n\nSIMETRICHNA RAZLIKA:");
    c = SymmetricDifference(a, b, &of);
    print(c);

    freeOverlap(&of);

    freeSet(a);
    freeSet(b);
    freeSet(c);
    getchar();
    getchar();
    return 0;
}

Set* set(int elcount)
{
    int i, a;
    Set* s;

    s = (Set*)malloc(sizeof(Set));
    s->arr = (int*)malloc(elcount * sizeof(int));

    s->len = elcount;
    random_generator(s);

    return s;
}

void print(Set *s)
{
    int i;
    printf("\nMoshtnost: %d\n", s->len);
    for (i = 0; i < s->len; i++)
    {
        printf("%d, ", s->arr[i], i);
    }
}

int findElement(Set *s, int element)
{
    int i;

    for (i = 0; i < s->len; i++)
    {
        if (element == s->arr[i])
            return i;
    }

    return -1;
}

void findOverlap(Set *A, Set *B, OverlapFlags *result)
{
    int i, findElementIndex;

    result->ofCount = 0;
    result->ofArr = (unsigned int*)calloc((unsigned int)ceilf(2 * (A->len + B->len) / (sizeof(int)*8.0f)), sizeof(int));

    for (i = 0; i < B->len; i++)
    {
        findElementIndex = findElement(A, B->arr[i]);
        if (findElementIndex != -1)
        {
            result->ofArr[(2 * findElementIndex) / (sizeof(int) * 8)] |= (1 << (2 * findElementIndex) % (sizeof(int) * 8));
            result->ofArr[(2 * i + 1) / (sizeof(int) * 8)] |= (1 << (2 * i + 1) % (sizeof(int) * 8));
            result->ofCount += 1;
            findElementIndex = -1;
        }
    }

}

void freeOverlap(OverlapFlags* of)
{
    free(of->ofArr);
}

void freeSet(Set* s)
{
    free(s->arr);
    free(s);
}

Set* Intersection(Set *A, Set *B, OverlapFlags *of)
{
    int i;
    Set *C;

    C = (Set*)malloc(sizeof(Set));
    C->len = 1;
    C->arr = (Set*)malloc(sizeof(int));

    for (i = 0; i < A->len; i++)
    {
        if (of->ofArr[(2 * i) / (sizeof(int) * 8)] & (1 << (2 * i) % (sizeof(int) * 8)))
        {
            C->arr[C->len - 1] = A->arr[i];
            C->len++;
            C->arr = realloc(C->arr, C->len * sizeof(int));
        }
    }

    C->len--;
    C->arr = realloc(C->arr, C->len * sizeof(int));

    return C;
}

Set* Difference(Set *A, Set *B, OverlapFlags *of)
{
    Set *D;
    int i, k;

    D = (Set*)malloc(sizeof(Set));
    D->len = A->len - of->ofCount;
    D->arr = (int*)malloc(D->len * sizeof(int));

    for (i = k = 0; i < A->len; i++)
    {
        if ((of->ofArr[(2 * i) / (sizeof(int) * 8)] & (1 << (2 * i) % (sizeof(int) * 8))) == 0)
        {
            D->arr[k] = A->arr[i];
            k++;
        }
    }


    return D;
}

Set* Union(Set *A, Set *B, OverlapFlags *of)
{
    Set *C;
    int i, k;

    C = (Set*)malloc(sizeof(Set));
    C->len = A->len + B->len - of->ofCount;
    C->arr = (int*)malloc(C->len * sizeof(int));

    for (i = 0; i < A->len; i++)
    {
        C->arr[i] = A->arr[i];
    }

    k = i;
    for (i = 0; i < B->len; i++)
    {
        if ((of->ofArr[(2 * i + 1) / (sizeof(int) * 8)] & (1 << (2 * i + 1) % (sizeof(int) * 8))) == 0)
        {
            C->arr[k] = B->arr[i];
            k++;
        }
    }

    return C;
}

Set* SymmetricDifference(Set *A, Set *B, OverlapFlags *of)
{
    Set *D;
    int i, k;

    D = (Set*)malloc(sizeof(Set));
    D->len = A->len + B->len - of->ofCount * 2;
    D->arr = (int*)malloc(D->len * sizeof(int));

    for (i = k = 0; i < A->len; i++)
    {
        if ((of->ofArr[(2 * i) / (sizeof(int) * 8)] & (1 << (2 * i) % (sizeof(int) * 8))) == 0)
        {
            D->arr[k] = A->arr[i];
            k++;
        }
    }

    for (i = 0; i < B->len; i++)
    {
        if ((of->ofArr[(2 * i + 1) / (sizeof(int) * 8)] & (1 << (2 * i + 1) % (sizeof(int) * 8))) == 0)
        {
            D->arr[k] = B->arr[i];
            k++;
        }
    }


    return D;
}

void random_generator(Set *s)
{
    int i, a;

    a = 1;
    s->arr[0] = 1 + rand() % 6;
    for (i = 1; i < s->len; i++)
    {
        s->arr[i] = (s->arr[i - 1] + 1 + rand() % 25);
        a += 10;
    }
}