Skip to content

Instantly share code, notes, and snippets.

@pcyu16

pcyu16/set_operation.c

Last active December 12, 2015 02:58
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save pcyu16/4703240 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save pcyu16/4703240 to your computer and use it in GitHub Desktop.
Download ZIP
set operation
Raw
set_operation.c
/**
* set_operation.c
* Author: pcyu16
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stddef.h>
typedef int val_t;
struct set_t {
size_t size;
val_t *elems;
};
typedef struct set_t* Set;
const long double err = 1e-6;
inline val_t vabs(val_t v);
inline size_t max_sizet(size_t a, size_t b);
int cmp(const void *a, const void *b);
_Bool set_contains(Set a, Set b);
_Bool set_isSorted(Set s);
_Bool set_equals(Set a, Set b);
void set_sort(Set s);
Set set_new(val_t *a, size_t n);
void set_delete(Set s);
Set set_union(Set a, Set b);
Set set_difference(Set a, Set b);
Set set_intersection(Set a, Set b);
inline val_t vabs(val_t v)
{
if(v < 0)
return -v;
return v;
}
int cmp(const void *a, const void *b)
{
const val_t x = *(val_t*)a;
const val_t y = *(val_t*)b;
if(vabs(x-y) < err)
return 0;
return x-y;
}
inline size_t max_sizet(size_t a, size_t b)
{
return a>b?a:b;
}
_Bool set_isSorted(Set s)
{
if(s -> size == 0 || s -> size == 1)
return true;
size_t i;
val_t v = s -> elems[0];
for(i=1;i<s -> size;i++){
if(v > s -> elems[i])
return false;
v = s -> elems[i];
}
return true;
}
void set_sort(Set s)
{
qsort(s -> elems, s -> size, sizeof(val_t), cmp);
}
Set set_new(val_t *a, size_t n)
{
Set s = (Set)malloc(sizeof(struct set_t));
s -> size = n;
s -> elems = (val_t*)malloc(n*sizeof(val_t));
memcpy(s -> elems, a, n*sizeof(val_t));
return s;
}
void set_delete(Set s)
{
if(s -> elems != NULL)
free(s -> elems);
free(s);
}
Set set_union(Set a, Set b)
{
if(!set_isSorted(a))
set_sort(a);
if(!set_isSorted(b))
set_sort(b);
val_t ar[a->size + b->size];
int cnt = 0, i, st=0;
for(i=0;i<a->size;i++){
ar[cnt++] = a -> elems[i];
while(st < b->size && b->elems[st] <= a->elems[i]){
if(a->elems[i] != b->elems[st])
ar[cnt++] = b->elems[st];
st++;
}
}
Set s = set_new(ar, cnt);
return s;
}
Set set_intersection(Set a, Set b)
{
if(!set_isSorted(a))
set_sort(a);
if(!set_isSorted(b))
set_sort(b);
val_t ar[max_sizet(a->size, b->size)];
int cnt = 0, cur = 0, st = 0, i;
for(i=0;i<a->size;i++){
while(st < b->size && b->elems[st] <= a->elems[i]){
if(a->elems[i] == b->elems[st]){
ar[cnt++] = a -> elems[i];
break;
}
st++;
}
}
Set s = set_new(ar, cnt);
return s;
}
Set set_difference(Set a, Set b)
{
if(!set_isSorted(a))
set_sort(a);
if(!set_isSorted(b))
set_sort(b);
val_t ar[max_sizet(a->size, b->size)];
int cnt = 0, cur = 0, st = 0, i;
for(i=0;i<a->size;i++){
ar[cnt++] = a->elems[i];
while(st < b->size && b->elems[st] <= a->elems[i]){
if(a->elems[i] == b->elems[st]){
cnt--;
break;
}
st++;
}
}
Set s = set_new(ar, cnt);
return s;
}
void set_display(FILE *out, const char *format, Set s)
{
fprintf(out, "{");
int i;
for(i=0;i<s->size;i++){
if(i)
fprintf(out, ", ");
fprintf(out, format, s->elems[i]);
}
fprintf(out, "}\n");
}
int main()
{
int a[] = {2,1,3};
Set x = set_new(a, 3);
a[2] = 7;
Set y = set_new(a, 3);
set_delete(x);
set_delete(y);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment