-
-
Save PotatoPope/b733f7da43c97571572a89fca350e9e0 to your computer and use it in GitHub Desktop.
set
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdlib.h> | |
#include "common.h" | |
#include "tree.h" | |
#include "set.h" | |
/* | |
* The type of sets. | |
*/ | |
struct set { | |
tree_t *tree; | |
cmpfunc_t cmpfunc; | |
}; | |
/* | |
* Creates a new set using the given comparison function | |
* to compare elements of the set. | |
*/ | |
set_t *set_create(cmpfunc_t cmpfunc){ | |
set_t *set = malloc(sizeof(set_t)); | |
set->tree = tree_create(cmpfunc); | |
set->cmpfunc = cmpfunc; | |
return set; | |
} | |
/* | |
* Destroys the given set. Subsequently accessing the set | |
* will lead to undefined behavior. | |
*/ | |
void set_destroy(set_t *set) { | |
tree_destroy(set->tree); | |
free(set); | |
} | |
/* | |
* Returns the size (cardinality) of the given set. | |
*/ | |
int set_size(set_t *set) { | |
return tree_size(set->tree); | |
} | |
/* | |
* Adds the given element to the given set. | |
*/ | |
void set_add(set_t *set, void *elem) { | |
if (!tree_contains(set->tree, elem)) | |
{ | |
node_add(set->tree, elem); | |
} | |
} | |
/* | |
* Returns 1 if the given element is contained in | |
* the given set, 0 otherwise. | |
*/ | |
int set_contains(set_t *set, void *elem) { | |
return tree_contains(set->tree, elem); | |
} | |
/* | |
* Returns the union of the two given sets; the returned | |
* set contains all elements that are contained in either | |
* a or b. | |
*/ | |
set_t *set_union(set_t *a, set_t *b) | |
{ | |
set_t *new_set = set_create(a->cmpfunc); | |
int size_a = set_size(a); | |
int size_b = set_size(b); | |
/* | |
* Using the tree_union func to flatten the tree into an array | |
* and then perform union operations | |
*/ | |
new_set->tree = tree_union(a->tree, b->tree, size_a, size_b); | |
return new_set; | |
} | |
/* | |
* Returns the intersection of the two given sets; the | |
* returned set contains all elements that are contained | |
* in both a and b. | |
*/ | |
set_t *set_intersection(set_t *a, set_t *b) { | |
//set_t *copyset = set_copy(a); | |
set_t *new_set = set_create(a->cmpfunc); | |
int size_a = set_size(a); | |
int size_b = set_size(b); | |
/* | |
* Using the tree_intersection func to flatten the tree into an array | |
* and then perform intersection operations | |
*/ | |
new_set->tree = tree_intersection(a->tree, b->tree, size_a, size_b); | |
return new_set; | |
} | |
/* | |
* Returns the set difference of the two given sets; the | |
* returned set contains all elements that are contained | |
* in a and not in b. | |
*/ | |
set_t *set_difference(set_t *a, set_t *b) { | |
//set_t *copyset = set_copy(a); | |
set_t *new_set = set_create(a->cmpfunc); | |
int size_a = set_size(a); | |
int size_b = set_size(b); | |
/* | |
* Using the tree_difference func to flatten the tree into an array | |
* and then perform difference operations | |
*/ | |
new_set->tree = tree_difference(a->tree, b->tree, size_a, size_b); | |
return new_set; | |
} | |
/* | |
* Returns a copy of the given set. | |
*/ | |
set_t *set_copy(set_t *set) { | |
set_t *set_copy = set_create(set->cmpfunc); | |
int size_a = set_size(set); | |
int size_b = set_size(set); | |
set_copy->tree = tree_copy(set->tree, size_a, size_b); | |
return set_copy; | |
} | |
/*set_t *set = malloc(sizeof(set_t));; | |
set->cmpfunc = cmpfunc; | |
set-> = set_copy | |
return set_copy;*/ | |
/* | |
* The type of set iterators. | |
*/ | |
struct set_iter { | |
tree_t *node; | |
}; | |
/* | |
* Creates a new set iterator for iterating over the given set. | |
*/ | |
set_iter_t *set_createiter(set_t *set) | |
{ | |
set_iter_t *iter = malloc(sizeof(set_iter_t)); | |
if (iter == NULL) | |
return 0; | |
iter->node = set->tree; | |
return iter; | |
} | |
/* | |
* Destroys the given set iterator. | |
*/ | |
void set_destroyiter(set_iter_t *iter) { | |
free(iter); | |
} | |
/* | |
* Returns 0 if the given set iterator has reached the end of the | |
* set, or 1 otherwise. | |
*/ | |
int set_hasnext(set_iter_t *iter) | |
{ | |
if (iter->node == NULL) | |
return 0; | |
else | |
return 1; | |
} | |
/* | |
* Returns the next element in the sequence represented by the given | |
* set iterator. | |
*/ | |
static int i = 0; | |
void *set_next(set_iter_t *iter) | |
{ | |
if(iter->node == NULL) | |
printf("tree iterator exhausted"); | |
else | |
{ | |
int size = iter->node->numitems; | |
int arr[size]; | |
int *p; | |
p = arr; | |
void *elem; | |
/* | |
* trying to flatten the tree so it will be easier to show the next | |
* element in sequence | |
*/ | |
store_inorder(iter->node, p, i); | |
elem = (p+i); | |
return elem; | |
++i; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment