// each data MUST have a 'value' property (for sorting)
// each data MUST have a 'id' property (for direct-access)

// data in SortedDirectAccessDoublyLinkedList are sorted by 'value', from min to max, in a doubly-linked list
// each node in the doubly-linked list is of the form {datum: , value: , prev: , next: }
// 'datum' refers to the original datum; 'value' is retrieved from data, below'/'above' refer to previous/next value-based nodes

function SortedDirectAccessDoublyLinkedList () {
  this._valueAccessor = // accessor to the value to sort on
    function (datum) {
    return datum.value;
  }
  this._min = null; // reference to the doubly-linked node with the min value
  this._max = null; // reference to the doubly-linked node with the max value
  this.size = 0 // number of data in the doubly-linked list
  this._idToNode = {}; // direct access to a node of the doubly-linked list
}

SortedDirectAccessDoublyLinkedList.prototype.valueAccessor = function (_) {
  if (!arguments.length) return this._valueAccessor;
  this._valueAccessor = _;

  //for chaining purpose
  return this;
};

SortedDirectAccessDoublyLinkedList.prototype.clear = function () {
  this._min = null;
  this._max = null;
  this.size = 0;
  this._idToNode = {};

  //for chaining purpose
  return this
};

SortedDirectAccessDoublyLinkedList.prototype.dln = function (datum){
  // dln = doubly-linked node
  return this._idToNode[datum.id];
};

SortedDirectAccessDoublyLinkedList.prototype.addMany = function (data) {

  data.forEach( function (datum, item) {
    this.add(datum);
  }, this)

  //for chaining purpose
  return this;
};

SortedDirectAccessDoublyLinkedList.prototype.add = function (datum){
  //create a new doubly-linked node
  var dln = {
    datum: datum, // original datum
    value: this._valueAccessor(datum),
    below: null,	// previous value-based node
    above: null		// next value-based node
  };

  //insert node in the adequate position in the doubly-linked list
  if (this.size === 0) { //special case: no node in the list yet
    this._min = this._max = dln;
  } else if (dln.value <= this._min.value) {//special case: new datum is the min
    dln.above = this._min;
    dln.above.below = dln;
    this._min = dln;
  } else if (dln.value >= this._max.value) { //special case: new datum is the max
    dln.below = this._max;
    dln.below.above = dln;
    this._max = dln;
  } else {
    //insert the node at the adequate position
    var current = this._max;
    //loop to find immediate below
    while (current.value > dln.value) {
      current = current.below;
    }
    dln.below = current;
    dln.above = current.above;
    dln.above.below = dln;
    dln.below.above = dln;
  }

  //direct access to the node
  this._idToNode[dln.datum.id] = dln;

  //update size
  this.size++;

  //for chaining purpose
  return this;
};

SortedDirectAccessDoublyLinkedList.prototype.remove = function (datum) {
  var dln = this.dln(datum);

  //remove node from the doubly-linked list
  if (this.size === 1) { //special case: last item to remove
    this._min = this._max = null;
  } else if (dln === this._min) { //special case: datum is the min
    this._min = this._min.above;
    this._min.below = null;
  } else if (dln === this._max) { //special case: datum is the max
    this._max = this._max.below;
    this._max.above = null;
  } else {
    //remove pointers to the node
    dln.above.below = dln.below;
    dln.below.above = dln.above;
  }

  dln = null // carbage collector
  delete this._idToNode[datum.id]; //remove direct access to the node

  //update size
  this.size--;

  //for chaining purpose
  return this;
}