src/misc/espresso/gasp.c File Reference

#include "espresso.h"

Include dependency graph for gasp.c:

Go to the source code of this file.

Functions
static pcover	reduce_gasp (pcover F, pcover D)
pcover	expand_gasp (INOUT pcover F, IN pcover D, IN pcover R, IN pcover Foriginal)
void	expand1_gasp (pcover F, pcover D, pcover R, pcover Foriginal, int c1index, pcover *G)
pcover	irred_gasp (pcover F, pcover D, pcover G)
pcover	last_gasp (pcover F, pcover D, pcover R, cost_t *cost)
pcover	super_gasp (pcover F, pcover D, pcover R, cost_t *cost)

---

Function Documentation

void expand1_gasp	(	pcover	F,
		pcover	D,
		pcover	R,
		pcover	Foriginal,
		int	c1index,
		pcover *	G
	)

Definition at line 104 of file gasp.c.

{
    register int c2index;
    register pcube p, last, c2under;
    pcube RAISE, FREESET, temp, *FD, c2essential;
    pcover F1;

    if (debug & EXPAND1) {
        printf("\nEXPAND1_GASP:    \t%s\n", pc1(GETSET(F, c1index)));
    }

    RAISE = new_cube();
    FREESET = new_cube();
    temp = new_cube();

    /* Initialize the OFF-set */
    R->active_count = R->count;
    foreach_set(R, last, p) {
        SET(p, ACTIVE);
    }
    /* Initialize the reduced ON-set, all nonprime cubes become active */
    F->active_count = F->count;
    foreachi_set(F, c2index, c2under) {
        if (c1index == c2index || TESTP(c2under, PRIME)) {
            F->active_count--;
            RESET(c2under, ACTIVE);
        } else {
            SET(c2under, ACTIVE);
        }
    }

    /* Initialize the raising and unassigned sets */
    (void) set_copy(RAISE, GETSET(F, c1index));
    (void) set_diff(FREESET, cube.fullset, RAISE);

    /* Determine parts which must be lowered */
    essen_parts(R, F, RAISE, FREESET);

    /* Determine parts which can always be raised */
    essen_raising(R, RAISE, FREESET);

    /* See which, if any, of the reduced cubes we can cover */
    foreachi_set(F, c2index, c2under) {
        if (TESTP(c2under, ACTIVE)) {
            /* See if this cube can be covered by an expansion */
            if (setp_implies(c2under, RAISE) ||
              feasibly_covered(R, c2under, RAISE, temp)) {
                
                /* See if c1under can expanded to cover c2 reduced against
                 * (F - c1) u c1under; if so, c2 can definitely be removed !
                 */

                /* Copy F and replace c1 with c1under */
                F1 = sf_save(Foriginal);
                (void) set_copy(GETSET(F1, c1index), GETSET(F, c1index));

                /* Reduce c2 against ((F - c1) u c1under) */
                FD = cube2list(F1, D);
                c2essential = reduce_cube(FD, GETSET(F1, c2index));
                free_cubelist(FD);
                sf_free(F1);

                /* See if c2essential is covered by an expansion of c1under */
                if (feasibly_covered(R, c2essential, RAISE, temp)) {
                    (void) set_or(temp, RAISE, c2essential);
                    RESET(temp, PRIME);         /* cube not prime */
                    *G = sf_addset(*G, temp);
                }
                set_free(c2essential);
            }
        }
    }

    free_cube(RAISE);
    free_cube(FREESET);
    free_cube(temp);
}

pcover expand_gasp	(	INOUT pcover	F,
		IN pcover	D,
		IN pcover	R,
		IN pcover	Foriginal
	)

Definition at line 80 of file gasp.c.

{
    int c1index;
    pcover G;

    /* Try to expand each nonprime and noncovered cube */
    G = new_cover(10);
    for(c1index = 0; c1index < F->count; c1index++) {
        expand1_gasp(F, D, R, Foriginal, c1index, &G);
    }
    G = sf_dupl(G);
    G = expand(G, R, /*nonsparse*/ FALSE);      /* Make them prime ! */
    return G;
}

pcover irred_gasp	(	pcover	F,
		pcover	D,
		pcover	G
	)

Definition at line 189 of file gasp.c.

{
    if (G->count != 0)
        F = irredundant(sf_append(F, G), D);
    else
        free_cover(G);
    return F;
}

pcover last_gasp	(	pcover	F,
		pcover	D,
		pcover	R,
		cost_t *	cost
	)

Definition at line 201 of file gasp.c.

{
    pcover G, G1;

    EXECUTE(G = reduce_gasp(F, D), GREDUCE_TIME, G, *cost);
    EXECUTE(G1 = expand_gasp(G, D, R, F), GEXPAND_TIME, G1, *cost);
    free_cover(G);
    EXECUTE(F = irred_gasp(F, D, G1), GIRRED_TIME, F, *cost);
    return F;
}

static pcover reduce_gasp	(	pcover	F,
		pcover	D
	)			[static]

Definition at line 41 of file gasp.c.

{
    pcube p, last, cunder, *FD;
    pcover G;

    G = new_cover(F->count);
    FD = cube2list(F, D);

    /* Reduce cubes of F without replacement */
    foreach_set(F, last, p) {
        cunder = reduce_cube(FD, p);
        if (setp_empty(cunder)) {
            fatal("empty reduction in reduce_gasp, shouldn't happen");
        } else if (setp_equal(cunder, p)) {
            SET(cunder, PRIME);                 /* just to make sure */
            G = sf_addset(G, p);                /* it did not reduce ... */
        } else {
            RESET(cunder, PRIME);               /* it reduced ... */
            G = sf_addset(G, cunder);
        }
        if (debug & GASP) {
            printf("REDUCE_GASP: %s reduced to %s\n", pc1(p), pc2(cunder));
        }
        free_cube(cunder);
    }

    free_cubelist(FD);
    return G;
}

pcover super_gasp	(	pcover	F,
		pcover	D,
		pcover	R,
		cost_t *	cost
	)

Definition at line 216 of file gasp.c.

{
    pcover G, G1;

    EXECUTE(G = reduce_gasp(F, D), GREDUCE_TIME, G, *cost);
    EXECUTE(G1 = all_primes(G, R), GEXPAND_TIME, G1, *cost);
    free_cover(G);
    EXEC(G = sf_dupl(sf_append(F, G1)), "NEWPRIMES", G);
    EXECUTE(F = irredundant(G, D), IRRED_TIME, F, *cost);
    return F;
}