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

#include "sets.h"

TYPESEG fullPartialSegment [] = {
        0, 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767,
        65535, 131071, 262143, 524287, 1048575, 2097151, 4194303,
        8388607, 16777215, 33554431, 67108863, 134217727, 268435455,
        536870911, 1073741823, 2147483647};
/* 4294967295 */

int Cardinal[256] = {
        0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
        1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
        2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
        3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};



SET allocSet(int n) {
    SET s;

    s = calloc((size_t) (n-1) / SIZESEG + 3, sizeof(TYPESEG));
    assert(s != NULL);
    TAILLE(s) = (TYPESEG) ((n-1) / SIZESEG + 1);
    CARD(s) = 0;
    return s;
}


void freeSet(SET s) {
    free(s);
}


void clearSet(SET s) {
    unsigned int * p = s+TAILLE(s)+1;

    while (p > s+1)
        *p -- = (TYPESEG) 0;
    /*   int i; */

    /*   for (i = 2; i < TAILLE(s)+2; i++) */
    /*     *(s+i) = (TYPESEG) 0; */
    CARD(s) = 0;
}


void FillSet(SET s, int n) {
    int i;

    for (i = 2; i < 2+n/SIZESEG; i++)
        *(s+i) = ~((TYPESEG) 0);

    if (n%SIZESEG != 0)
        *(s+i) = (TYPESEG) fullPartialSegment [n%SIZESEG];

    CARD(s) = (TYPESEG) n;
}


void copySet(SET s, SET d) {
    int i;

    TAILLE(d) = TAILLE(s);
    CARD(d) = CARD(s);
    for (i = 2; i < TAILLE(s)+2; i++)
        *(d+i) = *(s+i);
}


SET makeSet(int *S, int nb, SET E) {
    clearSet(E);
    for (int i = 0; i < nb; i ++)
        ADDe(S[i], E);
    return E;
}


int nCommuns(SET s1, SET s2) {
    int i, n = 0;
    TYPESEG S;
    unsigned char *c;

    for (i = 2; i < TAILLE(s1)+2; i++) {
        S = *(s1+i)&*(s2+i);
        c = (unsigned char *) (&S);
        n += Cardinal[*c]+Cardinal[*(c+1)]+Cardinal[*(c+2)]+Cardinal[*(c+3)];
    }
    return n;
}

int nFaitsCommunsInSet(SET s1, SET s2) {
    int i, n = 0;
    TYPESEG S1, S2;

    for (i = 2; i < TAILLE(s1)+2; i++) {
        S1 = *(s1+i);
        S2 = *(s2+i);
        while (S1 || S2) {
            if ((S1%4 == S2%4) && (S1%4 != 3))
                n ++;
            S1 = (S1 >> (TYPESEG) 2);
            S2 = (S2 >> (TYPESEG) 2);
        }
    }
    return n;
}


int isSubSet(SET u, SET s) {
    int i;

    for (i = 2; i < TAILLE(u)+2; i++)
        if ((*(u+i)&*(s+i)) != *(u+i))
            return 0;
    return 1;
}


int isSupSet(SET u, SET s) {
    int i;

    for (i = 2; i < TAILLE(u)+2; i++)
        if ((*(u+i)&*(s+i)) != *(s+i))
            return 0;
    return 1;
}

char setsIntersect(SET s1, SET s2) {
    int i;

    for (i = 2; i < TAILLE(s1)+2; i++)
        if ((*(s1+i)&*(s2+i)) != (TYPESEG) 0)
            return 1;
    return 0;
}

// add elements of s1 to s2
void addSet(SET s1, SET s2) {
    int i;

    for (i = 2; i < TAILLE(s1)+2; i++)
        *(s2+i) = (*(s2+i))|(*(s1+i));
    CALCARD(s2);
}


void FactsLevelToSet(int * F, int nf, SET S) {
    int i;
    TYPESEG * p = S+SEGMARGIN;

    for (i = 0, *p = (TYPESEG) 0; i < nf; i ++) {
        if ( F[2*i] ) {
            if ( ! F[2*i+1] )
                *p = (*p)|(((TYPESEG) 1) << (TYPESEG) ((2*i)%SIZESEG));
        }
        else if ( F[2*i+1] )
            *p = (*p)|(((TYPESEG) 1) << (TYPESEG) ((2*i+1)%SIZESEG));
        if ((2*i+2)%SIZESEG == 0) {
            p ++;
            *p = (TYPESEG) 0;
        }
    }
    CALCARD(S);
}