//C has no set: this is a sorted array without repeats,
//so a search is a binary search
typedef struct {
int *items;
size_t count;
} Set;
int compareInts(const void *a, const void *b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y);
}
//a pointer to the element, or nullptr if there is no such element
int *setFind(const Set *s, int value) {
return bsearch(&value, s->items, s->count, sizeof(int), compareInts);
}
//puts the value in its sorted place, a repeat is skipped
void setAdd(Set *s, int value) {
if (setFind(s, value) != nullptr) {
return;
}
s->items = realloc(s->items, (s->count + 1) * sizeof(int));
size_t i = s->count;
for (; i > 0 && s->items[i - 1] > value; i--) {
s->items[i] = s->items[i - 1];
}
s->items[i] = value;
s->count++;
}
Set first = {};
setAdd(&first, 1);
setAdd(&first, 2);
Set second = {};
setAdd(&second, 2);
setAdd(&second, 1);
Set third = {};
setAdd(&third, 1);
setAdd(&third, 2);
setAdd(&third, 3);
//both arrays are sorted, so equal sets have equal arrays
bool isEqual = first.count == second.count
&& memcmp(first.items, second.items, first.count * sizeof(int)) == 0;
//isEqual is true
//some element of first is in third
bool isIntersects = false;
for (size_t i = 0; i < first.count && !isIntersects; i++) {
isIntersects = setFind(&third, first.items[i]) != nullptr;
}
//isIntersects is true
//every element of third is in first
bool isSubset = true;
for (size_t i = 0; i < third.count && isSubset; i++) {
isSubset = setFind(&first, third.items[i]) != nullptr;
}
//isSubset is false
printf("isEqual is %s\n", isEqual ? "true" : "false");
printf("isIntersects is %s\n", isIntersects ? "true" : "false");
printf("isSubset is %s\n", isSubset ? "true" : "false");
free(first.items);
free(second.items);
free(third.items);