/* Sorted map ADT V1.02 25/11/05
   See smap.h for docs
   Copyright 2008 Jeffrey Lee
   This file is part of WOUM.
   WOUM is free software: you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation, either version 3 of the License, or
   (at your option) any later version.
   WOUM is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   You should have received a copy of the GNU General Public License
   along with WOUM.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef _SMAP_C
#define _SMAP_C

#include <stdlib.h>

#include "smap.h"
#include "gdll.h"

typedef struct {
	int key;
	void *value;
} pair;

typedef struct {
	int (*cmp)(const void *a,const void *b);
	gdll *table;
	int killkeys;
} _smap;

static int (*smap_sort_func)(const void *a,const void *b) = 0;
static int smap_sort_func2(const void *a,const void *b)
{
	pair *aa,*bb;
	aa = (pair *) a;
	bb = (pair *) b;
	if (smap_sort_func)
		return (smap_sort_func)((void *) aa->key,(void *) bb->key);
	else
		return aa->key - bb->key;
}

smap smap_create(int (*cmp)(const void *a,const void *b),int killkeys)
{
	_smap *h;
	h = malloc(sizeof(_smap));
	if (h == 0)
		return 0;
	h->cmp = cmp;
	h->table = gdll_create(0);
	if (h->table == 0)
	{
		free(h);
		return 0;
	}
	h->killkeys = killkeys;
	return (smap) h;
}

void smap_kill(smap hh)
{
	_smap *h;
	pair *p;
	h = (_smap *) hh;
	while (h->table->size > 0)
	{
		p = (pair *) h->table->head->me;
		gdll_killitem(h->table->head);
		if ((h->cmp) && (h->killkeys))
			free((void *) p->key);
	}
	gdll_kill(h->table,0);
	free(h);
}

int smap_size(smap hh)
{
	_smap *h;
	h = (_smap *) hh;
	return h->table->size;
}

int *smap_keys(smap hh)
{
	_smap *h;
	int *ar,i;
	pair **ar2;
	h = (_smap *) hh;
	smap_sort_func = h->cmp;
	if (gdll_sort(h->table,smap_sort_func2))
		return 0;
	ar2 = (pair **) gdll_array(h->table);
	if (ar2 == 0)
		return 0;
	ar = malloc(4*h->table->size);
	if (ar == 0) {
		free(ar2);
		return 0;
	}
	for (i=0;i<h->table->size;i++)
		ar[i] = ar2[i]->key;
	free(ar2);
	return ar;
}

void **smap_values(smap hh)
{
	_smap *h;
	void **ar;
	int i;
	pair **ar2;
	h = (_smap *) hh;
	smap_sort_func = h->cmp;
	if (gdll_sort(h->table,smap_sort_func2))
		return 0;
	ar2 = (pair **) gdll_array(h->table);
	if (ar2 == 0)
		return 0;
	ar = malloc(4*h->table->size);
	if (ar == 0) {
		free(ar2);
		return 0;
	}
	for (i=0;i<h->table->size;i++)
		ar[i] = ar2[i]->value;
	free(ar2);
	return ar;
}

int smap_add(smap hh,int key,void *value)
{
	_smap *h;
	h = (_smap *) hh;
	pair *p;
	gdll_item *i;
	i = h->table->head;
	while (i)
	{
		p = (pair *) i->me;
		if (h->cmp) {
			if ((h->cmp)((void *) key,(void *) p->key) == 0)
				return 1;
		} else if (key == p->key)
			return 1;
		i = i->next;
	}
	p = malloc(sizeof(pair));
	if (p == 0)
		return 1;
	p->key = key;
	p->value = value;
	i = gdll_createitem(p);
	gdll_addhead(h->table,i);
	return 0;
}

int smap_remove(smap hh,int key)
{
	_smap *h;
	h = (_smap *) hh;
	pair *p;
	gdll_item *i;
	i = h->table->head;
	while (i)
	{
		p = (pair *) i->me;
		if (h->cmp) {
			if ((h->cmp)((void *) key,(void *) p->key) == 0) {
				gdll_killitem(i);
				if (h->killkeys)
					free((void *) p->key);
				free(p);
				return 1;
			}
		} else if (key == p->key) {
			gdll_killitem(i);
			free(p);
			return 1;
		}
		i = i->next;
	}
	return 0;
}

int smap_remove2(smap hh,void *value)
{
	_smap *h;
	h = (_smap *) hh;
	pair *p;
	gdll_item *i,*ii;
	int cnt = 0;
	i = h->table->head;
	while (i)
	{
		p = (pair *) i->me;
		ii = i->next;
		if (value == p->value) {
			gdll_killitem(i);
			if ((h->cmp) && (h->killkeys))
				free((void *) p->key);
			free(p);
			cnt++;
		}
		i = ii;
	}
	return cnt;
}

void *smap_get(smap hh,int key)
{
	_smap *h;
	h = (_smap *) hh;
	pair *p;
	gdll_item *i;
	i = h->table->head;
	while (i)
	{
		p = (pair *) i->me;
		if (h->cmp) {
			if ((h->cmp)((void *) key,(void *) p->key) == 0)
				return p->value;
		} else if (key == p->key)
			return p->value;
		i = i->next;
	}
	return 0;
}

int smap_contains(smap hh,int key)
{
	_smap *h;
	h = (_smap *) hh;
	pair *p;
	gdll_item *i;
	i = h->table->head;
	while (i)
	{
		p = (pair *) i->me;
		if (h->cmp) {
			if ((h->cmp)((void *) key,(void *) p->key) == 0)
				return 1;
		} else if (key == p->key)
			return 1;
		i = i->next;
	}
	return 0;
}

#endif
