set

set.c

#include <stdlib.h>
#include "common.h"
#include "tree.h"
#include "set.h"
/*
 * The type of sets.
 */
struct set {
  tree_t *tree;
  cmpfunc_t cmpfunc;
};

/*
 * Creates a new set using the given comparison function
 * to compare elements of the set.
 */
set_t *set_create(cmpfunc_t cmpfunc){
  set_t *set = malloc(sizeof(set_t));
  set->tree = tree_create(cmpfunc);
  set->cmpfunc = cmpfunc;
  return set;
}
/*
 * Destroys the given set.  Subsequently accessing the set
 * will lead to undefined behavior.
 */
void set_destroy(set_t *set) {
  tree_destroy(set->tree);
  free(set);
}

/*
 * Returns the size (cardinality) of the given set.
 */
int set_size(set_t *set) {
  return tree_size(set->tree);
}

/*
 * Adds the given element to the given set.
 */
void set_add(set_t *set, void *elem) {
  if (!tree_contains(set->tree, elem))
  {
    node_add(set->tree, elem);
  }
}
/*
 * Returns 1 if the given element is contained in
 * the given set, 0 otherwise.
 */
int set_contains(set_t *set, void *elem) {
  return tree_contains(set->tree, elem);
}

/*
 * Returns the union of the two given sets; the returned
 * set contains all elements that are contained in either
 * a or b.
 */
set_t *set_union(set_t *a, set_t *b)
{
  set_t *new_set = set_create(a->cmpfunc);
  int size_a = set_size(a);
  int size_b = set_size(b);
  /*
   * Using the tree_union func to flatten the tree into an array
   * and then perform union operations
   */
  new_set->tree = tree_union(a->tree, b->tree, size_a, size_b);
  return new_set;
}

/*
 * Returns the intersection of the two given sets; the
 * returned set contains all elements that are contained
 * in both a and b.
 */
set_t *set_intersection(set_t *a, set_t *b) {

  //set_t *copyset = set_copy(a);
  set_t *new_set = set_create(a->cmpfunc);
  int size_a = set_size(a);
  int size_b = set_size(b);
/*
 * Using the tree_intersection func to flatten the tree into an array
 * and then perform intersection operations
 */
  new_set->tree = tree_intersection(a->tree, b->tree, size_a, size_b);

 return new_set;
}
/*
 * Returns the set difference of the two given sets; the
 * returned set contains all elements that are contained
 * in a and not in b.
 */
set_t *set_difference(set_t *a, set_t *b) {

  //set_t *copyset = set_copy(a);
  set_t *new_set = set_create(a->cmpfunc);
  int size_a = set_size(a);
  int size_b = set_size(b);
/*
 * Using the tree_difference func to flatten the tree into an array
 * and then perform difference operations
 */
  new_set->tree = tree_difference(a->tree, b->tree, size_a, size_b);
  return new_set;
}

/*
 * Returns a copy of the given set.
 */
set_t *set_copy(set_t *set) {

  set_t *set_copy = set_create(set->cmpfunc);
  int size_a = set_size(set);
  int size_b = set_size(set);
  set_copy->tree = tree_copy(set->tree, size_a, size_b);
  return set_copy;
}

  /*set_t *set = malloc(sizeof(set_t));;
  set->cmpfunc = cmpfunc;
  set-> = set_copy
  return set_copy;*/

/*
 * The type of set iterators.
 */
struct set_iter {
  tree_t *node;
};

/*
 * Creates a new set iterator for iterating over the given set.
 */
set_iter_t *set_createiter(set_t *set)
{
  set_iter_t *iter = malloc(sizeof(set_iter_t));
  if (iter == NULL)
    return 0;
  iter->node = set->tree;
  return iter;
}

/*
 * Destroys the given set iterator.
 */
void set_destroyiter(set_iter_t *iter) {
  free(iter);
}

/*
 * Returns 0 if the given set iterator has reached the end of the
 * set, or 1 otherwise.
 */
int set_hasnext(set_iter_t *iter)
{
  if (iter->node == NULL)
    return 0;
  else
    return 1;
}

/*
 * Returns the next element in the sequence represented by the given
 * set iterator.
 */
static int i = 0;
void *set_next(set_iter_t *iter)
{

  if(iter->node == NULL)
    printf("tree iterator exhausted");
  else
  {
    int size = iter->node->numitems;
    int arr[size];
    int *p;
    p = arr;
    void *elem;
   /*
    * trying to flatten the tree so it will be easier to show the next
    * element in sequence
    */
    store_inorder(iter->node, p, i);
    elem = (p+i);
    return elem;
    ++i;
  }
}