#include <u.h>
#include <libc.h>
#include "common.h"
#include "debug.h"
#include "collection.h"
#include "function.h"
#include "array.h"
#include "set.h"

enum { DEBUG_LIST = false };

typedef struct List List;

struct List 
{
  void *item;
  List *next;
};

List *list_add(List *self, void *p)
{
  List *newitem = (List *)emalloc_fs(sizeof(*newitem));
  newitem->item = p;
  newitem->next = self;
  return newitem;
}

void list_do(List *self, collectioneach each, void *arg)
{
  if(self == nil || each(self->item, arg) == COLLECTION_DO_STOP)
  {
    return;
  }

  list_do(self->next, each, arg);
}

void list_unary_do(List *self, functionunary each)
{
  if(self == nil)
  {
    return;
  }

  each(self->item);
  list_unary_do(self->next, each);
}

void list_free(List *self)
{
  if(self == nil)
  {
    return;
  }

  list_free(self->next);
  self->next = nil;
  free(self);
}

/**
 * @param isremoved is only set if it's removed, and nothing if it's not.
 */
List *list_remove(List *self, 
  void *p, collectionisequal isequal, bool *isremoved)
{
  NOISE(DEBUG_LIST, 
    "entering list_remove with list: 0x%uX p: 0x%uX", self, p);

  if(self == nil)
  {
    return nil;
  }

  if(isequal(self->item, p))
  {
    List *result = self->next;

    NOISE(DEBUG_LIST, "list_remove found item");
    free(self);
    if(isremoved != nil)
    {
      *isremoved = true;
    }

    NOISE(DEBUG_LIST, "list_remove found return");
    return result;
  }

  self->next = list_remove(self->next, p, isequal, isremoved);
  return self;
}

bool list_find(List *self, void **p, collectionisequal isequal)
{
  assert_valid(p);
  assert_valid(isequal);

  NOISE(DEBUG_LIST, "entering list_find");
  if(self == nil)
  {
    return false;
  }
  if(isequal(self->item, *p))
  {
    *p = self->item;
    return true;
  }
  return list_find(self->next, p, isequal);
}
    
bool list_includes(List *self, void *p, collectionisequal isequal)
{
  return list_find(self, &p, isequal);
}


enum 
{ 
  DEBUG_SET = false,
  SET_DEFAULT_SIZE = 11
};

#define SET_ITEM_SLOT_RATIO_THRESHOLD 0.75

struct Set
{
  collectionhash hash;
  collectionisequal isequal;
  int total;
  Array *elements;
};

static Array *set_elements(Set *self)
{
  return self->elements;
}

static uint set_array_size(Set *self)
{
  return array_size(set_elements(self));
}

static uint set_index_for(Set *self, void *p)
{
  return self->hash(p) % set_array_size(self);
}


static void set_init(Set *self, collectionisequal isequal, collectionhash hash)
{
  self->isequal = isequal;
  self->hash = hash;
  self->total = 0;
  self->elements = array_new_size(SET_DEFAULT_SIZE);
  array_resize(set_elements(self), SET_DEFAULT_SIZE);
}

Set *set_new(collectionisequal isequal, collectionhash hash)
{
  Set *result;
  assert_valid(isequal);
  assert_valid(hash);
  
  result = (Set *)emalloc_fs(sizeof(*result));
  set_init(result, isequal, hash);
  return result;
}

static void set_free_chains(Array *chains)
{
  array_unary_do(chains, (functionunary)list_free);
  array_free(chains);
}

static void set_destroy(Set *self)
{
  set_free_chains(set_elements(self));
}

void set_free(Set *self)
{
  if(self == nil)
  {
    return;
  }

  set_destroy(self);
  free(self);
}

void set_free_with(Set *self, functionunary free_each)
{
  set_unary_do(self, free_each);
  set_free(self);
}

uint set_size(Set *self)
{
  assert_valid(self);
  return self->total;
}

static uint set_items_threshold(Set *self)
{
  return set_array_size(self) * SET_ITEM_SLOT_RATIO_THRESHOLD;
}

static bool set_issaturated(Set *self)
{
  return set_size(self) >= set_items_threshold(self);
}

static uint set_next_capacity(Set *self)
{
  return set_size(self) * 2 + 1;
}

static collection_do_ret set_rehash_each(void *p, void *arg)
{
  assert_valid(p);
  assert_valid(arg);

  set_add((Set *)arg, p);
  return COLLECTION_DO_CONTINUE;
}

static collection_do_ret set_rehash_chain_each(void *p, void *arg)
{
  list_do((List *)p, set_rehash_each, arg);
  return COLLECTION_DO_CONTINUE;
}

static void set_grow(Set *self)
{
  uint newsize;
  Array *old; 

  newsize = set_next_capacity(self);
  old = self->elements;
  self->elements = array_new_size(newsize);
  array_resize(set_elements(self), newsize);
  self->total = 0;
  array_do(old, set_rehash_chain_each, self);
  set_free_chains(old);
}

static void set_grow_if_saturated(Set *self)
{
  if(set_issaturated(self))
  {
    set_grow(self);
  }
}

void set_add(Set *self, void *p)
{
  uint index;
  assert_valid(self);

  NOISE(DEBUG_SET, "entering set_add with self: 0x%uX p: 0x%uX", self, p);
  if(set_includes(self, p))
  {
    NOISE(DEBUG_SET, "set_add already has it");
    return;
  }
  
  set_grow_if_saturated(self);
  index = set_index_for(self, p);
  NOISE(DEBUG_SET, "set_add index: %d", index);

  array_put(set_elements(self), index, 
    list_add((List *)array_at(set_elements(self), index), p));
  ++(self->total);
}

bool set_find(Set *self, void **p)
{
  assert_valid(self);
  assert_valid(p);

  NOISE(DEBUG_SET, "entering set_find with self: 0x%uX p: 0x%uX", self, p);
  return list_find(array_at(set_elements(self), set_index_for(self, *p)), 
    p, self->isequal);
}

bool set_includes(Set *self, void *p)
{  
  return set_find(self, &p);
}

bool set_remove(Set *self, void *p)
{
  bool result = false;
  uint index;
  assert_valid(self);

  NOISE(DEBUG_SET, "entering set_remove with self: 0x%uX p: 0x%uX", self, p);
  index = set_index_for(self, p);

  NOISE(DEBUG_SET, "set_remove got index: %u", index);
  array_put(set_elements(self), index,
    list_remove(array_at(set_elements(self), index), 
      p, self->isequal, &result));
  
  if(result)
  {
    --(self->total);
  }
  return result;
}


typedef struct SetDoData
{
  collectioneach each;
  void *arg;
  collection_do_ret ret;
} SetDoData;

collection_do_ret set_do_each(void *p, void *arg)
{
  SetDoData *data = (SetDoData *)arg;
  assert_valid(data);

  data->ret = data->each(p, data->arg);
  return data->ret;
}

collection_do_ret set_do_chain_each(void *p, void *arg)
{
  SetDoData *data = (SetDoData *)arg;
  assert_valid(data);

  list_do((List *)p, set_do_each, arg);
  return data->ret;
}

void set_do(Set *self, collectioneach each, void *arg)
{
  SetDoData data = (SetDoData){each, arg, COLLECTION_DO_CONTINUE};
  assert_valid(self);
  assert_valid(each);

  array_do(set_elements(self), set_do_chain_each, &data);
}


collection_do_ret set_unary_do_each(void *p, void *arg)
{
  list_unary_do((List *)p, (functionunary)arg);
  return COLLECTION_DO_CONTINUE;
}

void set_unary_do(Set *self, functionunary each)
{
  assert_valid(self);
  assert_valid(each);
  array_do(set_elements(self), set_unary_do_each, (void *)each);
}