/** @file critbit2.c
 * my second Crit-bit tree example.
 * PUBLIC DOMAIN - Jon Mayo - July 9, 2009
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#ifndef EXPORT
/**
 * you could define this for tagging functions that are exported. by default export nothing.
 */
#define EXPORT static
#endif

/**
 *
 */
typedef unsigned char critbit2_flag_t;

/**
 *
 */
struct critbit2_node {
	void *child[2];
	size_t critbitofs; /**< the critical bit. */
	critbit2_flag_t is_inner[2]; /**< 1 if the child[i] pointer is for node inner. */
};

/**
 *
 */
struct critbit2_tree {
	void *root;
	critbit2_flag_t is_inner; /**< 1 if the root pointer is for node inner. */
	const char *(*getkey)(void *, size_t *); /**< this gets a key and length. */
	int (*compare)(const char *, size_t, const char *, size_t); /**< this compares two keys. */
	/**
	 * @todo keep a memory pool of nodes. 32 nodes per chunk, 1 bit per as a
	 * flag for allocation.
	 */
};

/**
 * find the critical bit between two keys.
 */
static size_t critbit2_critbit(size_t a_len, const char *a, size_t b_len, const char *b) {
	size_t i, len;

	assert(a != NULL);
	assert(b != NULL);

	len=a_len<=b_len?a_len:b_len;

	for(i=0;i<len;i++) {
		if(a[i]!=b[i]) {
			return i; /**< @todo figure out bit offset. */
		}
	}

	/* find up the loop */
	if(a_len<=b_len) {
		/* a is shorter or equal in length to b. */
		for(;i<b_len;i++) {
			/** @todo treat a[i] past its length as 0. */
			if(!b[i]) {
				return i; /**< @todo figure out bit offset. */
			}
		}
	} else {
		/* b is shorter than a. */
		for(;i<a_len;i++) {
			/** @todo treat b[i] past its length as 0. */
			if(!a[i]) {
				return i; /**< @todo figure out bit offset. */
			}
		}
	}

	return i; /* they are the same length, no difference. */
}

/**
 *
 */
static void *critbit2_walk(struct critbit2_tree *t, const char *key, size_t key_len, void ***insertion_point) {
	void *curr, **curr_ptr, **grandpa_ptr;
	struct critbit2_node *currnode;
	critbit2_flag_t is_inner, grandpa_is_inner;

	/* handle empty tree. */
	if(!t->root) {
		return NULL; /* not found - empty tree. */
	}

	/* look up an inner node. */
	grandpa_ptr=NULL;
	curr_ptr=&t->root;
	curr=*curr_ptr;
	is_inner=t->is_inner;
	while(is_inner) {
		unsigned dir;

		currnode=curr;

		if((currnode->critbitofs/CHAR_BIT)<key_len) {
			dir=(key[currnode->critbitofs/CHAR_BIT]>>(currnode->critbitofs%CHAR_BIT))&1;
		} else {
			dir=0;
		}

		assert(dir <= 1); /* dir must be 0 or 1. */

		/* keep track of our grandparent. */
		grandpa_ptr=curr_ptr;
		grandpa_is_inner=is_inner;

		is_inner=currnode->is_inner[dir];
		curr_ptr=&currnode->child[dir];
		curr=*curr_ptr;

		assert(curr != NULL);
	}

	if(insertion_point) {
		*insertion_point=curr_ptr;
	}

	return curr;
}

/**
 *
 */
EXPORT void critbit2_init(struct critbit2_tree *t, const char *(*getkey)(void *, size_t *), int (*compare)(const char*, size_t, const char*, size_t)) {
	assert(t != NULL);
	assert(getkey != NULL);

	t->root=NULL;
	t->is_inner=0;
	t->getkey=getkey;
	t->compare=compare;
}

/**
 *
 */
EXPORT int critbit2_insert(struct critbit2_tree *t, void *p) {
	const char *key;
	size_t key_len;
	void **insertion_point; /**< pointer where we'll stick a new internal node. */
	void *sibling; /**< closest matching sibling where we're going to insert ourselves. */

	assert(t != NULL);
	assert(t->getkey != NULL);
	assert(p != NULL);

	/* handle empty tree. */
	if(!t->root) {
		t->root=p;
		t->is_inner=0;
		return 1; /* success */
	}

	/* all other cases. */
	key=t->getkey(p, &key_len);

	/* find a place to insert into the tree. */
	sibling=critbit2_walk(t, key, key_len, &insertion_point);

	assert(insertion_point != NULL); /* the way this function works, this is never NULL. */
	assert(*insertion_point == sibling); /* this points to it after all. */

	/** @todo create a leaf here. */

	/** @todo insert new node and sibling into the leaf. */

	return 0; /* failure */
}

/**
 *
 */
EXPORT void *critbit2_lookup(struct critbit2_tree *t, const char *key, size_t key_len) {
	const char *ret_key; /**< key of the return value. */
	size_t ret_key_len; /**< length of the key of the return value. */
	void *ret; /**< return value. */

	ret=critbit2_walk(t, key, key_len, NULL);

	ret_key=t->getkey(ret, &ret_key_len);
	if(t->compare(ret_key, ret_key_len, key, key_len)) {
		return NULL; /* failure - keys don't match. */
	}

	return ret; /* success */
}

/* Unit test code */
#ifdef STAND_ALONE

struct mynode {
	char *name;
	double value;
};

static const char *mynode_getkey(void *p, size_t *len) {
	struct mynode *y=p;

	assert(y != NULL);
	assert(len != NULL);

	*len=strlen(y->name);

	return y->name;
}

static int mynode_compare(const char *a, size_t a_len, const char *b, size_t b_len) {
	int res; /**< result. */
	size_t len;

	/* choose the smaller len for the comparison. */
	len=a_len<b_len?a_len:b_len;

	/* compare the shortest length. */
	res=memcmp(a, b, len);

	/* if compares the same, then subtract differing lengths so that the longer
	 * string is greater than a shorter sub string. */
	return res ? res : (int)a_len-(int)b_len;
}

static struct mynode *mynode_create(const char *name, double value) {
	struct mynode *y;
	y=malloc(sizeof *y);
	y->name=strdup(name);
	y->value=value;
	return y;
}

static void mynode_free(struct mynode *y) {
	if(y) {
		free(y->name);
		free(y);
	}
}

static void mynode_print(struct mynode *y) {
	if(y) {
		printf("%p:\"%s\"=%g\n", (void*)y, y->name, y->value);
	} else {
		printf("(null)\n");
	}
}

static void critbit2_test1(void) {
	struct critbit2_tree t;
	struct mynode *tmp;

	printf("size: %zu\n", sizeof(struct critbit2_node));

	critbit2_init(&t, mynode_getkey, mynode_compare);

	tmp=mynode_create("life", 42.);

	critbit2_insert(&t, tmp);

	tmp=critbit2_lookup(&t, "life", strlen("life"));

	mynode_print(tmp);

	mynode_free(tmp);
}

static int critbit2_test2(void) {
	struct critbit2_tree t;
	const char *test_name[]={
		"this", "is", "a", "test", "."
	};
	const double test_value[]={
		42.0, 88.0, 128.0, 1.0, 16.0,
	};
	unsigned i;

	printf("size: %zu\n", sizeof(struct critbit2_node));

	critbit2_init(&t, mynode_getkey, mynode_compare);

	for(i=0;i<sizeof test_name/sizeof *test_name;i++) {
		struct mynode *tmp;
		tmp=mynode_create(test_name[i], test_value[i]);
		if(!critbit2_insert(&t, tmp)) {
			printf("Could not insert '%s'\n", test_name[i]);
			return 0; /* failure */
		}
	}

	for(i=0;i<sizeof test_name/sizeof *test_name;i++) {
		struct mynode *tmp;
		tmp=critbit2_lookup(&t, test_name[i], strlen(test_name[i]));
		if(!tmp) {
			printf("Not found '%s'\n", test_name[i]);
		} else {
			mynode_print(tmp);
		}
	}

	/** @todo delete all nodes. */

	return 1; /* success */
}

int main() {
	printf("*** Test #1:\n");
	critbit2_test1();
	printf("*** Test #2:\n");
	critbit2_test2();
}
#endif