/*
 *   set.c -- routines for maniuplating sets and set families
 */

/* LINTLIBRARY */

#include "espresso.h"

static pset_family set_family_garbage = NULL;

/** MM: efektivnejsie by bolo memccpy */
static void intcpy(register unsigned int *d, register unsigned int *s, register long int n)
{
    register int i;
    for(i = 0; i < n; i++) {
    	*d++ = *s++;
    }
}


/* bit_index -- find first bit (from LSB) in a word (MSB=bit n, LSB=bit 0) */
int bit_index(register unsigned int a)
{
    register int i;
    if (a == 0)
	return -1;
    for(i = 0; (a & 1) == 0; a >>= 1, i++)
	;
    return i;
}


/* set_ord -- count number of elements in a set */
int set_ord(register pset a)
{
    register int i, sum = 0;
    register unsigned int val;
    for(i = LOOP(a); i > 0; i--)
	if ((val = a[i]) != 0)
	    sum += count_ones(val);
    return sum;
}

/* set_dist -- distance between two sets (# elements in common) */
int set_dist(register pset a, register pset b)
{
    register int i, sum = 0;
    register unsigned int val;
    for(i = LOOP(a); i > 0; i--)
	if ((val = a[i] & b[i]) != 0)
	    sum += count_ones(val);
    return sum;
}

/* set_clear -- make "r" the empty set of "size" elements */
/** MM: moze dostat NULL parameter r; chybu indikuje navratovou hodnotou NULL */
pset set_clear(register pset r, int size)
{
    if (r==NULL) return NULL; /** MM: kontrola spravnosti parametra */
    
    register int i = LOOPINIT(size);
    *r = i; do r[i] = 0; while (--i > 0);
    return r;
}

/* set_fill -- make "r" the universal set of "size" elements */
/** MM: vrati upravene r */
/** MM: pridana kontrola parametra r */
pset set_fill(register pset r, register int size)
{
    register int i = LOOPINIT(size);
    if (r == NULL) return NULL; /** MM: ak chyba parametra */
    *r = i;
    r[i] = ~ (unsigned) 0;
    r[i] >>= i * BPI - size;
    while (--i > 0)
    	r[i] = ~ (unsigned) 0;
    return r;
}

/* set_copy -- copy set a into set r */
/** MM: pridana kontrola parametrov, chybu indikuje NULL */
/** MM: parametre nedealokuje */
pset set_copy(register pset r, register pset a)
{
    if ( (r == NULL) || (a == NULL)){ /** MM: ak chyba parametrov */
        FREE(a);
        return NULL;
    }
    register int i = LOOPCOPY(a);
    do r[i] = a[i]; while (--i >= 0);
    return r;
}

/* set_and -- compute intersection of sets "a" and "b" */
pset set_and(register pset r, register pset a, register pset b)
{
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = a[i] & b[i]; while (--i > 0);
    return r;
}

/* set_or -- compute union of sets "a" and "b" */
/** MM: pridana kontrola parametrov r a a */
pset set_or(register pset r, register pset a, register pset b)
{
    if ( (r==NULL) || (a==NULL) ) return NULL;
    register int i = LOOP(a);
    /* argument "b" might be used uninitialized -> NULL pointer */
    if (!b) b = a; /*union of "a" and "a" will be "a" */
    PUTLOOP(r,i); do r[i] = a[i] | b[i]; while (--i > 0);
    return r;
}

/* set_diff -- compute difference of sets "a" and "b" */
/** MM: pridana kontrola parametrov */
pset set_diff(register pset r, register pset a, register pset b)
{
    if ( (r == NULL) || (a==NULL) || (b==NULL) ) return NULL; /** MM: ak chyba vystupneho parametra */
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = a[i] & ~b[i]; while (--i > 0); /** MM: cyklus sa vykona minimalne raz -> ukazatele musia byt validne */
    return r;
}

/* set_xor -- compute exclusive-or of sets "a" and "b" */
pset set_xor(register pset r, register pset a, register pset b)
{
    register int i = LOOP(a);
#ifdef IBM_WATC
    PUTLOOP(r,i); do r[i] = (a[i]&~b[i]) | (~a[i]&b[i]); while (--i > 0);
#else
    PUTLOOP(r,i); do r[i] = a[i] ^ b[i]; while (--i > 0);
#endif
    return r;
}

/* set_merge -- compute "a" & "mask" | "b" & ~ "mask" */
pset set_merge(register pset r, register pset a, register pset b, register pset mask)
{
    register int i = LOOP(a);
    PUTLOOP(r,i); do r[i] = (a[i]&mask[i]) | (b[i]&~mask[i]); while (--i > 0);
    return r;
}

/* set_andp -- compute intersection of sets "a" and "b" , TRUE3 if nonempty */
bool3 set_andp(register pset r, register pset a, register pset b)
{
    register int i = LOOP(a);
    register unsigned int x = 0;
    PUTLOOP(r,i); do {r[i] = a[i] & b[i]; x |= r[i];} while (--i > 0);
    return x != 0;
}

/* setp_empty -- check if the set "a" is empty */
bool3 setp_empty(register pset a)
{
    register int i = LOOP(a);
    do if (a[i]) return FALSE3; while (--i > 0);
    return TRUE3;
}

/* setp_equal -- check if the set "a" equals set "b" */
bool3 setp_equal(register pset a, register pset b)
{
    register int i = LOOP(a);
    do if (a[i] != b[i]) return FALSE3; while (--i > 0);
    return TRUE3;
}

/* setp_disjoint -- check if intersection of "a" and "b" is empty */
bool3 setp_disjoint(register pset a, register pset b)
{
    register int i = LOOP(a);
    do if (a[i] & b[i]) return FALSE3; while (--i > 0);
    return TRUE3;
}

/* setp_implies -- check if "a" implies "b" ("b" contains "a") */
bool3 setp_implies(register pset a, register pset b)
{
    register int i = LOOP(a);
    do if (a[i] & ~b[i]) return FALSE3; while (--i > 0);
    return TRUE3;
}


/* sf_active -- make all members of the set family active */
pset_family sf_active(pset_family A)
{
    register pset p, last;
    foreach_set(A, last, p) {
    	SET(p, ACTIVE);
    }
    A->active_count = A->count;
    return A;
}


/* sf_inactive -- remove all inactive cubes in a set family */
/** MM: len modifikuje parameter A */
/** MM: bola pridana kontrola parametra */
pset_family sf_inactive(pset_family A)
{
    register pset p, last, pdest;
    
    if (A==NULL) return NULL; /** MM: ak chyba parametra */

    pdest = A->data;
    foreach_set(A, last, p) {
    	if (TESTP(p, ACTIVE)) {
    	    if (pdest != p) {
        		INLINEset_copy(pdest, p);
    	    }
    	    pdest += A->wsize;
    	} else {
    	    A->count--;
    	}
    }
    return A;
}


/* sf_copy -- copy a set family */
pset_family sf_copy(pset_family R, pset_family A)
{
    R->sf_size = A->sf_size;
    R->wsize = A->wsize;
/*R->capacity = A->count;*/
/*R->data = REALLOC(unsigned int, R->data, (long) R->capacity * R->wsize);*/
    R->count = A->count;
    R->active_count = A->active_count;
    intcpy(R->data, A->data, (long) A->wsize * A->count);
    return R;
}


/* sf_join -- join A and B into a single set_family */
/** MM: uz kontrola oboch parametrov, ktore NEdealokuje */
/** MM: oprava fatal-u, chyba cez NULL */
pset_family sf_join(pset_family A, pset_family B)
{
    pset_family R;
    
    if ( (A == NULL) || (B == NULL) ) return NULL; /** MM: ak chyba parametra */
    
    long asize = A->count * A->wsize;
    long bsize = B->count * B->wsize;

    if (A->sf_size != B->sf_size) { /** MM: ak chyba fatal */
        fatal2("sf_join: sf_size mismatch");
        return NULL;
    }
    R = sf_new(A->count + B->count, A->sf_size);
    if (R == NULL) return NULL; /** MM: ak chyba alokacie */
    R->count = A->count + B->count;
    R->active_count = A->active_count + B->active_count;
    intcpy(R->data, A->data, asize);
    intcpy(R->data + asize, B->data, bsize);
    return R;
}


/* sf_append -- append the sets of B to the end of A, and dispose of B */
/** MM: oba parametre treba kontrolovat pre NULL! */
/** MM: pri chybe vrati NULL a zmaze vsetky data! (A aj B) */
/** MM: set_family B moze obsahovat aj prazdne data */
pset_family sf_append(pset_family A, pset_family B)
{
    long asize = A->count * A->wsize;
    long bsize = B->count * B->wsize;
    pset tmpdata;

    if ( (B == NULL) || (A == NULL) ) { /** MM: ak je hociktory parameter NULL, je to chyba na vstupe */
        sf_free(A); /** MM: sf_free kontroluje parameter */
        sf_free(B);
        return NULL;
    }
    /** MM: az teraz moze nasledovat povodna vetva */
    
    if (A->sf_size != B->sf_size) {
        fatal2("sf_append: sf_size mismatch");
        sf_free(A); sf_free(B);
        return NULL;
    }
    A->capacity = A->count + B->count;
    tmpdata = REALLOC(unsigned int, A->data, (long) A->capacity * A->wsize);
    if ( tmpdata == NULL && (A->capacity != 0) ){ /** MM: chyba pri rozsirovani pola */
        sf_free(A);
        sf_free(B);
        return NULL;
    }
    /** MM: priradenie dat a pokracovanie v povodnej procedure */
    A->data = tmpdata;
    intcpy(A->data + asize, B->data, bsize);
    A->count += B->count;
    A->active_count += B->active_count;
    sf_free(B);
    return A;
}


/* sf_new -- allocate "num" sets of "size" elements each */
/** MM: vrati NULL pri chybe */
pset_family sf_new(int num, int size)
{   
    pset_family A;
    if (set_family_garbage == NULL) {
    	A = ALLOC(set_family_t, 1);
    	if (A==NULL) return NULL; /** MM: ak chyba */
    } else {
        A = set_family_garbage;
        set_family_garbage = A->next;
    }
    /** MM: tu sa dostanem, ak mam set_family_struct */
    A->sf_size = size;
    A->wsize = SET_SIZE(size);
    A->capacity = num;
    A->data = ALLOC(unsigned int, (long) A->capacity * A->wsize);
    if ( ((A->data) == NULL) && (num!=0) ){ /** MM: chyba */
        sf_free(A);
        return NULL;
    }
    A->count = 0;
    A->active_count = 0;
    return A;
}


/* sf_save -- create a duplicate copy of a set family */
pset_family sf_save(register pset_family A)
{
    if (A==NULL) return NULL; /** MM: ak chyba parametra */
    return sf_copy(sf_new(A->count, A->sf_size), A);
}


/* sf_free -- free the storage allocated for a set family */
/** MM: pridana kontrola ukazatela */
void sf_free(pset_family A)
{
    if (A!=NULL){
        FREE(A->data);
        A->next = set_family_garbage;
        set_family_garbage = A;
    }
}


/* sf_cleanup -- free all of the set families from the garbage list */
void sf_cleanup(void)
{
    register pset_family p, pnext;
    for(p = set_family_garbage; p != (pset_family) NULL; p = pnext) {
    	pnext = p->next;
    	FREE(p);
    }
    set_family_garbage = (pset_family) NULL;
}


/* sf_addset -- add a set to the end of a set family */
/** MM: alokuje pamat a treba kontrolovat aj parameter */
/** MM: modifikuje svoj parameter A! Parameter s je nezmeneny */
/** MM: jej ulohou je vytvorit "novu" set_family, takze pri chybe povodnu zmaze a vrati NULL.
 * povodny parameter ale bude obsahovat neplatny ukazatel!!! */
pset_family sf_addset(pset_family A, const pset s)
{
    register pset p;
    
    if ( (A==NULL) || (s==NULL) ) return NULL;

    if (A->count >= A->capacity) {
        pset tmpdata;
    	A->capacity = A->capacity + A->capacity/2 + 1;
    	tmpdata = REALLOC(unsigned int, A->data, (long) A->capacity * A->wsize);
    	if (tmpdata==NULL){ /** MM: chyba realokacie */
    	   sf_free(A); /** MM: uvolni data a strukturu zaradi do garbage kolekcie */
    	   return NULL;            
        } else A->data = tmpdata;
    }
    p = GETSET(A, A->count++);
    INLINEset_copy(p, s);
    return A;
}

/* sf_delset -- delete a set from a set family */
void sf_delset(pset_family A, int i)
{   (void) set_copy(GETSET(A,i), GETSET(A, --A->count));}

/* sf_print -- print a set_family as a set (list the element numbers) */
/** MM: implicitny vystup do debugoutput */
void sf_print(pset_family A)
{
    if ( (A==NULL) || (debugoutput==NULL) ) return; /** MM: ak chyba parametrov */
    char *ps1(register pset a); /** MM: forward deklaracia funkcie */
    register pset p;
    register int i;
    foreachi_set(A, i, p)
    	fprintf(debugoutput, "A[%d] = %s\n", i, ps1(p));
}

/* ps1 -- convert a set into a printable string */
#define largest_string 120
static char s1[largest_string];

char *ps1(register pset a)
{
    register int i, num, l, len = 0, n = NELEM(a);
    char temp[20];
    bool3 first = TRUE3;

    s1[len++] = '[';
    for(i = 0; i < n; i++)
	if (is_in_set(a,i)) {
	    if (! first)
		s1[len++] = ',';
	    first = FALSE3; num = i;
	    /* Generate digits (reverse order) */
	    l = 0; do temp[l++] = num % 10 + '0'; while ((num /= 10) > 0);
	    /* Copy them back in correct order */
	    do s1[len++] = temp[--l]; while (l > 0);
	    if (len > largest_string-15) {
		s1[len++] = '.'; s1[len++] = '.'; s1[len++] = '.';
		break;
	    }
	}

    s1[len++] = ']';
    s1[len++] = '\0';
    return s1;
}

/* set_adjcnt -- adjust the counts for a set by "weight" */
void
set_adjcnt(register pset a, register int *count, register int weight)
{
    register int i, base;
    register unsigned int val;

    for(i = LOOP(a); i > 0; ) {
	for(val = a[i], base = --i << LOGBPI; val != 0; base++, val >>= 1) {
	    if (val & 1) {
		count[base] += weight;
	    }
	}
    }
}



/* sf_count -- perform a column sum over a set family */
int *sf_count(pset_family A)
{
    register pset p, last;
    register int i, base, *count;
    register unsigned int val;

    count = ALLOC(int, A->sf_size);
    for(i = A->sf_size - 1; i >= 0; i--) {
	count[i] = 0;
    }

    foreach_set(A, last, p) {
	for(i = LOOP(p); i > 0; ) {
	    for(val = p[i], base = --i << LOGBPI; val != 0; base++, val >>= 1) {
		if (val & 1) {
		    count[base]++;
		}
	    }
	}
    }
    return count;
}


/* sf_count_restricted -- perform a column sum over a set family, restricting
 * to only the columns which are in r; also, the columns are weighted by the
 * number of elements which are in each row
 */
int *sf_count_restricted(pset_family A, register pset r)
{
    register pset p;
    register int i, base, *count;
    register unsigned int val;
    int weight;
    pset last;

    count = ALLOC(int, A->sf_size);
    for(i = A->sf_size - 1; i >= 0; i--) {
	count[i] = 0;
    }

    /* Loop for each set */
    foreach_set(A, last, p) {
	weight = 1024 / (set_ord(p) - 1);
	for(i = LOOP(p); i > 0; ) {
	    for(val=p[i]&r[i], base= --i<<LOGBPI; val!=0; base++, val >>= 1) {
		if (val & 1) {
		    count[base] += weight;
		}
	    }
	}
    }
    return count;
}


/*
 *  sf_delc -- delete columns first ... last of A
 */
/** MM: kontroluje parameter, ktory dealokuje a vracia novu strukrutu */
/** MM: chyba cez NULL a dealokacia parametra */
pset_family sf_delc(pset_family A, int first, int last)
{
    return sf_delcol(A, first, last-first + 1);
}


/*
 *  sf_addcol -- add columns to a set family; includes a quick check to see
 *  if there is already enough room (and hence, can avoid copying)
 */
/** MM: pridana kontrola parametra */
/** MM: chyba cez NULL, da sa povedat, ze disposes of A */
pset_family sf_addcol(pset_family A, int firstcol, int n)
{
    int maxsize;
    
    if (A == NULL) return NULL; /** MM: ak chyba parametra */

    /* Check if adding columns at the end ... */
    if (firstcol == A->sf_size) {
    	/* If so, check if there is already enough room */
    	maxsize = BPI * LOOPINIT(A->sf_size);
    	if ((A->sf_size + n) <= maxsize) {
    	    A->sf_size += n;
    	    return A;
    	}
    }
    return sf_delcol(A, firstcol, -n); /** MM: moze vratit aj NULL */
}

/*
 * sf_delcol -- add/delete columns to/from a set family
 *
 *  if n > 0 then n columns starting from firstcol are deleted if n < 0
 *  then n blank columns are inserted starting at firstcol
 *      (i.e., the first new column number is firstcol)
 *
 *  This is done by copying columns in the array which is a relatively
 *  slow operation.
 */
/** MM: kontroluje parameter, ktory dealokuje a vracia novu strukrutu */
/** MM: chyba cez NULL a dealokacia parametra */
pset_family sf_delcol(pset_family A, register int firstcol, register int n)
{
    register pset p, last, pdest;
    register int i;
    pset_family B;
    
    if (A == NULL) return NULL; /** MM: ak chyba parametra */

    B = sf_new(A->count, A->sf_size - n);
    if (B == NULL){ /** MM: ak chyba alokacie */
        sf_free(A);
        return NULL;
    }
    /** MM: pokracuje nezmenena cast funkcie */
    foreach_set(A, last, p) {
    	pdest = GETSET(B, B->count++);
    	INLINEset_clear(pdest, B->sf_size);
    	for(i = 0; i < firstcol; i++)
    	    if (is_in_set(p, i))
    		set_insert(pdest, i);
    	for(i = n > 0 ? firstcol + n : firstcol; i < A->sf_size; i++)
    	    if (is_in_set(p, i))
    		set_insert(pdest, i - n);
    }
    sf_free(A);
    return B;
}


/*
 *  sf_copy_col -- copy column "srccol" from "src" to column "dstcol" of "dst"
 */
/** MM: nic nealokuje a ani nedealokuje */
/** MM: chyba parametra -> navratova hodnota NULL */
pset_family sf_copy_col(pset_family dst, int dstcol, pset_family src, int srccol)
{
    register pset last, p, pdest;
    register int word_test, word_set;
    unsigned int bit_set, bit_test;
    
    if ( (dst==NULL) || (src==NULL) ) return NULL;

    /* CHEAT! form these constants outside the loop */
    word_test = WHICH_WORD(srccol);
    bit_test = 1 << WHICH_BIT(srccol);
    word_set = WHICH_WORD(dstcol);
    bit_set = 1 << WHICH_BIT(dstcol);

    pdest = dst->data;
    foreach_set(src, last, p) {
    	if ((p[word_test] & bit_test) != 0)
    	    pdest[word_set] |= bit_set;
    /*
     *  equivalent code for this is ...
     *	if (is_in_set(p, srccol)) set_insert(pdest, destcol);
     */
    	pdest += dst->wsize;
    }
    return dst;
}



/*
 *  sf_compress -- delete columns from a matrix
 */
/** MM: dealokuje parameter A, parametre uz kontroluje */
/** MM: chyba cez NULL */
pset_family sf_compress(pset_family A, register pset c)
              			/* A will be freed */
{
    register pset p;
    register int i, bcol;
    pset_family B;
    
    if ( (A==NULL) || (c==NULL) ){ /** MM: ak chyba parametrov */
        sf_free(A);
        return NULL;
    }

    /* create a clean set family for the result */
    B = sf_new(A->count, set_ord(c));
    if (B == NULL) { /** MM: ak chyba alokacie */
        sf_free(A);
        return NULL;
    }
    for(i = 0; i < A->count; i++) {
    	p = GETSET(B, B->count++);
    	INLINEset_clear(p, B->sf_size);
    }

    /* copy each column of A which has a 1 in c */
    bcol = 0;
    for(i = 0; i < A->sf_size; i++) {
    	if (is_in_set(c, i)) {
    	    (void) sf_copy_col(B, bcol++, A, i); /** MM: moze sa tu pridat kontrola navratovej hodnoty */
    	}
    }
    sf_free(A);
    return B;
}

/*
 *   sf_permute -- permute the columns of a set_family
 *
 *   permute is an array of integers containing column numbers of A which
 *   are to be retained.
 */
pset_family sf_permute(pset_family A, register int *permute, register int npermute)
{
    pset_family B;
    register pset p, last, pdest;
    register int j;

    B = sf_new(A->count, npermute);
    B->count = A->count;
    foreach_set(B, last, p)
	INLINEset_clear(p, npermute);

    pdest = B->data;
    foreach_set(A, last, p) {
    	for(j = 0; j < npermute; j++)
    	    if (is_in_set(p, permute[j]))
    		set_insert(pdest, j);
    	pdest += B->wsize;
    }
    sf_free(A);
    return B;
}
