/*
 * avl.c -- libavl wrapper for Ruby
	* by Filip Pizlo, 2001
	*
	* History:
	*
	* August 2001, v 0.1: it works with the basic avl datatype
	*
	* License:
	*
	* Public domain.
	*
	*/

#include <ruby.h>

#include <avl.h>

VALUE
		fp_module_AVL,
		fp_class_AVL;

static ID
		cmp,
		eql;

struct fp_avl_element_struct;
typedef struct fp_avl_element_struct fp_avl_element;

struct fp_avl_element_struct {
	VALUE
			key,
			value;
};

static fp_avl_element *fp_avl_element_create(VALUE key,VALUE value) {
	fp_avl_element *ret;
	if (!rb_respond_to(key,cmp))
		rb_raise(rb_eTypeError,"The key must implement <=>");
	ret=ALLOC(fp_avl_element);
	ret->key=key;
	ret->value=value;
	return ret;
}

static int fp_avl_element_init(fp_avl_element *ele,VALUE key,VALUE value) {
	if (!rb_respond_to(key,cmp))
		rb_raise(rb_eTypeError,"The key must implement <=>");
	ele->key=key;
	ele->value=value;
	return 0;
}

static int fp_class_AVL_compare(fp_avl_element *a,fp_avl_element *b,
		void *arg) {
	return FIX2INT(rb_funcall(a->key,cmp,1,b->key));
}

static int fp_class_AVL_mark_element(fp_avl_element *ele,void *arg) {
	rb_gc_mark(ele->key);
	rb_gc_mark(ele->value);
}

static void fp_class_AVL_mark(avl_tree *tree) {
	avl_walk(tree,fp_class_AVL_mark_element,NULL);
}

static void fp_class_AVL_free(avl_tree *tree) {
	avl_destroy(tree,free);
}

VALUE fp_class_AVL_new(VALUE class) {
	avl_tree *tree=avl_create(fp_class_AVL_compare,NULL);
	VALUE ret=Data_Wrap_Struct(class,fp_class_AVL_mark,fp_class_AVL_free,tree);
	rb_obj_call_init(ret,0,NULL);
	return ret;
}

static VALUE fp_class_AVL_init(VALUE self) {
	return self;
}

VALUE fp_class_AVL_count(VALUE self) {
	return INT2FIX(avl_count(DATA_PTR(self)));
}

VALUE fp_class_AVL_insert(VALUE self,VALUE key,VALUE val) {
	fp_avl_element *ele=fp_avl_element_create(key,val);
	ele=avl_insert(DATA_PTR(self),ele);
	return ele==NULL?Qnil:ele->value;
}

VALUE fp_class_AVL_replace(VALUE self,VALUE key,VALUE val) {
	fp_avl_element *ele=fp_avl_element_create(key,val);
	ele=avl_replace(DATA_PTR(self),ele);
	return ele==NULL?Qnil:ele->value;
}

VALUE fp_class_AVL_delete(VALUE self,VALUE key) {
	fp_avl_element ele,*pEle;
	fp_avl_element_init(&ele,key,Qnil);
	pEle=avl_delete(DATA_PTR(self),&ele);
	return pEle==NULL?Qnil:pEle->value;
}

VALUE fp_class_AVL_find(VALUE self,VALUE key) {
	fp_avl_element ele,*pEle;
	fp_avl_element_init(&ele,key,Qnil);
	pEle=avl_find(DATA_PTR(self),&ele);
	return pEle==NULL?Qnil:pEle->value;
}

VALUE fp_class_AVL_find_close(VALUE self,VALUE key) {
	fp_avl_element ele,*pEle;
	fp_avl_element_init(&ele,key,Qnil);
	pEle=avl_find_close(DATA_PTR(self),&ele);
	return pEle==NULL?Qnil:pEle->value;
}

VALUE fp_class_AVL_each(VALUE self) {
	avl_traverser trav={0};
	fp_avl_element *ele;
	while ((ele=avl_traverse(DATA_PTR(self),&trav))!=NULL)
		rb_yield(rb_assoc_new(ele->key,ele->value));
	return Qnil;
}

VALUE fp_class_AVL_each_key(VALUE self) {
	avl_traverser trav={0};
	fp_avl_element *ele;
	while ((ele=avl_traverse(DATA_PTR(self),&trav))!=NULL)
		rb_yield(ele->key);
	return Qnil;
}

VALUE fp_class_AVL_each_value(VALUE self) {
	avl_traverser trav={0};
	fp_avl_element *ele;
	while ((ele=avl_traverse(DATA_PTR(self),&trav))!=NULL)
		rb_yield(ele->value);
	return Qnil;
}

VALUE fp_class_AVL_equal(VALUE self,VALUE other) {
	avl_tree *me=DATA_PTR(self),*her;
	avl_traverser trav={0};
	fp_avl_element *ele,*ele2;
	if (rb_obj_is_instance_of(other,fp_class_AVL)!=Qtrue) return Qfalse;
	her=DATA_PTR(other);
	if (avl_count(me)!=avl_count(her)) return Qfalse;
	while ((ele=avl_traverse(me,&trav))!=NULL) {
		ele2=avl_find(her,ele);
		if (ele2==NULL) return Qfalse;
		if (!rb_equal(ele->value,ele2->value)) return Qfalse;
	}
	return Qtrue;
}

VALUE fp_class_AVL_empty(VALUE self) {
	return avl_count(DATA_PTR(self))?Qfalse:Qtrue;
}

void Init_AVL() {
	fp_module_AVL=rb_define_module("AVL");
	// main AVL class
	fp_class_AVL=rb_define_class_under(fp_module_AVL,"AVL",rb_cObject);
	rb_define_singleton_method(fp_class_AVL,"new",fp_class_AVL_new,0);
	// primary methods
	rb_define_method(fp_class_AVL,"initialize",fp_class_AVL_init,0);
	rb_define_method(fp_class_AVL,"count",fp_class_AVL_count,0);
	rb_define_method(fp_class_AVL,"insert",fp_class_AVL_insert,2);
	rb_define_method(fp_class_AVL,"replace",fp_class_AVL_replace,2);
	rb_define_method(fp_class_AVL,"delete",fp_class_AVL_delete,1);
	rb_define_method(fp_class_AVL,"find",fp_class_AVL_find,1);
	rb_define_method(fp_class_AVL,"find_close",fp_class_AVL_find_close,1);
	rb_define_method(fp_class_AVL,"each",fp_class_AVL_each,0);
	// en-ruby-ization methods
	rb_define_method(fp_class_AVL,"[]",fp_class_AVL_find,1);
	rb_define_method(fp_class_AVL,"[]=",fp_class_AVL_replace,2);
	rb_define_method(fp_class_AVL,"each_key",fp_class_AVL_each_key,0);
	rb_define_method(fp_class_AVL,"each_value",fp_class_AVL_each_value,0);
	rb_define_method(fp_class_AVL,"each_pair",fp_class_AVL_each,0);
	rb_define_method(fp_class_AVL,"==",fp_class_AVL_equal,1);
	rb_define_method(fp_class_AVL,"empty?",fp_class_AVL_empty,0);
	// get some symbols...
	cmp=rb_intern("<=>");
	eql=rb_intern("==");
}