//*****************************************************************************
//
// map.c
//
// similar to a hashtable, but keys as well as values can be can be anything.
//
//*****************************************************************************

#include <stdlib.h>
#include "list.h"
#include "map.h"


// how big of a size does our map start out at?
#define DEFAULT_MAP_SIZE        5


int gen_hash_cmp(const void *key1, const void *key2) {
  int val = (key2 - key1);
  if(val < 0)      return -1;
  else if(val > 0) return  1;
  else             return  0;
  return val;
}

unsigned long gen_hash_func(const void *key) {
  return (unsigned long)key;
}

struct map_iterator {
  int curr_bucket;
  MAP *map;
  LIST_ITERATOR *bucket_i;
};

typedef struct map_entry {
  const void *key;
  void *val;
} MAP_ENTRY;

struct map_data {
  int size;
  int num_buckets;
  struct list **buckets;
  unsigned long (* hash_func)(const void *key);
  int           (*  compares)(const void *key1, const void *key2);
};


//
// an internal form of hashGet that returns the entire entry (key and val)
//
MAP_ENTRY *mapGetEntry(MAP *map, const void *key) {
  unsigned int bucket = map->hash_func(key) % map->num_buckets;

  if(map->buckets[bucket] == NULL)
    return NULL;
  else {
    LIST_ITERATOR *list_i = newListIterator(map->buckets[bucket]);
    MAP_ENTRY     *elem   = NULL;

    ITERATE_LIST(elem, list_i) {
      if(!map->compares(key, elem->key))
	break;
    } deleteListIterator(list_i);

    return elem;
  }
}


MAP_ENTRY *newMapEntry(const void *key, void *val) {
  MAP_ENTRY *entry = malloc(sizeof(MAP_ENTRY));
  entry->key = key;
  entry->val = val;
  return entry;
}

void deleteMapEntry(MAP_ENTRY *entry) {
  free(entry);
}


//
// Collect all of the MAP_ENTRYs in a map into a single list
LIST *mapCollectEntries(MAP *map) {
  LIST *list = newList();
  int i;
  for(i = 0; i < map->num_buckets; i++) {
    if(map->buckets[i] == NULL) continue;
    LIST_ITERATOR *list_i = newListIterator(map->buckets[i]);
    MAP_ENTRY       *elem = NULL;
    ITERATE_LIST(elem, list_i) {
      listPut(list, elem);
    } deleteListIterator(list_i);
  }
  return list;
}


//
// expand a map to the new size
void mapExpand(MAP *map, int size) {
  // collect all of the key:value pairs
  LIST     *entries = mapCollectEntries(map);
  MAP_ENTRY  *entry = NULL;
  int i;

  // delete all of the current buckets
  for(i = 0; i < map->num_buckets; i++) {
    if(map->buckets[i] == NULL) continue;
    deleteList(map->buckets[i]);
  }
  free(map->buckets);

  // now, make new buckets and set them to NULL
  map->buckets = calloc(size, sizeof(LIST *));
  map->num_buckets = size;

  // now, we put all of our entries back into the new buckets
  while((entry = listPop(entries)) != NULL) {
    unsigned int bucket = map->hash_func(entry->key) % map->num_buckets;
    if(map->buckets[bucket] == NULL) map->buckets[bucket] = newList();
    listPut(map->buckets[bucket], entry);
  }
  deleteList(entries);
}



//*****************************************************************************
//
// implementation of map.h
// documentation found in map.h
//
//*****************************************************************************
MAP *newMapSize(void *hash_func, void *compares, int size) {
  MAP *map = malloc(sizeof(MAP));
  map->size        = 0;
  map->num_buckets = size;
  map->hash_func   = (hash_func ? hash_func : gen_hash_func);
  map->compares    = (compares  ? compares  : gen_hash_cmp);
  map->buckets     = calloc(map->num_buckets, sizeof(LIST *));
  return map;
}

MAP *newMap(void *hash_func, void *compares) {
  return newMapSize(hash_func, compares, DEFAULT_MAP_SIZE);
}

void deleteMap(MAP *map) {
  int i;
  for(i = 0; i < map->num_buckets; i++) {
    if(map->buckets[i])
      deleteListWith(map->buckets[i], deleteMapEntry);
  }
  free(map->buckets);
  free(map);
}

int mapPut(MAP *map, const void *key, void *val) {
  MAP_ENTRY *elem = mapGetEntry(map, key);

  // update the val if it's already here
  if(elem)
    elem->val = val;
  else {
    // first, see if we'll need to expand the map
    if((map->size * 80)/100 > map->num_buckets)
      mapExpand(map, (map->num_buckets * 150)/100);

    unsigned int bucket = map->hash_func(key) % map->num_buckets;

    // if the bucket doesn't exist yet, create it
    if(map->buckets[bucket] == NULL)
      map->buckets[bucket] = newList();

    MAP_ENTRY *entry = newMapEntry(key, val);
    listPut(map->buckets[bucket], entry);
    map->size++;
  }

  return 1;
}

void *mapGet(MAP *map, const void *key) {
  MAP_ENTRY *elem = mapGetEntry(map, key);
  if(elem)
    return elem->val;
  else
    return NULL;
}

void *mapRemove(MAP *map, const void *key) {
  unsigned int bucket = map->hash_func(key) % map->num_buckets;

  if(map->buckets[bucket] == NULL)
    return NULL;
  else {
    LIST_ITERATOR *list_i = newListIterator(map->buckets[bucket]);
    MAP_ENTRY       *elem = NULL;

    ITERATE_LIST(elem, list_i) {
      if(!map->compares(key, elem->key))
	break;
    } deleteListIterator(list_i);

    if(elem == NULL)
      return NULL;

    void *val = elem->val;
    listRemove(map->buckets[bucket], elem);
    deleteMapEntry(elem);
    map->size--;
    return val;
  }
}

int mapIn(MAP *map, const void *key) {
  return (mapGetEntry(map, key) != NULL);
}

int mapSize(MAP *map) {
  return map->size;
}



//*****************************************************************************
//
// implementation of the hashmap iterator
// documentation in hashmap.h
//
//*****************************************************************************
MAP_ITERATOR *newMapIterator(MAP *map) {
  MAP_ITERATOR *I = malloc(sizeof(MAP_ITERATOR));
  I->map = map;
  I->bucket_i = NULL;
  mapIteratorReset(I);

  return I;
}

void        deleteMapIterator     (MAP_ITERATOR *I) {
  if(I->bucket_i) deleteListIterator(I->bucket_i);
  free(I);
}

void        mapIteratorReset      (MAP_ITERATOR *I) {
  int i;

  if(I->bucket_i) deleteListIterator(I->bucket_i);
  I->bucket_i = NULL;
  I->curr_bucket = 0;

  // bucket_i will be NULL if there are no elements
  for(i = 0; i < I->map->num_buckets; i++) {
    if(I->map->buckets[i] != NULL &&
       listSize(I->map->buckets[i]) > 0) {
      I->curr_bucket = i;
      I->bucket_i = newListIterator(I->map->buckets[i]);
      break;
    }
  }
}


void        mapIteratorNext       (MAP_ITERATOR *I) {
  // no elements in the hashmap
  if(I->bucket_i == NULL)
    return;
  // we're at the end of our list
  else if(listIteratorNext(I->bucket_i) == NULL) {
    deleteListIterator(I->bucket_i);
    I->bucket_i = NULL;
    I->curr_bucket++;
    
    for(; I->curr_bucket < I->map->num_buckets; I->curr_bucket++) {
      if(I->map->buckets[I->curr_bucket] != NULL &&
	 listSize(I->map->buckets[I->curr_bucket]) > 0) {
	I->bucket_i = newListIterator(I->map->buckets[I->curr_bucket]);
	break;
      }
    }
  }
}

const void *mapIteratorCurrentKey(MAP_ITERATOR *I) {
  if(!I->bucket_i)
    return NULL;
  else {
    MAP_ENTRY *entry = ((MAP_ENTRY *) listIteratorCurrent(I->bucket_i));
    if(entry)
      return entry->key;
    else
      return NULL;
  }
}

void       *mapIteratorCurrentVal (MAP_ITERATOR *I) {
  if(!I->bucket_i) 
    return NULL;
  else {
    MAP_ENTRY *entry = ((MAP_ENTRY *) listIteratorCurrent(I->bucket_i));
    if(entry)
      return entry->val;
    else
      return NULL;
  }
}