/*
    contain.c -- set containment routines

    These are complex routines for performing containment over a
    family of sets, but they have the advantage of being much faster
    than a straightforward n*n routine.

    First the cubes are sorted by size, and as a secondary key they are
    sorted so that if two cubes are equal they end up adjacent.  We can
    than quickly remove equal cubes from further consideration by
    comparing each cube to its neighbor.  Finally, because the cubes
    are sorted by size, we need only check cubes which are larger (or
    smaller) than a given cube for containment.
*/

#include "espresso.h"


/*
    sf_contain -- perform containment on a set family (delete sets which
    are contained by some larger set in the family).  No assumptions are
    made about A, and the result will be returned in decreasing order of
    set size.
*/
/** MM: uz kontroluje parameter, ktory dealokuje */
/** MM: chyba cez NULL */
pset_family sf_contain(pset_family A)
                                /* disposes of A */
{
    int cnt;
    pset *A1;
    pset_family R;
    
    if (A == NULL) return NULL; /** MM: ak chyba parametra */

    A1 = sf_sort(A, descend);           /* sort into descending order */
    if (A1 == NULL) { /** MM: ak chyba */
        sf_free(A);
        return NULL;
    }
    cnt = rm_equal(A1, descend);        /* remove duplicates */
    cnt = rm_contain(A1);               /* remove contained sets */
    R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */
    sf_free(A);
    return R; /** MM: ak chyba, netreba nic robit - volajuci si to musi zistit cez navratovu hodnotu */
}


/*
    sf_rev_contain -- perform containment on a set family (delete sets which
    contain some smaller set in the family).  No assumptions are made about
    A, and the result will be returned in increasing order of set size
*/
/** MM: maze A, ktore uz kontroluje */
/** MM: vracia novu strukturu */
pset_family sf_rev_contain(pset_family A)
                                /* disposes of A */
{
    int cnt;
    pset *A1;
    pset_family R;
    
    if (A == NULL) return NULL; /** MM: kontrola parametra A */

    A1 = sf_sort(A, ascend);            /* sort into ascending order */
    if (A1 == NULL) { /** MM: ak chyba */
        sf_free(A);
        return NULL;
    }
    cnt = rm_equal(A1, ascend);         /* remove duplicates */
    cnt = rm_rev_contain(A1);           /* remove containing sets */
    if (cnt == -1) { /** MM: ak chyba; tu by sa nemala vyskytnut */
        sf_free(A);
        FREE(A1);
        return NULL;
    }
    R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */
    sf_free(A);
    
    return R; /** MM: chybne R si musi osetrit volajuci */
}

/* sf_dupl -- delete duplicate sets in a set family */
/** MM: dealokuje parameter, ktory uz kontroluje */
/** MM: chyba cez NULL, vracia novu strukturu */
pset_family sf_dupl(pset_family A)
                                /* disposes of A */
{
    register int cnt;
    register pset *A1;
    pset_family R;
    
    if (A == NULL) return NULL; /** MM: ak chyba parametra */

    A1 = sf_sort(A, descend);           /* sort the set family */
    if (A1 == NULL) return NULL; /** MM: ak chyba alokacie pamate */
    cnt = rm_equal(A1, descend);        /* remove duplicates */
    R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */
    sf_free(A);
    return R; /** MM: chybne R si musi osetrit volajuci */
}


/*
    sf_union -- form the contained union of two set families (delete
    sets which are contained by some larger set in the family).  A and
    B are assumed already sorted in decreasing order of set size (and
    the SIZE field is assumed to contain the set size), and the result
    will be returned sorted likewise.
*/
/** MM: uz kontroluje parametrem ktore dealokuje */
/** MM: chyba cez NULL */
pset_family sf_union(pset_family A, pset_family B)
                                /* disposes of A and B */
{
    int cnt;
    pset_family R;
    pset *A1 = sf_list(A), *B1 = sf_list(B), *E1;
    if ( (A1==NULL) || (B1==NULL) ) goto cleanup; /** MM: spaja kontrolu parametrov a aj prvy vypocet; vsetky funkcie si uz poradia s NULL */
    E1 = ALLOC(pset, MAX(A->count, B->count) + 1);
    if (E1==NULL) goto cleanup; /** MM: ak chyba alokacie */
    cnt = rm2_equal(A1, B1, E1, descend);
    cnt += rm2_contain(A1, B1) + rm2_contain(B1, A1);
    R = sf_merge(A1, B1, E1, cnt, A->sf_size);
    sf_free(A); sf_free(B);
    return R; /** chybu si pozrie volajuci; tu na nu nie je potrebne reagovat */
    
cleanup:
    FREE(A1); 
    FREE(B1); 
    sf_free(A); 
    sf_free(B); 
    return NULL;
}

/** MM: specialna verzia pre -Dunion */
/** MM: uz kontroluje parametrem ktore NEdealokuje */
/** MM: chyba cez NULL */
pset_family sf_union_no_dispose(pset_family A, pset_family B)
{
    int cnt;
    pset_family R;
    pset *A1 = sf_list(A), *B1 = sf_list(B), *E1;
    if ( (A1==NULL) || (B1==NULL) ) goto cleanup; /** MM: spaja kontrolu parametrov a aj prvy vypocet; vsetky funkcie si uz poradia s NULL */
    E1 = ALLOC(pset, MAX(A->count, B->count) + 1);
    if (E1==NULL) goto cleanup; /** MM: ak chyba alokacie */
    cnt = rm2_equal(A1, B1, E1, descend);
    cnt += rm2_contain(A1, B1) + rm2_contain(B1, A1);
    R = sf_merge(A1, B1, E1, cnt, A->sf_size);
    return R; /** chybu si pozrie volajuci; tu na nu nie je potrebne reagovat */
    
cleanup:
    FREE(A1); 
    FREE(B1); 
    return NULL;
}


/*
    dist_merge -- consider all sets to be "or"-ed with "mask" and then
    delete duplicates from the set family.
*/
/** MM: dealokuje parameter A, ktory uz kontroluje */
/** MM: chyba cez NULL */
pset_family dist_merge(pset_family A, pset mask)
                                /* disposes of A */
                                /* mask defines variables to mask out */
{
    pset *A1;
    int cnt;
    pset_family R;
    
    if (A == NULL) return NULL; /** MM: ak chyba parametra */

    set_copy(cube->temp[0], mask);
    A1 = sf_sort(A, d1_order);
    if (A1 == NULL) { /** MM: ak chyba */
        sf_free(A);
        return NULL; 
    }
    cnt = d1_rm_equal(A1, d1_order);
    R = sf_unlist(A1, cnt, A->sf_size);
    sf_free(A);
    return R; /** MM: ak chyba, tak aj tak sa vrati R - volajuci si skontroluje hodnotu tak ci tak */
}


/*
    d1merge -- perform an efficient distance-1 merge of cubes of A
*/
/** MM: uz kontroluje parameter, ktory dealokuje */
pset_family d1merge(pset_family A, int var)
                                /* disposes of A */
           
{
    if (A == NULL) return NULL;
    return dist_merge(A, cube->var_mask[var]);
}



/* d1_rm_equal -- distance-1 merge (merge cubes which are equal under a mask) */
/** MM: nealokuje */
int d1_rm_equal(register pset *A1, int (*compare) (const void *a, const void *b) )
                  				/* A1 = array of set pointers */
                 				/* compare = comparison function */
{
    register int i, j, dest;

    dest = 0;
    if (A1[0] != (pcube) NULL) {
    	for(i = 0, j = 1; A1[j] != (pcube) NULL; j++)
    	    if ( (*compare)(&A1[i], &A1[j]) == 0) {
        		/* if sets are equal (under the mask) merge them */
        		set_or(A1[i], A1[i], A1[j]);
    	    } else {
        		/* sets are unequal, so save the set i */
        		A1[dest++] = A1[i];
        		i = j;
    	    }
    	A1[dest++] = A1[i];
    }
    A1[dest] = (pcube) NULL;
    return dest;
}


/* rm_equal -- scan a sorted array of set pointers for duplicate sets */
/** MM: len meni prvky pola A1 */
int rm_equal(pset *A1, int (*compare) (const void *a, const void *b) )
                                /* A1 updated in place */                   
{
    register pset *p, *pdest = A1;

    if (*A1 != NULL) {                  /* If more than one set */
    	for(p = A1+1; *p != NULL; p++)
    	    if ((*compare)(p, p-1) != 0)
    		*pdest++ = *(p-1);
    	*pdest++ = *(p-1);
    	*pdest = NULL;
    }
    return pdest - A1;
}


/* rm_contain -- perform containment over a sorted array of set pointers */
int rm_contain(pset *A1)
                                /* updated in place */
{
    register pset *pa, *pb, *pcheck, a, b;
    pset *pdest = A1;
    int last_size = -1;
    pcheck = A1; /* just in case of untrue condition */

    /* Loop for all cubes of A1 */
    for(pa = A1; (a = *pa++) != NULL; ) {
	/* Update the check pointer if the size has changed */
	if (SIZE(a) != last_size)
	    last_size = SIZE(a), pcheck = pdest;
	for(pb = A1; pb != pcheck; ) {
	    b = *pb++;
	    INLINEsetp_implies(a, b, /* when_false => */ continue);
	    goto lnext1;
	}
	/* set a was not contained by some larger set, so save it */
	*pdest++ = a;
    lnext1: ;
    }

    *pdest = NULL;
    return pdest - A1;
}


/* rm_rev_contain -- perform rcontainment over a sorted array of set pointers */
/** MM: len upravuje polia dane ako parameter */
/** MM: navratova hodnota je -1 v pripade chyby parametra */
int rm_rev_contain(pset *A1) /* A1 updated in place */
{
    register pset *pa, *pb, *pcheck, a, b;
    pset *pdest = A1;
    int last_size = -1;
    pcheck = A1; /* just in case of untrue condition */
    
    if (A1 == NULL) return -1; /** MM: ak chyba parametra */

    /* Loop for all cubes of A1 */
    for(pa = A1; (a = *pa++) != NULL; ) {
    	/* Update the check pointer if the size has changed */
    	if (SIZE(a) != last_size)
    	    last_size = SIZE(a), pcheck = pdest;
    	for(pb = A1; pb != pcheck; ) {
    	    b = *pb++;
    	    INLINEsetp_implies(b, a, /* when_false => */ continue);
    	    goto lnext1;
    	}
    	/* the set a did not contain some smaller set, so save it */
    	*pdest++ = a;
lnext1: ;
    }

    *pdest = NULL;
    return pdest - A1; /** MM: return value je vzdy vacsia ako -1 */
}


/* rm2_equal -- check two sorted arrays of set pointers for equal cubes */
int rm2_equal(register pset *A1, register pset *B1, pset *E1, int (*compare) (const void *a, const void *b) )
                                        /* updated in place */
{
    register pset *pda = A1, *pdb = B1, *pde = E1;

    /* Walk through the arrays advancing pointer to larger cube */
    for(; *A1 != NULL && *B1 != NULL; )
	switch((*compare)(A1, B1)) {
	    case -1:    /* "a" comes before "b" */
		*pda++ = *A1++; break;
	    case 0:     /* equal cubes */
		*pde++ = *A1++; B1++; break;
	    case 1:     /* "a" is to follow "b" */
		*pdb++ = *B1++; break;
	}

    /* Finish moving down the pointers of A and B */
    while (*A1 != NULL)
	*pda++ = *A1++;
    while (*B1 != NULL)
	*pdb++ = *B1++;
    *pda = *pdb = *pde = NULL;

    return pde - E1;
}


/* rm2_contain -- perform containment between two arrays of set pointers */
int rm2_contain(pset *A1, pset *B1)
                                /* updated in place */
                                /* unchanged */
{
    register pset *pa, *pb, a, b, *pdest = A1;

    /* for each set in the first array ... */
    for(pa = A1; (a = *pa++) != NULL; ) {
	/* for each set in the second array which is larger ... */
	for(pb = B1; (b = *pb++) != NULL && SIZE(b) > SIZE(a); ) {
	    INLINEsetp_implies(a, b, /* when_false => */ continue);
	    /* set was contained in some set of B, so don't save pointer */
	    goto lnext1;
	}
	/* set wasn't contained in any set of B, so save the pointer */
	*pdest++ = a;
    lnext1: ;
    }

    *pdest = NULL;                      /* sentinel */
    return pdest - A1;                  /* # elements in A1 */
}



/* sf_sort -- sort the sets of A */
/** MM: parameter A nemeni, vracia nove pole */
pset *sf_sort(pset_family A, int (*compare) (const void *a, const void *b) )
{
    register pset p, last, *pdest, *A1;
    
    if (A == NULL) return NULL; /** MM: ak chyba parametra */

    /* Create a single array pointing to each cube of A */
    pdest = A1 = ALLOC(pset, A->count + 1);
    if (A1 == NULL) return NULL; /** MM: ak chyba */
    /** MM: pokracuje nezmenena vetva programu */
    foreach_set(A, last, p) {
    	PUTSIZE(p, set_ord(p));         /* compute the set size */
    	*pdest++ = p;                   /* save the pointer */
    }
    *pdest = NULL;                      /* Sentinel -- never seen by sort */

    /* Sort cubes by size */
    qsort((void *) A1, A->count, sizeof(pset), compare);
    return A1;
}


/* sf_list -- make a list of pointers to the sets in a set family */
/** MM: pridana kontrola parametra, chybu indikuje NULL */
/** MM: vyraba novu strukturu, parameter nedealokuje */
pset *sf_list(register pset_family A)
{
    register pset p, last, *pdest, *A1;
    
    if (A == NULL) return NULL;

    /* Create a single array pointing to each cube of A */
    pdest = A1 = ALLOC(pset, A->count + 1);
    if (A1 == NULL) return NULL; /** MM: ak chyba */
    foreach_set(A, last, p)
    	*pdest++ = p;                   /* save the pointer */
    *pdest = NULL;                      /* Sentinel */
    return A1;
}


/* sf_unlist -- make a set family out of a list of pointers to sets */
/** MM: A1 na konci maze, vracia novu strukturu */
pset_family sf_unlist(pset *A1, int totcnt, int size)
{
    register pset pr, p, *pa;
    
    if (A1 == NULL) return NULL; /** MM: ak chyba parametra */
    /** MM: parameter musi byt nieco neNULL, lebo sa ocakava pole ukazatelov a for() cyklus s tym pocita */
    
    pset_family R = sf_new(totcnt, size);
    if (R == NULL) { /** MM: ak chyba alokacie */
        FREE(A1);
        return NULL; 
    }

    R->count = totcnt;
    for(pr = R->data, pa = A1; (p = *pa++) != NULL; pr += R->wsize)
    	INLINEset_copy(pr, p);
    FREE(A1); /** MM: zmazanie zoznamu ukazatelov na sety; nie setov samotnych!!! */
    return R;
}


/* sf_merge -- merge three sorted lists of set pointers */
/** MM: uz kontroluje parametre, ktore dealokuje */
/** MM: chyba cez NULL */
pset_family sf_merge(pset *A1, pset *B1, pset *E1, int totcnt, int size)
                                        /* A1, B1, E1 will be disposed of */
{
    register pset pr, ps, *pmin, *pmid, *pmax;
    pset_family R = NULL; /** MM: pociatocna inicializacia */
    pset *temp[3], *swap;
    int i, j, n;
    
    if ( (A1==NULL) || (B1==NULL) || (E1==NULL) ) goto cleanup; /** MM: ak chyba alokacie */

    /* Allocate the result set_family */
    R = sf_new(totcnt, size);
    if (R==NULL) goto cleanup; /** MM: ak chyba alokacie */
    R->count = totcnt;
    pr = R->data;

    /* Quick bubble sort to order the top member of the three arrays */
    n = 3;  temp[0] = A1;  temp[1] = B1;  temp[2] = E1;
    for(i = 0; i < n-1; i++)
    	for(j = i+1; j < n; j++)
    	    if (desc1(*temp[i], *temp[j]) > 0) {
        		swap = temp[j];
        		temp[j] = temp[i];
        		temp[i] = swap;
    	    }
    pmin = temp[0];  pmid = temp[1];  pmax = temp[2];

    /* Save the minimum element, then update pmin, pmid, pmax */
    while (*pmin != (pset) NULL) {
    	ps = *pmin++;
    	INLINEset_copy(pr, ps);
    	pr += R->wsize;
    	if (desc1(*pmin, *pmax) > 0) {
    	    swap = pmax; pmax = pmin; pmin = pmid; pmid = swap;
    	} else if (desc1(*pmin, *pmid) > 0) {
    	    swap = pmin; pmin = pmid; pmid = swap;
    	}
    }

cleanup: /** MM: spolocny epilog pre vsetky vetvy na usetrenie miesta */
    FREE(A1);
    FREE(B1);
    FREE(E1);
    return R;
}
