//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 numbers = {};
setAdd(&numbers, 1);
setAdd(&numbers, 2);
setAdd(&numbers, 3);
setAdd(&numbers, 4);
bool contain1 = setFind(&numbers, 1) != nullptr;
//contain1 is true
bool contain5 = setFind(&numbers, 5) != nullptr;
//contain5 is false
//every element of numbers2 is in numbers
Set numbers2 = {};
setAdd(&numbers2, 1);
setAdd(&numbers2, 2);
bool containAll = true;
for (size_t i = 0; i < numbers2.count && containAll; i++) {
containAll = setFind(&numbers, numbers2.items[i]) != nullptr;
}
//containAll is true
printf("contain1 is %s\n", contain1 ? "true" : "false");
printf("contain5 is %s\n", contain5 ? "true" : "false");
printf("containAll is %s\n", containAll ? "true" : "false");
free(numbers.items);
free(numbers2.items);