// Computer Science-y data structures
var linklist = {};

// Returns a simple structure of {value, previous, next}.
// link list generators should connect the previous and next attributes as
// needed.
linklist.ListItem = function(value) {
  this.value = value;
  this.previous = null;
  this.next = null;
  this.head = false;
  this.tail = false;
};

MochiKit.Base.update(linklist.ListItem.prototype, {
  __repr__: function() {
    return '[linklist.ListItem [' + this.value + ']]';
  },
  toString: function() { return this.__repr__(); },
  
  // Goes through the items applying ``fn(item.value)``,
  // returns the found item; `direction` can be 'previous' or 'next';
  // ('next' is default).
  find: function(fn, direction) {
    var m = MochiKit.Base;
    direction = direction || 'next';
    var current = this;
    var i = 0, limit = 5000;
    while(i < limit) {
      i += 1;
      if(m.isNull(current))
        return null;
      if(fn(current.value))
        return current;
      if(current.head && (direction == 'previous'))
        return null;
      if(current.tail && (direction == 'next'))
        return null;
      current = current[direction];
    }
    return null;
  }
});

// Generates a single linked list out of the sequence 'values';
// Returns the first item in the list. To create a circular list, add
// the option ``{circular: true}`` to the call.
linklist.Single = function(values, options) {
  var m = MochiKit.Base;
  options = m.update({circular: false}, options || {});
  
  var collected = [];
  MochiKit.Iter.forEach(values, function(v) {
    var item = new linklist.ListItem(v);
    if(collected.length > 0) {
      collected[(collected.length-1)].next = item;
    }
    collected.push(item);
  });

  collected[0].head = true;
  collected[(collected.length-1)].tail = true;

  if(options.circular) {
    collected[(collected.length-1)].next = collected[0];
  }

  return collected[0];
};


linklist.Double = function(values, options) {
  var m = MochiKit.Base;
  options = m.update({circular: false}, options || {});
  
  var collected = [];
  MochiKit.Iter.forEach(values, function(v) {
    var item = new linklist.ListItem(v);
    if(collected.length > 0) {
      item.previous = collected[(collected.length-1)];
      item.previous.next = item;
    }
    collected.push(item);
  });
  
  collected[0].head = true;
  collected[(collected.length-1)].tail = true;

  if(options.circular) {
    collected[0].previous = collected[(collected.length-1)];
    collected[(collected.length-1)].next = collected[0];
  };
  
  return collected[0];
};