#include <assert.h>
#include <stddef.h>
#include "bool.h"
#include "regions.h"
#include "set.h"

/**************************************************************************
 *                                                                        *
 * Types and Globals                                                      *
 *                                                                        *
 **************************************************************************/

struct Set
{
  region r;
  set_cmp_fn cmp;
  bool bag;
  struct Set_elt *hd;
};

struct Set_elt
{
  void *elt;
  struct Set_elt *next;
};

/**************************************************************************
 *                                                                        *
 * Functions                                                              *
 *                                                                        *
 **************************************************************************/

/* Make a new set, allocated in region r.  If bag is FALSE, don't
   store duplicates in set; otherwise allow duplicates. */
set set_new(region r, set_cmp_fn cmp, bool bag)
{
  set s = ralloc(r, struct Set);
  s->r = r;
  s->cmp = cmp;
  s->bag = bag;
  s->hd = NULL;
  return s;
}

/* Return a copy of s in region r */
set set_copy(region r, set s)
{
  set news;
  set_scanner ss;
  void *elt;

  news = set_new(r, s->cmp, TRUE); /* Make a bag for now -- no need to
				     check for dups yet again */
  scan_set(elt, ss, s)
    set_insert(news, elt);
  news->bag = s->bag;
  return news;
}

/* Return TRUE iff s is empty */
bool set_empty(set s)
{
  return s->hd == NULL;
}

/* Return TRUE if elt in s */
bool set_member(set s, void *elt)
{
  set_scanner ss;
  void *cur_elt;

  scan_set(cur_elt, ss, s)
    if (!s->cmp(cur_elt, elt))
      return TRUE;
  return FALSE;
}

/* Return the number of elements in s */
int set_size(set s)
{
  set_scanner ss;
  void *cur_elt;
  int i;

  i = 0;
  scan_set(cur_elt, ss, s)
    i++;
  return i;
}

/* Add elt to s.  If elt is not in s or s is a bag, return TRUE.
   Otherwise return FALSE. */
bool set_insert(set s, void *elt)
{
  struct Set_elt *new_elt;

  if (!s->bag && set_member(s, elt))
    return FALSE;

  /* elt was not in s, or s->bag was TRUE */
  new_elt = ralloc(s->r, struct Set_elt);
  new_elt->elt = elt;
  new_elt->next = s->hd;
  s->hd = new_elt;
  return TRUE;
}

/* Remove all copies of elt from s. Return TRUE if elt was in s. */
bool set_remove(set s, void *elt)
{
  struct Set_elt **se;
  bool found;

  se = &s->hd;
  found = FALSE;
  while (*se)
    {
      if (s->cmp((*se)->elt, elt) == 0)
	{
	  *se = (*se)->next;
	  found = TRUE;
	  if (!s->bag)
	    return found;
	}
      se = &(*se)->next;
    }
  return found;
}

/* Return TRUE if s1 <= s2 */
bool set_subset(set s1, set s2)
{
  set_scanner ss;
  void *cur_elt;

  scan_set(cur_elt, ss, s1)
    if (!set_member(s2, cur_elt))
      return FALSE;
  return TRUE;
}

/* Return the union of s1 and s2.  Destructive operation */
set set_union(set s1, set s2)
{

  assert(s1->r == s2->r && s1->cmp == s2->cmp && s1->bag == s2->bag);
  if (s1->bag)
    {
      /* For bags we can just link the lists together */
      struct Set_elt **se;

      se = &s1->hd;
      while (*se)
	se = &(*se)->next;
      *se = s2->hd;
      return s1;
    }
  else
    {
      /* For sets we need to watch out for duplicates */
      struct Set_elt *se;

      for (se = s2->hd; se; se = se->next)
	set_insert(s1, se->elt);
      return s1;
    }
}

/* Iterate over elements of s */
void set_scan(set s, set_scanner *ss)
{
  *ss = s->hd;
}

void *set_next(set_scanner *ss)
{
  void *result;

  if (!*ss)
    return NULL;
  result = (*ss)->elt;
  *ss = (*ss)->next;
  return result;
}