/* The main difference between this linked list implementation and the 
 * one in 'structures' is that this one supports MochiKit iterators and
 * could probably be configured for other iterators as well.
 */
var linkedlist = (function(){
    var m = MochiKit.Base,
        itertools = MochiKit.Iter,
        for_each = MochiKit.Iter.forEach;
    
    var Sentinal = function() {this.is_sentinal = true;};
    var _sentinal = new Sentinal();
    
    var LinkedList = function(first_node) {
        this.first_node = first_node;
    };
    m.update(LinkedList.prototype, {
        __repr__: function() {
            return '[collection.LinkedList [' + this.first_node + ']]';
        },
        toString: function() {return this.__repr__();},
        iter: function() {
            return new LinkListIterator(this.first_node);
        }
    });
    
    var LinkListNode = function(value) {
        this.value = value;
        this.previous_node = null;
        this.next_node = null;

        this.is_head = false;
        this.is_tail = false;
    };
    m.update(LinkListNode.prototype, {
        __repr__: function() {
            return '[collection.LinkListNode [' + this.value + ']]';
        },
        toString: function() { return this.__repr__(); },
        
        iter: function() {
            return new LinkListIterator(this);
        }
    });
    

    // Waaa. this gets a bit complicated.. somewhat.  but it works.
    // It provides the basic iterator interface, along with the ability
    // to get the current and previous nodes.
    var LinkListIterator = function(node) {
        var next_node = node,
            current_node = node.previous_node,
            previous_node = null;

        if(current_node)
            previous_node = current_node.previous_node;

        var shift_previous = function() {
            next_node = current_node;
            current_node = previous_node;
            if(next_node && !current_node)
                current_node = next_node.previous_node;

            if(!current_node) {
                previous_node = null;
            }
            else {
                previous_node = current_node.previous_node;
                next_node = current_node.next_node;
            }
        };
        var shift_next = function() {
            previous_node = current_node;
            current_node = next_node;
            if(!current_node) {
                next_node = null;
            }
            else {
                previous_node = current_node.previous_node;
                next_node = current_node.next_node;
            }
        };

        return {
            repr: function() { 
                return "LinkListIterator[current_node: "+repr(current_node)+"]";
            },
            toString: m.forwardCall('repr'),
            next: function() {
                shift_next();
                if(m.isUndefinedOrNull(current_node)) {
                    throw itertools.StopIteration;
                }
                return current_node.value;
            },
            previous: function() {
                shift_previous();
                if(m.isUndefinedOrNull(current_node)) {
                    throw itertools.StopIteration;
                }
                return current_node.value;
            },
            current: function() {
                return current_node;
            }
        };
    };
    
    
    var build_list = function(values, options) {
        options = m.update({
            circular: false,
            double_link: false
        }, options || {});
        
        var collected = [];
        for_each(values, function(v) {
            var item = new LinkListNode(v);
            if(collected.length > 0) {
                var previous = collected[(collected.length-1)];
                previous.next_node = item;
                if(options.double_link)
                    item.previous_node = previous;
            }
            collected.push(item);
        });

        var head_node = collected[0],
            tail_node = collected[(collected.length-1)];
        
        head_node.is_head = true;
        tail_node.is_tail = true;
        
        if(options.circular) {
            tail_node.next_node = head_node;
            if(options.double_link)
                head_node.previous_node = tail_node;
        }
        
        return new LinkedList(head_node);
    };

    var Double = function(values, options) {
        options = m.update({double_link: true}, options || {});
        return build_list(values, options);
    };
    var Single = function(values, options) {
        options = m.update({double_link: false}, options || {});
        return build_list(values, options);
    };

    /* Export! */
    return {
        'Double': Double,
        'Single': Single,
        'LinkListIterator': LinkListIterator,
        'LinkListNode': LinkListNode,

        'LinkedList': LinkedList,
        'build_list': build_list
    };

})();