--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dict.c	Tue Apr 28 23:06:07 2009 +0000
@@ -0,0 +1,475 @@
+#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;
+	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;
+							}
+							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;
+					}
+					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
+			{
+				if(current->next >= 0)
+				{
+					//APPEND_KEY_STORE(key, key_store, key_size, current->letter);
+					decision = current;//nodes + current->next;
+					decision_key_size = key_size;
+					next_flag = TRUE;
+				}
+				else if(current->right >= 0)
+				{
+					decision = nodes + current->right;
+					decision_key_size = key_size;
+					next_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;
+}
+
+
+