/*
 * Ruby Treasures 0.1
 * Copyright (C) 2001 Paul Brannan <paul@atdesk.com>
 * 
 * You may distribute this software under the same terms as Ruby (see the file
 * COPYING that was distributed with this library).
 * 
 */
#include <ruby.h>
#include <stdlib.h>

typedef struct RUBY_LIST_NODE {
    VALUE value;
    struct RUBY_LIST_NODE *next;
    struct RUBY_LIST_NODE *prev;
} Ruby_List_Node;

typedef struct {
    struct RUBY_LIST_NODE *head;
    struct RUBY_LIST_NODE *tail;
    size_t size;
} Ruby_List;

static VALUE cList;

void ruby_list_mark(Ruby_List *list) {
    Ruby_List_Node *current;
    
    for(current = list->head; current != NULL; current = current->next) {
        rb_gc_mark(current->value);
    }
}

void ruby_list_free(Ruby_List *list) {
    Ruby_List_Node *current, *next;
    
    for(current = list->head; current != NULL; current = next) {
        next = current->next;
        free(current);
    }
}

VALUE list_empty(Ruby_List *list) {
    return list->size <= 0;
}

VALUE ruby_list_empty(VALUE self) {
    Ruby_List *list;
    
    Data_Get_Struct(self, Ruby_List, list);
    
    return list_empty(list) ? Qtrue : Qfalse;
}

VALUE ruby_list_push(VALUE self, VALUE x) {
    Ruby_List *list;
    
    Data_Get_Struct(self, Ruby_List, list);
        
    if(ruby_list_empty(self)) {
        list->head = list->tail = ALLOC(Ruby_List_Node);
        list->head->value = x;
        list->head->next = NULL;
        list->head->prev = NULL;
    } else {
        list->tail->next = ALLOC(Ruby_List_Node);
        list->tail->next->value = x;
        list->tail->next->next = NULL;
        list->tail->next->prev = list->tail;
        list->tail = list->tail->next;
    }

    ++list->size;

    return self;
}

VALUE ruby_list_clear(VALUE self) {
    Ruby_List * list;

    Data_Get_Struct(self, Ruby_List, list);

    list->head = NULL;
    list->tail = NULL;
    list->size = 0;

    return self;
}

VALUE ruby_list_new(int argc, VALUE * argv, VALUE klass) {
    VALUE ruby_list;
    Ruby_List *list;
    size_t i;

    ruby_list = Data_Make_Struct(
            cList,
            Ruby_List,
            ruby_list_mark,
            ruby_list_free,
            list);

    ruby_list_clear(ruby_list);

    for(i = 0; i < argc; ++i) {
        ruby_list_push(ruby_list, argv[i]);
    }

    return ruby_list;
}

VALUE ruby_list_pop(VALUE self) {
    Ruby_List *list;
    
    Data_Get_Struct(self, Ruby_List, list);
        
    if(list->tail == NULL) {
        return Qnil;
    } else {
        VALUE elem = list->tail->value;
        list->tail = list->tail->prev;
        if(list->tail != NULL) {
            list->tail->next = NULL;
        }
        --list->size;
        return elem;
    }
}

VALUE ruby_list_unshift(VALUE self, VALUE x) {
    Ruby_List *list;
    
    Data_Get_Struct(self, Ruby_List, list);
        
    if(ruby_list_empty(self)) {
        list->tail = list->head = ALLOC(Ruby_List_Node);
        list->tail->value = x;
        list->tail->prev = NULL;
        list->tail->next = NULL;
    } else {
        list->head->prev = ALLOC(Ruby_List_Node);
        list->head->prev->value = x;
        list->head->prev->prev = NULL;
        list->head->prev->next = list->head;
        list->head = list->head->prev;
    }

    ++list->size;

    return self;
}

VALUE ruby_list_shift(VALUE self) {
    Ruby_List *list;
    
    Data_Get_Struct(self, Ruby_List, list);
        
    if(list->head == NULL) {
        return Qnil;
    } else {
        VALUE elem = list->head->value;
        list->head = list->head->next;
        if(list->head != NULL) {
            list->head->prev = NULL;
        }
        --list->size;
        return elem;
    }
}

VALUE ruby_list_clone(VALUE self) {
    VALUE ruby_new_list;
    Ruby_List *list;
    Ruby_List_Node *current;

    Data_Get_Struct(self, Ruby_List, list);

    ruby_new_list = ruby_list_new(0, 0, cList);

    for(current = list->head; current != NULL; current = current->next) {
        ruby_list_push(ruby_new_list, current->value);
    }

    OBJ_INFECT(ruby_new_list, self);
    if(OBJ_FROZEN(self)) {
        OBJ_FREEZE(ruby_new_list);
    }
    return ruby_new_list;
}

VALUE ruby_list_each(VALUE self) {
    Ruby_List *list;
    Ruby_List_Node *current;
    VALUE last = Qnil;

    Data_Get_Struct(self, Ruby_List, list);

    for(current = list->head; current != NULL; current = current->next) {
        last = rb_yield(current->value);
    }

    return last;
}

VALUE ruby_list_reverse_each(VALUE self) {
    Ruby_List *list;
    Ruby_List_Node *current;
    VALUE last = Qnil;

    Data_Get_Struct(self, Ruby_List, list);

    for(current = list->tail; current != NULL; current = current->prev) {
        last = rb_yield(current->value);
    }

    return last;
}

VALUE ruby_list_reverse(VALUE self) {
    VALUE ruby_new_list;
    Ruby_List *list;
    Ruby_List_Node *current;

    Data_Get_Struct(self, Ruby_List, list);

    ruby_new_list = ruby_list_new(0, 0, cList);

    for(current = list->tail; current != NULL; current = current->prev) {
        ruby_list_push(ruby_new_list, current->value);
    }

    return ruby_new_list;
}

VALUE ruby_list_reverse_bang(VALUE self) {
    VALUE ruby_new_list;
    Ruby_List *new_list;
    Ruby_List *list;
    Ruby_List_Node *tmp_head, *tmp_tail;

    Data_Get_Struct(self, Ruby_List, list);

    ruby_new_list = ruby_list_reverse(self);
    Data_Get_Struct(ruby_new_list, Ruby_List, new_list);

    /* This will ensure that the old list gets properly garbage collected */
    tmp_head = list->head;
    tmp_tail = list->tail;
    list->head = new_list->head;
    list->tail = new_list->tail;
    new_list->head = tmp_head;
    new_list->tail = tmp_tail;

    return self;
}
    
VALUE ruby_list_first(VALUE self) {
    Ruby_List *list;
    
    Data_Get_Struct(self, Ruby_List, list);
        
    if(list->head) {
        return list->head->value;
    } else {
        return Qnil;
    }
}

VALUE ruby_list_last(VALUE self) {
    Ruby_List *list;
    
    Data_Get_Struct(self, Ruby_List, list);
        
    if(list->tail) {
        return list->tail->value;
    } else {
        return Qnil;
    }
}

VALUE ruby_list_size(VALUE self, VALUE other) {
    Ruby_List * list;

    Data_Get_Struct(self, Ruby_List, list);

    return INT2NUM(list->size);
}

VALUE ruby_list_compare(VALUE self, VALUE other) {
    Ruby_List *li, *lj;
    Ruby_List_Node *i, *j;
    VALUE ruby_comp;
    int comp;

    Data_Get_Struct(self, Ruby_List, li);
    Data_Get_Struct(other, Ruby_List, lj);
    
    for(i = li->head, j = lj->head;
        i != NULL && j != NULL;
        i = i->next, j = j->next) {
        ruby_comp = rb_funcall(i->value, rb_intern("<=>"), 1, j->value);
        comp = NUM2INT(ruby_comp);
        if(comp != 0) return ruby_comp;
    }

    if(i == NULL && j != NULL) return INT2NUM(-1);
    if(i != NULL && j == NULL) return INT2NUM(1);
    return INT2NUM(0);
}

void Init_list_helper(void) {
    cList = rb_define_class("List", rb_cObject);
    rb_define_singleton_method(cList, "new", ruby_list_new, -1);
    rb_define_method(cList, "empty?", ruby_list_empty, 0);
    rb_define_method(cList, "push", ruby_list_push, 1);
    rb_define_method(cList, "pop", ruby_list_pop, 0);
    rb_define_method(cList, "unshift", ruby_list_unshift, 1);
    rb_define_method(cList, "shift", ruby_list_shift, 0);
    rb_define_method(cList, "clone", ruby_list_clone, 0);
    rb_define_method(cList, "each", ruby_list_each, 0);
    rb_define_method(cList, "reverse_each", ruby_list_reverse_each, 0);
    rb_define_method(cList, "reverse", ruby_list_reverse, 0);
    rb_define_method(cList, "reverse!", ruby_list_reverse_bang, 0);
    rb_define_method(cList, "first", ruby_list_first, 0);
    rb_define_method(cList, "last", ruby_list_last, 0);
    rb_define_method(cList, "clear", ruby_list_clear, 0);
    rb_define_method(cList, "size", ruby_list_size, 0);
    rb_define_method(cList, "<=>", ruby_list_compare, 1);
    rb_define_alias(cList, "length", "size");
}