diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2007-10-01 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2007-10-01 08:01:00 -0700 |
commit | 4812c90424dfc40d26725244723887a2d16ddfd9 (patch) | |
tree | b32ace96e7e2d84d586e09ba605463b6f49c3271 /src/misc/espresso/contain.c | |
parent | e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 (diff) | |
download | abc-4812c90424dfc40d26725244723887a2d16ddfd9.tar.gz abc-4812c90424dfc40d26725244723887a2d16ddfd9.tar.bz2 abc-4812c90424dfc40d26725244723887a2d16ddfd9.zip |
Version abc71001
Diffstat (limited to 'src/misc/espresso/contain.c')
-rw-r--r-- | src/misc/espresso/contain.c | 441 |
1 files changed, 441 insertions, 0 deletions
diff --git a/src/misc/espresso/contain.c b/src/misc/espresso/contain.c new file mode 100644 index 00000000..180dceb6 --- /dev/null +++ b/src/misc/espresso/contain.c @@ -0,0 +1,441 @@ +/* + * Revision Control Information + * + * $Source$ + * $Author$ + * $Revision$ + * $Date$ + * + */ +/* + 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. +*/ +pset_family sf_contain(A) +INOUT pset_family A; /* disposes of A */ +{ + int cnt; + pset *A1; + pset_family R; + + A1 = sf_sort(A, descend); /* sort into descending order */ + 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; +} + + +/* + 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 +*/ +pset_family sf_rev_contain(A) +INOUT pset_family A; /* disposes of A */ +{ + int cnt; + pset *A1; + pset_family R; + + A1 = sf_sort(A, ascend); /* sort into ascending order */ + cnt = rm_equal(A1, ascend); /* remove duplicates */ + cnt = rm_rev_contain(A1); /* remove containing sets */ + R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */ + sf_free(A); + return R; +} + + +/* + sf_ind_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. Also maintains a set of row_indices to track which rows + disappear and how the rows end up permuted. +*/ +pset_family sf_ind_contain(A, row_indices) +INOUT pset_family A; /* disposes of A */ +INOUT int *row_indices; /* updated with the new values */ +{ + int cnt; + pset *A1; + pset_family R; + + A1 = sf_sort(A, descend); /* sort into descending order */ + cnt = rm_equal(A1, descend); /* remove duplicates */ + cnt = rm_contain(A1); /* remove contained sets */ + R = sf_ind_unlist(A1, cnt, A->sf_size, row_indices, A->data); + sf_free(A); + return R; +} + + +/* sf_dupl -- delete duplicate sets in a set family */ +pset_family sf_dupl(A) +INOUT pset_family A; /* disposes of A */ +{ + register int cnt; + register pset *A1; + pset_family R; + + A1 = sf_sort(A, descend); /* sort the set family */ + cnt = rm_equal(A1, descend); /* remove duplicates */ + R = sf_unlist(A1, cnt, A->sf_size); /* recreate the set family */ + sf_free(A); + return R; +} + + +/* + 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. +*/ +pset_family sf_union(A, B) +INOUT pset_family A, B; /* disposes of A and B */ +{ + int cnt; + pset_family R; + pset *A1 = sf_list(A), *B1 = sf_list(B), *E1; + + E1 = ALLOC(pset, MAX(A->count, B->count) + 1); + 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; +} + + +/* + dist_merge -- consider all sets to be "or"-ed with "mask" and then + delete duplicates from the set family. +*/ +pset_family dist_merge(A, mask) +INOUT pset_family A; /* disposes of A */ +IN pset mask; /* defines variables to mask out */ +{ + pset *A1; + int cnt; + pset_family R; + + (void) set_copy(cube.temp[0], mask); + A1 = sf_sort(A, d1_order); + cnt = d1_rm_equal(A1, d1_order); + R = sf_unlist(A1, cnt, A->sf_size); + sf_free(A); + return R; +} + + +/* + d1merge -- perform an efficient distance-1 merge of cubes of A +*/ +pset_family d1merge(A, var) +INOUT pset_family A; /* disposes of A */ +IN int var; +{ + return dist_merge(A, cube.var_mask[var]); +} + + + +/* d1_rm_equal -- distance-1 merge (merge cubes which are equal under a mask) */ +int d1_rm_equal(A1, compare) +register pset *A1; /* array of set pointers */ +int (*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 */ + (void) 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 */ +int rm_equal(A1, compare) +INOUT pset *A1; /* updated in place */ +IN int (*compare)(); +{ + 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(A1) +INOUT pset *A1; /* updated in place */ +{ + register pset *pa, *pb, *pcheck, a, b; + pset *pdest = A1; + int last_size = -1; + + /* 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 */ +int rm_rev_contain(A1) +INOUT pset *A1; /* updated in place */ +{ + register pset *pa, *pb, *pcheck, a, b; + pset *pdest = A1; + int last_size = -1; + + /* 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; +} + + +/* rm2_equal -- check two sorted arrays of set pointers for equal cubes */ +int rm2_equal(A1, B1, E1, compare) +INOUT register pset *A1, *B1; /* updated in place */ +OUT pset *E1; +IN int (*compare)(); +{ + 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(A1, B1) +INOUT pset *A1; /* updated in place */ +IN pset *B1; /* 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 */ +pset *sf_sort(A, compare) +IN pset_family A; +IN int (*compare)(); +{ + register pset p, last, *pdest, *A1; + + /* Create a single array pointing to each cube of A */ + pdest = A1 = ALLOC(pset, A->count + 1); + 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((char *) A1, A->count, sizeof(pset), compare); + return A1; +} + + +/* sf_list -- make a list of pointers to the sets in a set family */ +pset *sf_list(A) +IN register pset_family A; +{ + register pset p, last, *pdest, *A1; + + /* Create a single array pointing to each cube of A */ + pdest = A1 = ALLOC(pset, A->count + 1); + 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 */ +pset_family sf_unlist(A1, totcnt, size) +IN pset *A1; +IN int totcnt, size; +{ + register pset pr, p, *pa; + pset_family R = sf_new(totcnt, size); + + R->count = totcnt; + for(pr = R->data, pa = A1; (p = *pa++) != NULL; pr += R->wsize) + INLINEset_copy(pr, p); + FREE(A1); + return R; +} + + +/* sf_ind_unlist -- make a set family out of a list of pointers to sets */ +pset_family sf_ind_unlist(A1, totcnt, size, row_indices, pfirst) +IN pset *A1; +IN int totcnt, size; +INOUT int *row_indices; +IN register pset pfirst; +{ + register pset pr, p, *pa; + register int i, *new_row_indices; + pset_family R = sf_new(totcnt, size); + + R->count = totcnt; + new_row_indices = ALLOC(int, totcnt); + for(pr = R->data, pa = A1, i=0; (p = *pa++) != NULL; pr += R->wsize, i++) { + INLINEset_copy(pr, p); + new_row_indices[i] = row_indices[(p - pfirst)/R->wsize]; + } + for(i = 0; i < totcnt; i++) + row_indices[i] = new_row_indices[i]; + FREE(new_row_indices); + FREE(A1); + return R; +} + + +/* sf_merge -- merge three sorted lists of set pointers */ +pset_family sf_merge(A1, B1, E1, totcnt, size) +INOUT pset *A1, *B1, *E1; /* will be disposed of */ +IN int totcnt, size; +{ + register pset pr, ps, *pmin, *pmid, *pmax; + pset_family R; + pset *temp[3], *swap; + int i, j, n; + + /* Allocate the result set_family */ + R = sf_new(totcnt, size); + 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; + } + } + + FREE(A1); + FREE(B1); + FREE(E1); + return R; +} |