Mastering Algorithms With C - Kyle Loudon [55]
Figure 7.1. The associativity of set intersections (property 4) illustrated using a Venn diagram (see the related topics at the end of the chapter)
An interesting result occurs when the difference of one set is taken with either the intersection or union of two others. The resulting behavior is described by DeMorgan's laws:
Interface for Sets
Name
set_init
Synopsis
void set_init(Set *set, int (*match)(const void *key1, const void *key2),
void (*destroy)(void *data));
Return Value
None.
Description
Initializes the set specified by set. This operation must be called for a set before the set can be used with any other operation. The match argument is a function used by various set operations to determine if two members match. It should return 1 if key1 is equal to key2, and otherwise. The destroy argument provides a way to free dynamically allocated data when set_destroy is called. For example, if the set contains data dynamically allocated using malloc, destroy should be set to free to free the data as the set is destroyed. For structured data containing several dynamically allocated members, destroy should be set to a user-defined function that calls free for each dynamically allocated member as well as for the structure itself. For a set containing data that should not be freed, destroy should be set to NULL.
Complexity
O (1)
Name
set_destroy
Synopsis
void set_destroy(Set *set);
Return Value
None.
Description
Destroys the set specified by set. No other operations are permitted after calling set_destroy unless set_init is called again. The set_destroy operation removes all members from a set and calls the function passed as destroy to set_init once for each member as it is removed, provided destroy was not set to NULL.
Complexity
O (n), where n is the number of members in the set.
Name
set_insert
Synopsis
int set_insert(Set *set, const void *data);
Return Value
0if inserting the member is successful, 1 if the member is already in the set, or -1 otherwise.
Description
Inserts a member into the set specified by set. The new member contains a pointer to data, so the memory referenced by data should remain valid as long as the member remains in the set. It is the responsibility of the caller to manage the storage associated with data.
Complexity
O (n), where n is the number of members in the set.
Name
set_remove
Synopsis
int set_remove(Set *set, void **data);
Return Value
0if removing the member is successful, or -1 otherwise.
Description
Removes the member matching data from the set specified by set. Upon return, data points to the data stored in the member that was removed. It is the responsibility of the caller to manage the storage associated with the data.
Complexity
O (n), where n is the number of members in the set.
Name
set_union
Synopsis
int set_union(Set *setu, const Set *set1, const Set *set2);
Return Value
0if computing the union is successful, or -1 otherwise.
Description
Builds a set that is the union of set1 and set2. Upon return, setu contains the union. Because setu points to data in set1 and set2, the data in set1 and set2 must remain valid until setu is destroyed with set_destroy.
Complexity
O (mn), where m and n are the number of members in set1 and set2, respectively.
Name
set_intersection
Synopsis
int set_intersection(Set *seti, const Set *set1, const Set *set2);
Return Value
0if computing the intersection is successful, or -1 otherwise.
Description
Builds a set that is the intersection of set1 and set2. Upon return, seti contains the intersection. Because seti points to data in set1, the data in set1 must remain valid until seti is destroyed with set_destroy.
Complexity
O (mn), where m and n are the number of members in set1 and set2, respectively.
Name
set_difference
Synopsis
int