#include "datum.h"
#include "structs.h"
#include "debugmacros.h"
#include <string.h>
#include <stdlib.h>
//Index, Swap, Remove, Set, Length, New

ternary_node * find_node(datum * dict, datum * key, BOOL novalue)
{
	int i = 0;
	ternary_node * nodes;
	ternary_node * current = ((dict_data *)dict->c.generic.data)->nodes;
	nodes = current;
	if(((dict_data *)dict->c.generic.data)->num_nodes <= 0 || key->c.generic.len <= 1)
		return NULL;
	while(current >= nodes)
	{
		DEBUGPRINTF("current->letter: %c, key[%d]: %c\n", current->letter, i, ((char*)key->c.generic.data)[i]);
		if(((char*)key->c.generic.data)[i] == current->letter)
			if(i == (key->c.generic.len-2))
				if(current->payload || novalue)
					return current;
				else
					return NULL;
			else
			{
				current = nodes + current->next;
				++i;
			}
		else if(((char *)key->c.generic.data)[i] > current->letter)
			current = nodes + current->right;
		else
			current = nodes + current->left;
	}
	return NULL;
}

int vis_dict_index(datum ** inputlist, queue_entry * worker_entry)
{
	datum * output;
	int i = 0;
	ternary_node * found = find_node(inputlist[0], inputlist[1], FALSE);
	release_ref(inputlist[1]);
	if(found)
	{
		DEBUGPRINTF("Found payload: %X\n", found->payload);
		/*if(found->payload->type == BUILTIN_TYPE_STRING)
		{
			DEBUGPRINTF("Payload: %s\n", found->payload->c.generic.data);
		}*/
			
		output = add_ref(found->payload);
		inputlist[1] = NULL;
	}
	else
	{
		inputlist[1] = new_datum(BUILTIN_TYPE_YESNO, 2, 0, worker_entry->instance->def->program);
		inputlist[1]->c.integers.num_a = 0;
		output = NULL;
	}
	release_ref(inputlist[0]);
	inputlist[0] = output;
	return 0;
}

int vis_dict_swap(datum ** inputlist, queue_entry * worker_entry)
{
	ternary_node *first, *second;
	datum * temp;
	inputlist[0] = copy_datum(inputlist[0],0);
	first = find_node(inputlist[0], inputlist[1], FALSE);
	if(first)
	{
		second = find_node(inputlist[0], inputlist[2], FALSE);
		if(second)
		{
			temp = first->payload;
			first->payload = second->payload;
			second->payload = temp;
		}
	}
	release_ref(inputlist[1]);
	release_ref(inputlist[2]);
	return 0;
}

int vis_dict_remove(datum ** inputlist, queue_entry * worker_entry)
{
	//NOTE: Currently optimized for speed not for memory usage
	//Doesn't remove ternary_nodes that are no longer needed
	ternary_node * found;
	dict_data * dict;
	inputlist[0] = copy_datum(inputlist[0],0);
	found = find_node(inputlist[0], inputlist[1], FALSE);
	release_ref(inputlist[1]);
	dict = (dict_data *)inputlist[0]->c.generic.data;
	if(found)
	{
		release_ref(found->payload);
		found->payload = NULL;
		--(dict->num_entries);
	}
	return 0;
}

int vis_dict_set(datum ** inputlist, queue_entry * worker_entry)
{
	ternary_node * found, *current, *last;
	dict_data * dict, *new_dict;
	int new_node_storage,i,dir;
	int newlen;
	//DEBUGPRINTF("Payload: %s\n", inputlist[2]->c.generic.data);
	inputlist[0] = copy_datum(inputlist[0],0);
	found = find_node(inputlist[0], inputlist[1], TRUE);
	dict = (dict_data *)inputlist[0]->c.generic.data;
	DEBUGPRINTF("key: %s\n", inputlist[1]->c.generic.data);
	DEBUGPRINTF("Num nodes: %d, num entries: %d\n", dict->num_nodes, dict->num_entries);
	if(found)
	{
		if(found->payload)
			release_ref(found->payload);
		else
			++(dict->num_entries);
		found->payload = inputlist[2];
	}
	else if(inputlist[1]->c.generic.len > 1) //FIXME: silently fail on zero-length keys for now
	{
		if(dict->num_nodes)
		{
			current = dict->nodes;
			i = 0;
			while(current >= dict->nodes)
			{
				DEBUGPRINTF("Current node: %X\n", current);
				last = current;
				DEBUGPRINTF("Current letter: %c, key letter: %c\n", current->letter,((char *)inputlist[1]->c.generic.data)[i]);
				if(((char *)inputlist[1]->c.generic.data)[i] == current->letter)
				{
					DEBUGPUTS("Went straight\n");
					++i;
					current = dict->nodes + current->next;
					dir = 0;
				}
				else if(((char *)inputlist[1]->c.generic.data)[i] > current->letter)
				{
					DEBUGPUTS("Went right\n");
					current = dict->nodes + current->right;
					dir = 1;
				}
				else
				{
					DEBUGPUTS("Went left\n");
					current = dict->nodes + current->left;
					dir = 2;
				}
			}
			DEBUGPRINTF("Matched %d out of %d characters\n", i, (inputlist[1]->c.generic.len-1));
			DEBUGPRINTF("node_storage: %d, num_nodes: %d\n", dict->node_storage, dict->num_nodes);
			if((dict->node_storage-dict->num_nodes) < ((inputlist[1]->c.generic.len-1) - i))
			{
				DEBUGPUTS("Allocating more storage\n");
				new_node_storage = inputlist[1]->c.generic.len - 1 - i + dict->num_nodes;
				new_node_storage += new_node_storage >> 1; //1.5 times required storage
				newlen = sizeof(dict_data) + sizeof(ternary_node) * (new_node_storage-1);
				new_dict = malloc(newlen);
				DEBUGPRINTF("After malloc: new_dict = %X, size: %d, new_node_storage: %d\n", new_dict, newlen, new_node_storage);
				memcpy(new_dict, dict, sizeof(dict_data) + sizeof(ternary_node) * (dict->num_nodes-1));
				DEBUGPUTS("After memcpyy\n");
				new_dict->node_storage = new_node_storage;
				//new_dict->num_entries = dict->num_entries + 1;
				new_dict->num_nodes = dict->num_nodes;
				DEBUGPRINTF("last was: %X, dict->nodes was: %X, ", last, dict->nodes);
				last = new_dict->nodes + (last - dict->nodes);
				DEBUGPRINTF("last is now: %X, dict->nodes is now : %X, ", last, new_dict->nodes);
				VIS_FREE(dict, "dictionary object");
				DEBUGPUTS("After free\n");
				dict = new_dict;
				inputlist[0]->c.generic.data = dict;
				inputlist[0]->c.generic.len = newlen;
			}
			++(dict->num_entries);
			DEBUGPRINTF("Setting current to: %X\n", dict->nodes + dict->num_nodes);
			current =dict->nodes + dict->num_nodes;
			DEBUGPUTS("Setting left, right and next pointer to null\n");
			current->left = current->right = current->next = -1;
			current->payload = NULL;
			current->letter = ((char *)inputlist[1]->c.generic.data)[i];
			DEBUGPRINTF("Setting pointer in last node (%X) to current node\n", last);
			if(dir == 1)
				last->right = dict->num_nodes;
			else if(dir == 2)
				last->left = dict->num_nodes;
			else
				last->next = dict->num_nodes;
			++i;
			++(dict->num_nodes);
			last = current;
			DEBUGPUTS("Entering node add loop\n");
			for(;i < (inputlist[1]->c.generic.len-1); ++i)
			{
				DEBUGPRINTF("Adding node at index %d\n", dict->num_nodes);
				current = dict->nodes + dict->num_nodes;
				last->next = dict->num_nodes;
				current->left = current->right = current->next = -1;
				current->payload = NULL;
				current->letter = ((char *)inputlist[1]->c.generic.data)[i];
				++(dict->num_nodes);
				last = current;
			}
			DEBUGPUTS("Loop complete\n");
			last->payload = inputlist[2];
		}
		else
		{
			if(dict->node_storage < (inputlist[1]->c.generic.len-1))
			{
				VIS_FREE(dict, "dictionary object");
				newlen = sizeof(dict_data) + sizeof(ternary_node) * ((inputlist[1]->c.generic.len-1)<<2);
				dict = malloc(newlen);
				dict->node_storage = ((inputlist[1]->c.generic.len-1)<<2) + 1;
				inputlist[0]->c.generic.data = dict;
				inputlist[0]->c.generic.len = newlen;
				
			}
			dict->num_entries = 1;
			dict->num_nodes = (inputlist[1]->c.generic.len-1);
			for(i = 0; i < dict->num_nodes; ++i)
			{
				dict->nodes[i].left = dict->nodes[i].right = -1;
				dict->nodes[i].letter = ((char *)inputlist[1]->c.generic.data)[i];
				if(i == (dict->num_nodes - 1))
				{
					dict->nodes[i].next = -1;
					dict->nodes[i].payload = inputlist[2];
				}
				else
				{
					dict->nodes[i].next = i + 1;
					dict->nodes[i].payload = NULL;
				}
			}
		}
	}
	release_ref(inputlist[1]);
	DEBUGPRINTF("Num nodes after set: %d\n", dict->num_nodes);
	//DEBUGPRINTF("Payload: %s\n", inputlist[2]->c.generic.data);
	return 0;
}

int vis_dict_length(datum ** inputlist, queue_entry * worker_entry)
{
	datum * output;
	dict_data * dict = ((dict_data *)inputlist[0]->c.generic.data);
	output = new_datum(BUILTIN_TYPE_WHOLE, 2, 0, worker_entry->instance->def->program);
	output->c.integers.num_a = dict->num_entries;
	release_ref(inputlist[0]);
	inputlist[0] = output;
	return 0;
}

datum * create_dict(program * prog)
{
	dict_data * dict;
	datum * dat = new_datum(BUILTIN_TYPE_DICT, 1, sizeof(dict_data) + sizeof(ternary_node)*23, prog);
	dict = (dict_data *)dat->c.generic.data;
	dict->num_entries = 0;
	dict->num_nodes = 0;
	dict->node_storage = 24;
	return dat;
}

int vis_dict_new(datum ** inputlist, queue_entry * worker_entry)
{
	inputlist[0] = create_dict(worker_entry->instance->def->program);
	return 0;
}

#define APPEND_KEY_STORE(key, key_store, key_size, val) if(key_size == key_store) { key_store = key_store + (key_store>>1); key = realloc(key, key_store); } key[key_size++] = val

int vis_dict_first(datum ** inputlist, queue_entry * worker_entry)
{
	dict_data * dict = inputlist[0]->c.generic.data;
	char * key;
	int key_store = 128;
	int key_size = 0;
	
	int i = 0;
	ternary_node * nodes;
	ternary_node * current = dict->nodes;
	nodes = current;
	if(dict->num_nodes <= 0)
	{
		inputlist[1] = inputlist[0];
		inputlist[0] = NULL;
	}
	else
	{
		key = malloc(128);
		while(1)
		{
			if(current->left >= 0)
			{
				current = nodes + current->left;
			} else if(current->payload) {
				APPEND_KEY_STORE(key, key_store, key_size, current->letter);
				APPEND_KEY_STORE(key, key_store, key_size, '\0');
				release_ref(inputlist[0]);
				inputlist[0] = new_datum(BUILTIN_TYPE_STRING, 2, 0, worker_entry->instance->def->program);
				inputlist[0]->union_type = 1;
				inputlist[0]->c.generic.data = key;
				inputlist[0]->c.generic.len = key_size;
				inputlist[1] = NULL;
				break;
			} else if(current->next >= 0) {
				APPEND_KEY_STORE(key, key_store, key_size, current->letter);
				current = nodes + current->next;
			} else if(current->right >= 0) {
				current = nodes + current->right;
			} else {
				inputlist[1] = inputlist[0];
				inputlist[0] = NULL;
				VIS_FREE(key, "dictionary key store");
				break;
			}
		}
	}
	return 0;
}

int vis_dict_next(datum ** inputlist, queue_entry * worker_entry)
{
	dict_data * dict = inputlist[0]->c.generic.data;
	char * key;
	char * old_key = inputlist[1]->c.generic.data;
	int old_key_len = inputlist[1]->c.generic.len-2;
	int key_store = inputlist[1]->c.generic.len;
	int key_size = 0;
	
	int i = 0;
	ternary_node * nodes;
	ternary_node * current = dict->nodes;
	ternary_node * decision = NULL;
	int decision_key_size;
	BOOL next_flag = FALSE;
	BOOL this_flag = FALSE;
	nodes = current;
	
	if(dict->num_nodes <= 0)
	{
		release_ref(inputlist[1]);
		inputlist[1] = inputlist[0];
		inputlist[0] = NULL;
		return 0;
	}
	else
	{
		key = malloc(key_store);
		while(current >= nodes)
		{
			if(old_key[i] == current->letter)
				if(i == (old_key_len))
				{
					/*if(current->left >= 0)
					{
						current = nodes + current->left;
						break;
					}
					else */if(current->next >= 0)
					{
						APPEND_KEY_STORE(key, key_store, key_size, current->letter);
						current = nodes + current->next;
						break;
					}
					else if(current->right >= 0)
					{
						current = nodes + current->right;
						break;
					}
					else
					{
						if(decision)
						{
							key_size = decision_key_size;
							current = decision;
							if(next_flag)
							{
								APPEND_KEY_STORE(key, key_store, key_size, current->letter);
								current = nodes + current->next;
							}
							else if(this_flag)
							{
								APPEND_KEY_STORE(key, key_store, key_size, current->letter);
								APPEND_KEY_STORE(key, key_store, key_size, '\0');
								release_ref(inputlist[0]);
								release_ref(inputlist[1]);
								inputlist[1] = NULL;
								inputlist[0] = new_datum(BUILTIN_TYPE_STRING, 2, 0, worker_entry->instance->def->program);
								inputlist[0]->union_type = 1;
								inputlist[0]->c.generic.data = key;
								inputlist[0]->c.generic.len = key_size;
								return 0;
							}
							break;
						}
						else
						{
							VIS_FREE(key, "dictionary key store");
							release_ref(inputlist[1]);
							inputlist[1] = inputlist[0];
							inputlist[0] = NULL;
							return 0;
						}
					}
				}
				else
				{
					if(current->right >= 0)
					{
						decision = nodes + current->right;
						decision_key_size = key_size;
						next_flag = FALSE;
						this_flag = FALSE;
					}
					APPEND_KEY_STORE(key, key_store, key_size, current->letter);
					++i;
					current = nodes + current->next;
				}
			else if(old_key[i] > current->letter)
				current = nodes + current->right;
			else
			{
				//Hmm, what do I do here if there's a payload at this location?
				if(current->next >= 0 || current->payload)
				{
					//APPEND_KEY_STORE(key, key_store, key_size, current->letter);
					decision = current;//nodes + current->next;
					decision_key_size = key_size;
					if(current->payload)
					{
						next_flag = FALSE;
						this_flag = TRUE;
					} else {
						next_flag = TRUE;
						this_flag = FALSE;
					}
				}
				else if(current->right >= 0)
				{
					decision = nodes + current->right;
					decision_key_size = key_size;
					next_flag = FALSE;
					this_flag = FALSE;
				}
				current = nodes + current->left;
			}
		}
		if(current < nodes)
		{
			VIS_FREE(key, "dictionary key store");
			release_ref(inputlist[1]);
			inputlist[1] = inputlist[0];
			inputlist[0] = NULL;
			return 0;
		}
		while(1)
		{
			if(current->left >= 0)
			{
				current = nodes + current->left;
			} else if(current->payload) {
				APPEND_KEY_STORE(key, key_store, key_size, current->letter);
				APPEND_KEY_STORE(key, key_store, key_size, '\0');
				release_ref(inputlist[0]);
				release_ref(inputlist[1]);
				inputlist[1] = NULL;
				inputlist[0] = new_datum(BUILTIN_TYPE_STRING, 2, 0, worker_entry->instance->def->program);
				inputlist[0]->union_type = 1;
				inputlist[0]->c.generic.data = key;
				inputlist[0]->c.generic.len = key_size;
				break;
			} else if(current->next >= 0) {
				APPEND_KEY_STORE(key, key_store, key_size, current->letter);
				current = nodes + current->next;
			} else if(current->right >= 0) {
				current = nodes + current->right;
			} else {
				release_ref(inputlist[1]);
				inputlist[1] = inputlist[0];
				inputlist[0] = NULL;
				VIS_FREE(key, "dictionary key store");
				break;
			}
		}
	}
	return 0;
}