/*  =LinkedList (Class) - An implementation of a circularly doubly linked list.
  -----------------------------------------------  */
  dojo.declare("LinkedList", null, {

  // Attributes
    length/*Number*/            : null,
    debugMode/*Boolean*/        : false,
    firstItem/*LinkedListItem*/ : null,
    nextID/*Number*/            : 0,

  // Methods
    constructor: function() {
      if (this.debugMode) console.log("LinkedList has initialized");
      this.length = 0;
    },
    isEmpty: function() {
      return this.firstItem == null;
    },
    getFirst: function()/*LinkedListItem*/ {
      return this.firstItem;
    },
    traceMe: function() {
      console.log("-----");
      if (this.isEmpty()) {
        console.log("List is empty");
      } else {
        this._forEach(dojo.hitch(this, function(nextItem, count) {
          console.log("[" + String(count) + "].data: " + nextItem.data + " (" + nextItem.id + ")");
        }));
      }
      console.log("-----");
    },
    getItem: function(testFunc/*Function*/)/*LinkedListItem*/ {
      var item = null;
      this._forEach(dojo.hitch(this, function(nextItem) {
        if (testFunc(nextItem)) item = nextItem;
      }));
      return item;
    },
    forEach: function(callback/*Function*/, thisObject/*Object*/) {
      this._forEach(dojo.hitch(this, function(nextItem, count) {
        if (thisObject != null) {
          thisObject.call(callback, nextItem.data, count);
        } else {
          callback(nextItem.data, count);
        }
      }));
    },
    _forEach: function(callback/*Function*/) {
      var count = 0;
      var nextItem = this.firstItem;
      do {
        callback(nextItem, count++);
        nextItem = nextItem.next;
      } while (nextItem.isNotEqualTo(this.firstItem));
    },
    remove: function(isTarget/*Function*/) {
      if (typeof (isTarget) != "function") return;
      
      var target = null;
      this._forEach(dojo.hitch(this, function(next) {
        if (isTarget(next)) target = next;
      }));
      if (target!= null) {
        if (target.isEqualTo(this.firstItem)) {
          this.firstItem = this.firstItem.next;
        }
        return this._remove(target);
      } else {
        console.warn("The target LinkedListItem was not found.");
        return null;
      }
    },
    _remove: function(target/*LinkedListItem*/) {
      // If we're removing the only item in the list
      if (target.isEqualTo(target.next)) {
        this.firstItem = null;
      }
      
      target.next.previous = target.previous;
      target.previous.next = target.next;
      
      this.length--;
      return target.data;
    },
    insertBefore: function(data, target/*LinkedListItem*/) {
      var newItem = new LinkedListItem(String(this.nextID++));
      newItem.data = data;
      
      if (target.isEqualTo(this.firstItem)) {
        this.unshift(data);
      } else {
        // Tell the new item who its neighbors are
        newItem.next = target;
        newItem.previous = target.previous;
        
        // Tell the new item's neighbors about the new item
        target.previous.next = newItem;
        target.previous = newItem;
        
        this.length++;
      }
      
      return newItem;
    },
    push: function(data/*Object*/)/*LinkedListItem*/ {
      //if (this.debugMode) console.log("LinkedList.push(" + data + ")");

      // Create the new item
      var newItem = new LinkedListItem(String(this.nextID++));
      newItem.data = data;

      // If this is the first and only item in the list, point everything to it.
      if (this.isEmpty()) {
        //if (this.debugMode) console.log("this.firstItem == null: " + (this.firstItem == null));
        //if (this.debugMode) console.log("LinkedList is empty. LinkedList.firstItem.data: " + this.firstItem.data);
        this.firstItem = newItem;
        this.firstItem.previous = this.firstItem;
        this.firstItem.next = this.firstItem;
        //if (this.debugMode) console.log("LinkedList.firstItem.data: " + this.firstItem.data);
      }

      // Add the new item after the last item in the list
      var lastItem = this.firstItem.previous;
      lastItem.next = newItem;  
      newItem.previous = lastItem;

      // Complete the loop
      newItem.next = this.firstItem;
      this.firstItem.previous = newItem;

      this.length++;

      return newItem;
    },
    pop: function()/*Object*/ {
      if (this.isEmpty()) {
        console.error("Objects of type LinkedList must contain data before you attempt to pop");
        return;
      }
      var target = this.firstItem.previous;
      
      return this._remove(target);
    },
    shift: function()/*Object*/ {
      if (this.isEmpty()) {
        console.error("Objects of type LinkedList must contain data before you attempt to shift");
        return;
      }

      // First we want to change the current "first" to the next item in the list.
      this.firstItem = this.firstItem.next;

      // Now we can just pop to get rid of the target item.
      return this.pop();
    },
    unshift: function(data/*Object*/)/*LinkedListItem*/ {
      var newItem = this.push(data);

      // At this point we have added the new item at the end of the list. We just need to move it to the beginning.
      this.firstItem = newItem;

      return newItem;
    }
  });
  
/*  =LinkedListItem (Class)
  ----------------------------------------------- */
  dojo.declare("LinkedListItem", null, {

  // Attributes
    id/*String*/                : null,
    data/*Object*/              : null, 
    next/*LinkedListItem*/      : null,
    previous/*LinkedListItem*/  : null,
    debugMode/*Boolean*/        : false,

  // Methods
    constructor: function(id/*String*/) {
      this.id = id;
    },
    isEqualTo: function(target/*LinkedListItem*/)/*Boolean*/ {
      if (this.debugMode) console.log(this.id + ".isEqualTo(" + target.id + ")");
      return (this.id == target.id);
    },
    isNotEqualTo: function(target/*LinkedListItem*/)/*Boolean*/ {
      if (this.debugMode) console.log(this.id + ".isNotEqualTo(" + target.id + ")");
      return (this.id != target.id);
    }
  });