If the sets are sorted you'll be able to optomize your intersection algorithm pretty easily. Of course, that means a performance hit when adding numbers to your sets.
But if your sets are sorted you can use binary searches for the intersection (and for insertions) which are pretty speedy. Binary searches also scale really well.
Here's a start I came up with:
Code:
typedef struct
{
int *set;
size_t size;
} set_t;
size_t binsearch(int *haystack, int needle, size_t size)
{
size_t half = size / 2;
size_t res;
if(!size)
return (size_t)-1;
if(needle == haystack[half])
return half;
if(size < 2)
return (size_t)-1;
if(needle < haystack[half])
return binsearch(haystack, needle, half);
res = binsearch(haystack + half, needle, size - half);
return res == (size_t)-1 ? res : res + half;
}
size_t insertionpoint(int *haystack, int needle, size_t size)
{
size_t half = size / 2;
if(size < 2)
return haystack[0] < needle;
if(haystack[half] > needle)
return insertionpoint(haystack, needle, half);
return insertionpoint(haystack + half, needle, size - half) + half;
}
set_t *set_init(void)
{
set_t *set;
if(!(set = malloc(sizeof(set_t))))
return NULL;
set->set = NULL;
set->size = 0;
return set;
}
void set_free(set_t *set)
{
if(set->set)
free(set->set);
free(set);
}
size_t set_insert(set_t *set, int num)
{
size_t i;
if(binsearch(set->set, num, set->size) == (size_t)-1)
{
int *temp;
if(!(temp = realloc(set->set, sizeof(int) * (set->size + 1))))
return 0;
i = set->size ? insertionpoint(temp, num, set->size) : 0;
memmove(temp + i + 1, temp + i, sizeof(int) * (set->size - i));
temp[i] = num;
set->set = temp;
set->size++;
}
return set->size;
}
set_t *set_intersect(set_t *set1, set_t *set2)
{
set_t *new;
size_t i;
if(!(new = set_init()))
return NULL;
for(i = 0;i < set1->size;++i)
if(binsearch(set2->set, set1->set[(int)i], set2->size) != (size_t)-1)
if(!(set_insert(new, set1->set[(int)i])))
{
set_free(new);
return NULL;
}
return new;
}
I'm sure there's still lots of room for improvement.