#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

#include "ismap.h"

typedef struct
{
  int key;
  char* value;
  bool occupied;
} entry;

struct ismap
{
  int capacity;
  int size;
  entry *table; // INVARIANT: always at least one free slot in table
  int (*hash)(int);
};

#define ISMAP_INITIAL_CAPACITY 10000000

int ismap_compute_index(int key, int (*hash)(int), int cap);
void ismap_embiggen(ismap *m);
void ismap_table_add(entry *table, int key, char *value, int (*hash)(int), int cap);
int ismap_table_find_key(const entry *table, int key, int (*hash)(int), int capacity);

ismap *ismap_create(int (*h)(int))
{
  ismap *result = malloc(sizeof(ismap));
  if (result != NULL)
    {
      result->size = 0;
      result->hash = h;
      result->table = malloc(sizeof(entry) * ISMAP_INITIAL_CAPACITY);
      result->capacity = (result->table != NULL ? ISMAP_INITIAL_CAPACITY : 0);
      for (int i = 0; i < result->capacity; i++)
	{
	  result->table[i].occupied = false;
	}
    }
  return result;
}

int ismap_size(const ismap *m)
{
  return m->size;
}

/**
 * Returns the index where key is located in the given map, or the index
 * where it would go if it is not present.
 * 
 * @param table a table with at least one free slot
 * @param key a string, non-NULL
 * @param hash a hash function for strings
 * @param capacity the capacity of table
 * @return the index of key in table, or the index of the empty slot to put it in if it is not present
 */
int ismap_table_find_key(const entry *table, int key, int (*hash)(int), int capacity)
{
  // compute starting location for search from hash function
  int i = ismap_compute_index(key, hash, capacity);
  while (table[i].occupied && table[i].key != key)
    {
      i = (i + 1) % capacity;
    }
  return i;
}

void ismap_put(ismap *m, int key, char *value)
{
  int index = ismap_table_find_key(m->table, key, m->hash, m->capacity);
  if (m->table[index].occupied)
    {
      // key already present
      m->table[index].value = value;
    }
  else
    {
      if (m->size + 1 > m->capacity / 2)
	{
	  // grow
	  ismap_embiggen(m);
	  
	  // add to table
	  if (m->size + 1 < m->capacity)
	    {
	      // need add here since the index of the free spot will
	      // have changed after rehashing
	      ismap_table_add(m->table, key, value, m->hash, m->capacity);
	      m->size++;
	    }
	}
      else
	{
	  // add to table at free spot we found
	  m->table[index].key = key;
	  m->table[index].value = value;
	  m->table[index].occupied = true;
	  m->size++;
	}
    }
}

/**
 * Adds the given key and value into the given table.
 *
 * @param table a hash table with >= 2 unoccupied slots
 * @param key a string not present as a key in table, non-NULL
 * @param value a pointer to an integer, non-NULL
 * @param hash a hash function for strings
 * @param cap the number of slots in table
 */
void ismap_table_add(entry *table, int key, char *value, int (*hash)(int), int cap)
{
  int i = ismap_compute_index(key, hash, cap);
  while (table[i].occupied)
    {
      i = (i + 1) % cap;
    }
  table[i].key = key;
  table[i].value = value;
  table[i].occupied = true;
}

void ismap_embiggen(ismap *m)
{
}

int ismap_compute_index(int key, int (*hash)(int), int cap)
{
  return (hash(key) % cap + cap) % cap;
}

bool ismap_contains_key(const ismap *m, int key)
{
  return m->table[ismap_table_find_key(m->table, key, m->hash, m->capacity)].occupied;
}

char *ismap_get(ismap *m, int key)
{
  int index = ismap_table_find_key(m->table, key, m->hash, m->capacity);
  if (m->table[index].occupied)
    {
      return m->table[index].value;
    }
  else
    {
      return NULL;
    }
}

void ismap_for_each(ismap *m, void (*f)(int, char *, void *), void *arg)
{
  for (int i = 0; i < m->capacity; i++)
    {
      if (m->table[i].occupied)
	{
	  f(m->table[i].key, m->table[i].value, arg);
	}
    }
}  

void ismap_destroy(ismap *m)
{
  // not our responsibility to free values
  free(m->table);
  free(m);
}