| /* | |
| 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; | |
| 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 */ | |
| 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; | |
| } |