#include <core.h>
#include <list.h>
using List;

// Universally quantified
struct IntSetA<`a> {
  `a elts;
  void (*add)(`a,int);
  bool (*is_member)(`a,int);
};

// Existentialy quantified
struct IntSetE { <`a> : regions(`a) > `H
  `a elts;
  void (*add)(`a,int);
  bool (*is_member)(`a,int);
};

// Implementation I; an intset's data is stored as a int ?`H @ pointer
//   (a pointer to a fat pointer containing the elements)

bool is_member1(int ?`H @ elts, int x) {
  for (int i = 0; i<numelts(*elts); i++) {
    if (x == (*elts)[i]) return true;
  }
  return false;
}

void add1(int ?`H @ elts,int x) {
  if (!is_member1(elts,x)) {
    let new_elts = new { for i < numelts(*elts)+1 :
			 i < numelts(*elts) ? (*elts)[i] : x };
    *elts = new_elts;
  }
}

// Implementation II; an intset's data is stored as a pointer to a
// list of ints

bool is_member2(list_t<int,`H> @ elts, int x) {
  for (list_t y = *elts; y != NULL; y=y->tl) {
    if (x == y->hd) return true;
  }
  return false;
}

void add2(list_t<int,`H> @ elts,int x) {
  if (!is_member2(elts,x)) {
    *elts = new List(x,*elts);
  }
}

// Make universal packages

struct IntSetA<int ?`H @> createA1() {
  return IntSetA{ .elts = new NULL, .add=add1, .is_member=is_member1 };
}

struct IntSetA<list_t<int,`H> @> createA2() {
  return IntSetA{ .elts = new NULL, .add=add2, .is_member=is_member2 };
}

// Make existential packages (notice they both have the same return type)

struct IntSetE createE1() {
  return IntSetE{ .elts = new NULL, .add=add1, .is_member=is_member1 };
}
struct IntSetE createE2() {
  return IntSetE{ .elts = new NULL, .add=add2, .is_member=is_member2 };
}

// Notice now that we have to write two different functions to invoke
// the add operation on a universally quantified set, one for each
// implementation.  For the existentials, we need just one function.
// Exercise: fill in the code for the following functions to add an
// element to a set.

void addA1(struct IntSetA<int ?`H @> iset) { 
}
void addA2(struct IntSetA<list_t<int,`H> @> iset) { 
}
void addE(struct IntSetE iset) { 
}