Mastering Algorithms With C - Kyle Loudon [60]
if (list_ins_next(seti, list_tail(seti), data) != 0) {
set_destroy(seti);
return -1;
}
}
}
return 0;
}
/*****************************************************************************
* *
* ---------------------------- set_difference ---------------------------- *
* *
*****************************************************************************/
int set_difference(Set *setd, const Set *set1, const Set *set2) {
ListElmt *member;
void *data;
/*****************************************************************************
* *
* Initialize the set for the difference. *
* *
*****************************************************************************/
set_init(setd, set1->match, NULL);
/*****************************************************************************
* *
* Insert the members from set1 not in set2. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
if (!set_is_member(set2, list_data(member))) {
data = list_data(member);
if (list_ins_next(setd, list_tail(setd), data) != 0) {
set_destroy(setd);
return -1;
}
}
}
return 0;
}
/*****************************************************************************
* *
* ----------------------------- set_is_member ---------------------------- *
* *
*****************************************************************************/
int set_is_member(const Set *set, const void *data) {
ListElmt *member;
/*****************************************************************************
* *
* Determine if the data is a member of the set. *
* *
*****************************************************************************/
for (member = list_head(set); member != NULL; member = list_next(member)) {
if (set->match(data, list_data(member)))
return 1;
}
return 0;
}
/*****************************************************************************
* *
* ----------------------------- set_is_subset ---------------------------- *
* *
*****************************************************************************/
int set_is_subset(const Set *set1, const Set *set2) {
ListElmt *member;
/*****************************************************************************
* *
* Do a quick test to rule out some cases. *
* *
*****************************************************************************/
if (set_size(set1) > set_size(set2))
return 0;
/*****************************************************************************
* *
* Determine if set1 is a subset of set2. *
* *
*****************************************************************************/
for (member = list_head(set1); member != NULL; member = list_next(member)) {
if (!set_is_member(set2, list_data(member)))
return 0;
}
return 1;
}
/*****************************************************************************
* *
* ------------------------------ set_is_equal ---------------------------- *
* *
*****************************************************************************/
int set_is_equal(const Set *set1, const Set *set2) {
/*****************************************************************************
* *
* Do a quick test to rule out some cases. *
* *
*****************************************************************************/
if (set_size(set1) != set_size(set2))
return 0;
/*****************************************************************************
* *
* Sets of the same size are equal if they are subsets. *
* *
*****************************************************************************/
return set_is_subset(set1, set2);
}
Set Example: Set Covering
Set covering is an optimization problem that nicely models many problems of combinatorics and resource selection. Here is the idea: given a set S and a set P of subsets A 1 to An of S, set C, which is composed of one or more sets from P, is said to cover S if each member in S is contained in at least