/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

#include "Hashtable.h"

#include <stdlib.h>
#include <stdio.h>

/*--------------------*/

/* auxiliary list functions */

#define eqElement(e1,e2) (compare((e1),(e2)) == 0)

#define mkEmptyList() ((List)0)
#define isEmptyList(l) ((l) == (List)0)

static int
isInList(Element e, List l)
{
  while (!isEmptyList(l))
    {
      if (eqElement(e, l->info))
        return 1;
      l = l->next;
    }
  return 0;
}

/*--------------------*/

static List
cons(Element e, List l)
{
  /* the only call of malloc for List values */
  List res = malloc(sizeof(*l));

  if (!res)
    {
      perror("cons: malloc failed");
      exit(1);
    }
  res->info = e;
  res->next = l;

  return res;
}

/*--------------------*/

static List
removeElem1(Element e, List l)
{
  if (isEmptyList(l))
    return l;

  if (eqElement(e, l->info))
    {
      List l1 = l->next;

      free(l);
      return l1;
    }

  l->next = removeElem1(e, l->next);
  return l;
}


/*--------------------*/

/* hash table creation */

/* size for new empty hashtable */
#define initialSize 16

Set
mkEmpty(void)
{
  Set res = malloc(sizeof(*res));
  List *table =
    malloc(initialSize *
           sizeof(*table));

  if (!res || !table)
    {
      perror
        ("mkEmptySet: malloc failed");
      exit(1);
    }

  res->size = initialSize;
  res->card = 0;
  res->table = table;

  {
    unsigned int i;

    for (i = 0; i < res->size; ++i)
      table[i] = mkEmptyList();
  }

  return res;
}

/*--------------------*/

Set
resizeHashtable(Set s,
                unsigned int newsize)
{
  unsigned int size = s->size;

  List *newtable =
    malloc(newsize * sizeof(*newtable));

  List *oldtable = s->table;

  unsigned int i;

  /* initialize new table */
  for (i = 0; i < newsize; ++i)
    newtable[i] = mkEmptyList();

  /* move entries from old table into new table */
  for (i = 0; i < size; ++i)
    {
      List l = oldtable[i];

      while (!isEmptyList(l))
        {
          List l1 = l;
          unsigned int i2 =
            hash(l->info) % newsize;

          l = l->next;
          l1->next = newtable[i2];
          newtable[i2] = l1;
        }
    }

  free(oldtable);

  s->size = newsize;
  s->table = newtable;

  return s;
}

/*--------------------*/

/* if card > 1.0 * size, the table size is doubled */
/* this factor and the expansion factor can be tuned */

Set
checkTableOverflow(Set s)
{
  /* don't use floating point arithmetic for this check */
  if (s->card > s->size)
    return resizeHashtable(s,
                           2 * s->size);

  return s;
}

/*--------------------*/

/* if card < 0.25 * size, the table size is divided by 2 */
/* this factor and the shrinking factor can be tuned */

Set
checkTableUnderflow(Set s)
{
  if (s->size > initialSize
      && 4 * s->card < s->size)
    return
      resizeHashtable(s, s->size / 2);

  return s;
}

/*--------------------*/

int
isInSet(Element e, Set s)
{
  unsigned int i = hash(e) % s->size;

  return isInList(e, s->table[i]);
}

/*--------------------*/

Set
insertElem(Element e, Set s)
{
  unsigned int i = hash(e) % s->size;
  List l = s->table[i];

  if (!isInList(e, l))
    {
      s->table[i] = cons(e, l);
      ++(s->card);
      s = checkTableOverflow(s);
    }

  return s;
}

Set
removeElem(Element e, Set s)
{
  unsigned int i = hash(e) % s->size;
  List l = s->table[i];

  if (isInList(e, l))
    {
      s->table[i] = removeElem1(e, l);
      --(s->card);
      s = checkTableUnderflow(s);
    }

  return s;
}

/*--------------------*/

static int
checkHashes(Set s)
{
  unsigned int i;

  for (i = 0; i < s->size; ++i)
    {
      List l = s->table[i];

      while (!isEmptyList(l))
        {
          if (hash(l->info) % s->size !=
              i)
            return 0;
          l = l->next;
        }
    }
  return 1;
}

static int
checkCard(Set s)
{
  unsigned int i;
  unsigned int res = 0;

  for (i = 0; i < s->size; ++i)
    {
      List l = s->table[i];

      while (!isEmptyList(l))
        {
          ++res;
          l = l->next;
        }
    }
  return res == s->card;
}

static int
checkTableLevel(s)
{
  /* check whether size and
     card fit the space constraints */
  return 1;
}

int
invSetAsHashtable(Set s)
{
  return
    checkHashes(s)
    &&
    checkCard(s)
    &&
    checkTableLevel(s);
}