/*
    module: cvrm.c
    Purpose: miscellaneous cover manipulation
	a) verify two covers are equal, check consistency of a cover
	b) unravel a multiple-valued cover into minterms
	c) sort covers
*/

#include "espresso.h"

/** MM: nic nealokuje a nemala by v nej vzniknut chyba */
static void cb_unravel(register pset c, int start, int end, pset startbase, pset_family B1)
{
    pcube base = cube->temp[0], p, last;
    int expansion, place, skip, var, size, offset;
    register int i, j, k, n;

    /* Determine how many cubes it will blow up into, and create a mask
	for those parts that have only a single coordinate
    */
    expansion = 1;
    (void) set_copy(base, startbase);
    for(var = start; var <= end; var++) {
    	if ((size = set_dist(c, cube->var_mask[var])) < 2) {
    	    (void) set_or(base, base, cube->var_mask[var]);
    	} else {
    	    expansion *= size;
    	}
    }
    (void) set_and(base, c, base);

    /* Add the unravelled sets starting at the last element of B1 */
    offset = B1->count;
    B1->count += expansion;
    foreach_remaining_set(B1, last, GETSET(B1, offset-1), p) {
    	INLINEset_copy(p, base);
    }

    place = expansion;
    for(var = start; var <= end; var++) {
    	if ((size = set_dist(c, cube->var_mask[var])) > 1) {
    	    skip = place;
    	    place = place / size;
    	    n = 0;
    	    for(i = cube->first_part[var]; i <= cube->last_part[var]; i++) {
        		if (is_in_set(c, i)) {
        		    for(j = n; j < expansion; j += skip) {
            			for(k = 0; k < place; k++) {
            			    p = GETSET(B1, j+k+offset);
            			    (void) set_insert(p, i);
            			}
        		    }
        		    n += place;
        		}
    	    }
    	}
    }
}

/** MM: kontroluje parameter, ktory dealokuje */
/** MM: chyba cez NULL, inak vracia novu strukturu */
/** MM: start a end uz musia mat spravne hodnoty!!! */
pcover unravel_range(pset_family B, int start, int end)
{
    pcover B1;
    int var, total_size, expansion, size;
    register pcube p, last, startbase = cube->temp[1];

    if (B == NULL){ /** MM: ak chyba parametra */
        return NULL;
    }
    /* Create the starting base for those variables not being unravelled */
    (void) set_copy(startbase, cube->emptyset);
    for(var = 0; var < start; var++)
    	(void) set_or(startbase, startbase, cube->var_mask[var]);
    for(var = end+1; var < cube->num_vars; var++)
    	(void) set_or(startbase, startbase, cube->var_mask[var]);

    /* Determine how many cubes it will blow up into */
    total_size = 0;
    foreach_set(B, last, p) {
    	expansion = 1;
    	for(var = start; var <= end; var++)
    	    if ((size = set_dist(p, cube->var_mask[var])) >= 2)
    		if ((expansion *= size) > 1000000){ /** MM: ak chyba */
    		    fatal2("unreasonable expansion in unravel");
    		    sf_free(B);
    		    return NULL;
            }
    	total_size += expansion;
    }

    /* We can now allocate a cover of exactly the correct size */
    B1 = new_cover(total_size);
    if (B1 == NULL) { /** MM: ak chyba */
        sf_free(B);
        return NULL;
    }
    foreach_set(B, last, p) {
    	cb_unravel(p, start, end, startbase, B1);
    }
    free_cover(B);
    return B1;
}


pcover unravel(pset_family B, int start)
{
    return unravel_range(B, start, cube->num_vars-1);
}

/* lex_sort -- sort cubes in a standard lexical fashion */
/** MM: disposes parameter, ktory kontroluje */
/** MM: vracia novu strukturu */
pcover lex_sort(pset_family T)
{
    if (T==NULL) return NULL; /** MM: ak chyba parametra */
    
    pcover T1 = sf_unlist(sf_sort(T, lex_order), T->count, T->sf_size); /** MM: vsetky vnorene funkcie si poradia s NULL */
    free_cover(T);
    return T1; /** MM: chybu si musi osetri volajuci */
}

/*  mini_sort -- sort cubes according to the heuristics of mini */
/** MM: disposes of F */
/** MM: zatial vnutorne neopravena!!! */
pcover mini_sort(pset_family F, int (*compare) (const void *a, const void *b) )
{
    register int *count, cnt, n = cube->size, i;
    register pcube p, last;
    pcover F_sorted;
    pcube *F1;

    /* Perform a column sum over the set family */
    count = sf_count(F);

    /* weight is "inner product of the cube and the column sums" */
    foreach_set(F, last, p) {
    	cnt = 0;
    	for(i = 0; i < n; i++)
    	    if (is_in_set(p, i))
        		cnt += count[i];
    	PUTSIZE(p, cnt);
    }
    FREE(count);

    /* use qsort to sort the array */
    qsort((void *) (F1 = sf_list(F)), F->count, sizeof(pcube), compare);
    F_sorted = sf_unlist(F1, F->count, F->sf_size);
    free_cover(F);

    return F_sorted;
}


/* sort_reduce -- Espresso strategy for ordering the cubes before reduction */
pcover sort_reduce(pset_family T)
{
    register pcube p, last, largest = NULL;
    register int bestsize = -1, size, n = cube->num_vars;
    pcover T_sorted;
    pcube *T1;

    if (T->count == 0)
	return T;

    /* find largest cube */
    foreach_set(T, last, p)
	if ((size = set_ord(p)) > bestsize)
	    largest = p, bestsize = size;

    foreach_set(T, last, p)
	PUTSIZE(p, ((n - cdist(largest,p)) << 7) + MIN(set_ord(p),127));

    qsort((void *) (T1 = sf_list(T)), T->count, sizeof(pcube), descend);
    T_sorted = sf_unlist(T1, T->count, T->sf_size);
    free_cover(T);

    return T_sorted;
}
/** MM: modifikuje F, ktore posle aj ako navrat */
/** MM: zatial vnutorne neopravena!!! */
pcover random_order(register pset_family F)
{
    pset temp;
    register int i, k;

    temp = set_new(F->sf_size);
    for(i = F->count - 1; i > 0; i--) {
    	/* Choose a random number between 0 and i */
    	k = rand() % i;
    	/* swap sets i and k */
    	set_copy(temp, GETSET(F, k));
    	set_copy(GETSET(F, k), GETSET(F, i));
    	set_copy(GETSET(F, i), temp);
    }
    set_free(temp);
    return F;
}

/*
 *  cubelist_partition -- take a cubelist T and see if it has any components;
 *  if so, return cubelist's of the two partitions A and B; the return value
 *  is the size of the partition; if not, A and B
 *  are undefined and the return value is 0
 */
int cubelist_partition(pset *T, pset **A, pset **B, unsigned int comp_debug)
         			/* a list of cubes */
               			/* cubelist of partition and remainder */
                        
{
    register pcube *T1, p, seed, cof;
    pcube *A1, *B1;
    bool3 change;
    int count, numcube;

    numcube = CUBELISTSIZE(T);

    /* Mark all cubes -- covered cubes belong to the partition */
    for(T1 = T+2; (p = *T1++) != NULL; ) {
	RESET(p, COVERED);
    }

    /*
     *  Extract a partition from the cubelist T; start with the first cube as a
     *  seed, and then pull in all cubes which share a variable with the seed;
     *  iterate until no new cubes are brought into the partition.
     */
    seed = set_save(T[2]);
    cof = T[0];
    SET(T[2], COVERED);
    count = 1;

    do {
	change = FALSE3;
	for(T1 = T+2; (p = *T1++) != NULL; ) {
	    if (! TESTP(p, COVERED) && ccommon(p, seed, cof)) {
		INLINEset_and(seed, seed, p);
		SET(p, COVERED);
		change = TRUE3;
		count++;
	    }
	
	}
    } while (change);

    set_free(seed);

    if (comp_debug) {
    	if (debugoutput) fprintf(debugoutput, "COMPONENT_REDUCTION: split into %d %d\n", count, numcube - count);
    }

    if (count != numcube) {
	/* Allocate and setup the cubelist's for the two partitions */
	*A = A1 = ALLOC(pcube, numcube+3);
	*B = B1 = ALLOC(pcube, numcube+3);
	(*A)[0] = set_save(T[0]);
	(*B)[0] = set_save(T[0]);
	A1 = *A + 2;
	B1 = *B + 2;

	/* Loop over the cubes in T and distribute to A and B */
	for(T1 = T+2; (p = *T1++) != NULL; ) {
	    if (TESTP(p, COVERED)) {
		*A1++ = p;
	    } else {
		*B1++ = p;
	    }
	}

	/* Stuff needed at the end of the cubelist's */
	*A1++ = NULL;
	(*A)[1] = (pcube) A1;
	*B1++ = NULL;
	(*B)[1] = (pcube) B1;
    }

    return numcube - count;
}

/*
 *  quick cofactor against a single output function
 */
/** MM: chyba cez NULL */
/** MM: uz kontroluje parameter, ktory nedealokuje */
pcover cof_output(pset_family T, register int i)
{
    pcover T1;
    register pcube p, last, pdest, mask;
    
    if (T == NULL) return NULL; /** MM: ak chyba parametra */

    mask = cube->var_mask[cube->output];
    T1 = new_cover(T->count);
    if (T1 == NULL) return NULL; /** MM: ak chyba alokacie */
    foreach_set(T, last, p) {
    	if (is_in_set(p, i)) {
    	    pdest = GETSET(T1, T1->count++);
    	    INLINEset_or(pdest, p, mask);
    	    RESET(pdest, PRIME);
    	}
    }
    return T1;
}


/*
 *  quick intersection against a single output function
 */
pcover uncof_output(pset_family T, int i)
{
    register pcube p, last, mask;

    if (T == NULL) {
	return T;
    }

    mask = cube->var_mask[cube->output];
    foreach_set(T, last, p) {
	INLINEset_diff(p, p, mask);
	set_insert(p, i);
    }
    return T;
}


/*
 *  A generic routine to perform an operation for each output function
 *
 *  func() is called with a PLA for each output function (with the output
 *  part effectively removed).
 *  func1() is called after reforming the equivalent output function
 *
 *  Each function returns TRUE3 if process is to continue
 */
/** MM: Each function returns TRUE3 if process is to continue a -1, ak nastala chyba */
/** MM: int pre indikaciu chyby; -1 pre chybu */
int foreach_output_function(pPLA PLA, int (*func) (pPLA PLA, int i), int (*func1) (pPLA PLA, int i) )
{
    pPLA PLA1;
    int i, tmp;

    /* Loop for each output function */
    for(i = 0; i < cube->part_size[cube->output]; i++) {
    
    	/* cofactor on the output part */
    	PLA1 = new_PLA();
    	PLA1->F = cof_output(PLA->F, i + cube->first_part[cube->output]);
    	PLA1->R = cof_output(PLA->R, i + cube->first_part[cube->output]);
    	PLA1->D = cof_output(PLA->D, i + cube->first_part[cube->output]);
    
    	/* Call a routine to do something with the cover */
    	tmp = (*func)(PLA1, i);
    	if (tmp == 0) {
    	    free_PLA(PLA1);
    	    return 0;
    	} else if (tmp==-1){ /** MM: ak chyba v so_espresso alebo so_both_do_espresso */
            free_PLA(PLA1);
            return -1;
        }
        /** MM: inak sa pokracuje */
    
    	/* intersect with the particular output part again */
    	PLA1->F = uncof_output(PLA1->F, i + cube->first_part[cube->output]);
    	PLA1->R = uncof_output(PLA1->R, i + cube->first_part[cube->output]);
    	PLA1->D = uncof_output(PLA1->D, i + cube->first_part[cube->output]);
    
    	/* Call a routine to do something with the final result */
    	/** MM: tuto funkciu netreba kontrolovat na chybu [so_save, so_both_save neboli upravovane]*/
    	if ( (*func1)(PLA1, i) == 0) {
    	    free_PLA(PLA1);
    	    return 0;
        }
    	
    
    	/* Cleanup for next go-around */
    	free_PLA(PLA1);
    	

    }
    return 0;
}

static pcover Fmin;
static pcube phase;

/*
 *  minimize each output function individually
 */
/** MM: kontroluje foreach_output_function */
/** MM: PLA by pri chybe mohlo byt nezmenene */
/** MM: zmenene na int kvoli indikacii chyby */
int so_espresso(pPLA PLA, int strategy)
{
    bool3 tmp = skip_make_sparse; /** MM: zaloha nastavenia */
    int tmp2;
        
    Fmin = new_cover(PLA->F->count);
    if (Fmin==NULL) return -1; /** MM: ak chyba alokacie */
    if (strategy == 0) {
    	tmp2 = foreach_output_function(PLA, so_do_espresso, so_save);
    } else {
    	tmp2 = foreach_output_function(PLA, so_do_exact, so_save);
    }
    if (tmp2 == -1){ /** MM: ak chyba foreach_output_function() */
        sf_free(Fmin);
        skip_make_sparse = tmp;
        return -1;
    }
    sf_free(PLA->F);
    PLA->F = Fmin;
    
    skip_make_sparse = tmp;
    return 0;
}


/*
 *  minimize each output function, choose function or complement based on the
 *  one with the fewer number of terms
 */
/** MM: kontroluje foreach_output_function */
/** MM: PLA by pri chybe mohlo byt nezmenene */
/** MM: zmenene na int pre indikaciu chyby */
int so_both_espresso(pPLA PLA, int strategy)
{
    bool3 tmp = skip_make_sparse; /** MM: zaloha nastavenia */
    int tmp2;
    
    phase = set_save(cube->fullset);
    Fmin = new_cover(PLA->F->count);
    if (strategy == 0) {
    	tmp2 = foreach_output_function(PLA, so_both_do_espresso, so_both_save);
    } else {
    	tmp2 = foreach_output_function(PLA, so_both_do_exact, so_both_save);
    }
    if (tmp2 == -1){ /** MM: ak chyba foreach_output_function() */
        sf_free(Fmin);
        FREE(phase);
        skip_make_sparse = tmp;
        return -1;
    }
    
    sf_free(PLA->F);
    PLA->F = Fmin;
	FREE(PLA->phase); /** MM: pridane kvoli memory-leakom */
    PLA->phase = phase;
    
    skip_make_sparse = tmp;
    return 0;
}


/** MM: opravene espresso(); ak chyba, tak -1 a PLA nie je modifokovane */
/** MM: vrati 1, ak sa ma este pokracovat */
int so_do_espresso(pPLA PLA, int i)
{
    char word[32];
    bool3 tmp = skip_make_sparse; /** MM: zaloha nastaveni */
    bool3 tmp2 = unwrap_onset;

    /* minimize the single-output function (on-set) */
    skip_make_sparse = 1;
    (void) snprintf(word, sizeof(word), "ESPRESSO-POS(%d)", i); /** MM: zmenene na secure version */
    EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F); /** MM: kontrola chyby ponechana na zaver */
    skip_make_sparse = tmp; /** MM: obnova nastaveni */
    unwrap_onset = tmp2;
    if (PLA->F==NULL) return -1; /** MM: ak chyba v espresso() */
    
    return 1; /** MM: funkcia vrati 1 (TRUE3) ak sa ma este pokracovat */
}

/** MM: kontroluje minimize_exact; pri chybe vrati -1 */
/** MM: vrati 1, ak sa ma este pokracovat */
int so_do_exact(pPLA PLA, int i)
{
    char word[32];
    bool3 tmp = skip_make_sparse; /** MM: zaloha stareho nastavenia */

    /* minimize the single-output function (on-set) */
    skip_make_sparse = 1;
    (void) snprintf(word, sizeof(word), "EXACT-POS(%d)", i); /** MM: zmenene na secure version */
    EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F);
    skip_make_sparse = tmp;
    if (PLA->F==NULL){ /** MM: ak chyba v minimize_exact, PLA->F je uz dealokovane */
        return -1;
    }

    return 1;
}


/*ARGSUSED*/
int so_save(pPLA PLA, int i)
{
    Fmin = sf_append(Fmin, PLA->F);	/* disposes of PLA->F */
    PLA->F = NULL;
    return 1;
}

/** MM: opravene espresso(); ak chyba, tak -1 a PLA je modifikovane */
/** MM: vrati 1, ak sa ma este pokracovat */
int so_both_do_espresso(pPLA PLA, int i)
{
    char word[32];
    bool3 tmp = skip_make_sparse; /** MM: zaloha nastaveni */

    /* minimize the single-output function (on-set) */
    (void) snprintf(word, sizeof(word), "ESPRESSO-POS(%d)", i); /** MM: zmenene na secure version */
    skip_make_sparse = 1;
    EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F);
    if (PLA->F==NULL){ /** MM: ak chyba v espresso() */
        skip_make_sparse = tmp; /** MM: obnova nastaveni */
        return -1;
    }
    /* minimize the single-output function (off-set) */
    (void) snprintf(word, sizeof(word), "ESPRESSO-NEG(%d)", i); /** MM: zmenene na secure version */
    skip_make_sparse = 1;
    EXEC_S(PLA->R = espresso(PLA->R, PLA->D, PLA->F), word, PLA->R);    
    skip_make_sparse = tmp; /** MM: obnova nastaveni */
    
    if (PLA->R==NULL) return -1; /** MM: ak chyba v espresso() */

    return 1;
}

/** MM: kontroluje minimize_exact; pri chybe vrati -1 */
int so_both_do_exact(pPLA PLA, int i)
{
    char word[32];
    bool3 tmp = skip_make_sparse; /** MM: zaloha stareho nastavenia */

    /* minimize the single-output function (on-set) */
    (void) snprintf(word, sizeof(word), "EXACT-POS(%d)", i); /** MM: zmenene na secure version */
    skip_make_sparse = 1;
    EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F);
    if (PLA->F==NULL){ /** MM: ak chyba v minimize_exact, PLA->F je uz dealokovane */
        skip_make_sparse = tmp;
        return -1;
    }

    /* minimize the single-output function (off-set) */
    (void) snprintf(word, sizeof(word), "EXACT-NEG(%d)", i); /** MM: zmenene na secure version */
    skip_make_sparse = 1;
    EXEC_S(PLA->R = minimize_exact(PLA->R, PLA->D, PLA->F, 1), word, PLA->R);
    if (PLA->R==NULL){ /** MM: ak chyba v minimize_exact, PLA->R je uz dealokovane */
        skip_make_sparse = tmp;
        return -1;
    }

    skip_make_sparse = tmp;

    return 1;
}


int so_both_save(pPLA PLA, int i)
{
    if (PLA->F->count > PLA->R->count) {
	sf_free(PLA->F);
	PLA->F = PLA->R;
	PLA->R = NULL;
	i += cube->first_part[cube->output];
	set_remove(phase, i);
    } else {
	sf_free(PLA->R);
	PLA->R = NULL;
    }
    Fmin = sf_append(Fmin, PLA->F);
    PLA->F = NULL;
    return 1;
}
