136 lines
3.6 KiB
C
136 lines
3.6 KiB
C
#include <assert.h>
|
|
#include <stdio.h>
|
|
#include <string.h>
|
|
#include <stdlib.h>
|
|
|
|
const char *mary="Mary";
|
|
const char *bob="Bob";
|
|
const char *jim="Jim";
|
|
const char *john="John";
|
|
const char *serena="Serena";
|
|
|
|
const char *setA[] = {john,bob,mary,serena};
|
|
const char *setB[] = {jim,mary,john,bob};
|
|
|
|
#define XSET(j) j, (sizeof(j)/sizeof(*j))
|
|
#define TALLOC(n,typ) malloc(n*sizeof(typ))
|
|
|
|
typedef enum {
|
|
esdDIFFERENCE,
|
|
esdSYMMETRIC } EsdFunction;
|
|
/** * * * * * * * * * * * * * * * * * * * *
|
|
* return value is difference or symmetric difference set
|
|
* its size is returned in sym_size
|
|
* f determinse whether it is a symmetric difference, or normal difference
|
|
* * * * * * * * * * * * * * * * * * * * **/
|
|
const char ** symmdiff( int *sym_size, EsdFunction f, const char *setA[], int setAsize, const char *setB[], int setBsize)
|
|
{
|
|
int union_size;
|
|
int max_union_size;
|
|
int diff_size;
|
|
const char **union_set;
|
|
const char **diff_set;
|
|
int *union_xor;
|
|
int ix, ixu;
|
|
|
|
max_union_size = setAsize + setBsize;
|
|
union_set = TALLOC(max_union_size, const char *);
|
|
union_xor = TALLOC(max_union_size, int);
|
|
|
|
/* I'm assuming here that setA has no duplicates,
|
|
* i.e. is a set in mathematical sense */
|
|
for (ix=0; ix<setAsize; ix++) {
|
|
union_set[ix] = setA[ix];
|
|
union_xor[ix] = 1;
|
|
}
|
|
diff_size = union_size = setAsize;
|
|
for (ix=0; ix<setBsize; ix++) {
|
|
for (ixu=0; ixu<union_size; ixu++) {
|
|
if (union_set[ixu] == setB[ix]) break;
|
|
}
|
|
if (ixu < union_size) { /* already in union */
|
|
union_xor[ixu] = 1-union_xor[ixu];
|
|
diff_size--;
|
|
}
|
|
else { /* not already in union -add */
|
|
if (f == esdSYMMETRIC) {
|
|
union_set[ixu] = setB[ix];
|
|
union_xor[ixu] = 1;
|
|
union_size++;
|
|
diff_size++;
|
|
}
|
|
}
|
|
}
|
|
/* Put results in symdiff set */
|
|
diff_set = TALLOC(diff_size, const char *);
|
|
ix = 0;
|
|
for (ixu=0; ixu<union_size; ixu++) {
|
|
if (union_xor[ixu]) {
|
|
if (ix == diff_size) {
|
|
printf("Short of space in diff_set\n");
|
|
exit(1);
|
|
}
|
|
diff_set[ix] = union_set[ixu];
|
|
ix++;
|
|
}
|
|
}
|
|
*sym_size = diff_size;
|
|
free(union_xor);
|
|
free(union_set);
|
|
return diff_set;
|
|
}
|
|
|
|
/* isSet tests that elements of list are unique, that is, that the list is a
|
|
* mathematical set. The uniqueness test implemented here is strcmp. */
|
|
int isSet(const char *list[], int lsize)
|
|
{
|
|
int i, j;
|
|
const char *e;
|
|
if (lsize == 0) {
|
|
return 1;
|
|
}
|
|
for (i = lsize-1; i>0; i--) {
|
|
e = list[i];
|
|
for (j = i-1; j>=0; j--) {
|
|
if (strcmp(list[j], e) == 0) {
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
void printSet (const char *set[], int ssize)
|
|
{
|
|
int ix;
|
|
printf(" = {");
|
|
for (ix=0;ix<ssize; ix++) {
|
|
printf( "%s ", set[ix]);
|
|
}
|
|
printf("}\n");
|
|
}
|
|
|
|
int main()
|
|
{
|
|
const char **symset;
|
|
int sysize;
|
|
|
|
/* Validate precondition stated by task, that inputs are sets. */
|
|
assert(isSet(XSET(setA)));
|
|
assert(isSet(XSET(setB)));
|
|
|
|
printf ("A symmdiff B");
|
|
symset = symmdiff( &sysize, esdSYMMETRIC, XSET(setA), XSET(setB));
|
|
printSet(symset, sysize);
|
|
free(symset);
|
|
printf ("A - B");
|
|
symset = symmdiff( &sysize, esdDIFFERENCE, XSET(setA), XSET(setB));
|
|
printSet(symset, sysize);
|
|
printf ("B - A");
|
|
symset = symmdiff( &sysize, esdDIFFERENCE, XSET(setB), XSET(setA));
|
|
printSet(symset, sysize);
|
|
free(symset);
|
|
|
|
return 0;
|
|
}
|