c4se記:さっちゃんですよ☆

.。oO(さっちゃんですよヾ(〃l _ l)ノ゙☆)

.。oO(此のblogは、主に音樂考察Programming に分類されますよ。ヾ(〃l _ l)ノ゙♬♪♡)

音樂は SoundCloud に公開中です。

考察は現在は主に Scrapbox で公表中です。

Programming は GitHub で開發中です。

JavaScript で色んなデータ構造(list/stack/queue/tree)

完全性を目指したものではありません。練習です。
双方向list, stack, queue, tree。
tree丈作る積りだったんですが、其の過程、必要に成って増えました。

/**
 * Reverse an Array.
 * @param Object[]
 * @return Object[]
 */
function reverse (arry) {
  return arry.reduceRight(function (acum, elm) {
    return acum.push(elm);
  }, []);
}


/**
 * @class ListNode
 * @param obj Object
 * @param prevNode ListNode (=null)
 * @param nextNode ListNode (=null)
 */
function ListNode (obj, prevNode, nextNode) {
  if (!(this instanceof ListNode)) {
    return new ListNode(obj);
  }
  this.data = obj;
  this.prev = prevNode;
  this.next = nextNode;
}


/**
 * @class List
 */
function List () {
  if (!(this instanceof List)) {
    return new List();
  }
  this.first = null;
  this.last = null;
}


List.prototype = {
  /**
   * @param obj Object
   * @return List
   */
  push: function (obj) {
    var newNode = new ListNode(obj);

    if (!this.first && !this.last) {
      this.first = this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return this;
  },


  /**
   * @return Object||undefined
   */
  pop: function () {
    var resultNode;

    if (!this.first && !this.last) {
      return void 0;
    }
    resultNode = this.last;
    this.last = resultNode.prev;
    resultNode.prev.next = null;
    return resultNode.data;
  },


  /**
   * @param obj Object
   * @return List
   */
  unshift: function (obj) {
    var newNode = new ListNode(obj);

    if (!this.first && !this.last) {
      this.first = this.last = newNode;
    } else {
      this.first.prev = newNode;
      this.first = newNode;
    }
    return this;
  },


  /**
   * @return Object||undefined
   */
  shift: function () {
    var resultNode;

    if (!this.first && !this.last) {
      return void 0;
    }
    resultNode = this.first;
    this.first = resultNode.next;
    resultNode.next.prev = null;
    return resultNode.data;
  },


  /**
   * @param fun Function
   *   fun(node, index, this)
   * @param obj Object (=null) this in fun.
   * @return List
   */
  forEach: function (fun, obj) {
    var i = 0,
        currentNode = this.first;

    while (currentNode) {
      fun.call(obj, currentNode, i, this);
      currentNode = currentNode.next;
      i += 1;
    }
    return this;
  },


  /**
   * @param fun Function
   *   fun(node, index, this)
   * @param obj Object (=null) this in fun.
   * @return List
   */
  map: function (fun, obj) {
    var result = new List(),
        i = 0,
        currentNode = this.first;

    while (currentNode) {
      result.push(new ListNode(fun.call(obj, currentNode, i, this));
      currentNode = currentNode.next;
      i += 1;
    }
    return result;
  },


  /**
   * @param fun Function
   *   fun(val, node, index, this)
   * @param val Object (=null)
   * @return Object
   */
  reduce: function (fun, val) {
    var resultVal = val,
        i = 0,
        currentNode = this.first;

    if (!currentNode) {
      return val;
    }
    if (resultVal === void 0) {
      resultVal = currentNode;
      currentNode = currentNode.next;
      i = 1;
    }
    while (currentNode) {
      resultVal = fun.call(null, resultVal, currentNode, i, this);
      currentNode = currentNode.next;
      i += 1;
    }
    return resultVal;
  }
};


/**
 * @class Queue
 */
function Queue () {
  if (!(this instanceof Queue)) {
    return new Queue();
  }
  this.datas = new List();
}


Queue.prototype = {
  /**
   * @param obj Object
   * @return Queue
   */
  enqueue: function (obj) {
    this.datas.push(obj);
    return this;
  },


  /**
   * @return Object||undefined
   */
  dequeue: function () {
    return this.datas.shift();
  },


  /**
   * @return Boolean
   */
  isEmpty: function () {
    return (!this.datas.first && !this.datas.last) ? true : false;
  }
};


/**
 * @class Stack
 */
function Stack () {
  if (!(this instanceof Stack)) {
    return new Stack();
  }
  this.datas = [];
}


Stack.prototype = {
  /**
   * @param Object
   * @return Stack
   */
  push: function (obj) {
    this.datas.push(obj);
    return this;
  },


  /**
   * @return Object||undefined
   */
  pop: function () {
    return this.datas.pop();
  },


  /**
   * @return Boolean
   */
  isEmpty: function () {
    return this.datas.length === 0;
  }
};


/**
 * @class TreeNode
 * @param obj Object
 * @param parentNode TreeNode (=null)
 * @param childNodes TreeNode[] (=[])
 */
function TreeNode (obj, parentNode, childNodes) {
  if (!(this instanceof TreeNode)) {
    return new TreeNode(obj, parentNode, childNodes);
  }
  childNodes = childNodes || [];
  parentNode && parentNode.appendChild(this);
  childs.forEach(function (child) {
    child.parent = this;
  });
  this.parent = parentNode;
  this.childs = childNodes;
}


TreeNode.prototype = {
  /**
   * @param node TreeNode
   * @return TreeNode
   */
  appendChild: function (node) {
    this.childs.push(node);
    node.parent = this;
    return this;
  },

  /**
   * @return Boolean
   */
  isLeaf: function () {
    return this.childs.length === 0;
  },

  /**
   * @return Boolean
   */
  isRoot: function () {
    return this.parent ? false : true;
  },

  
  /**
   * @param node TreeNode
   * @return Boolean
   */
  isChild: function (node) {
    return node.childs.indexOf(this) !== -1;
  },


  /**
   * @param node TreeNode
   * @return Boolean
   */
  isParent: function (node) {
    return node.parent === this;
  }
};


/**
 * @class Tree
 * @param rootNode TreeNode (=null)
 */
function Tree (rootNode) {
  if (!(this instanceof Tree)) {
    return new Tree(rootNode);
  }
  this.root = rootNode;
}


Tree.prototype = {
  /**
   * Breadth-first tracing.
   * @param fun Function
   *   fun(node, index, this)
   * @param obj Object (=null) this in fun.
   * @return Tree
   */
  forEachBreadth: function (fun, obj) {
    var currentNode,
        queue = new Queue(),
        i = 0;

    queue.enpueue(this.root);
    while (!queue.isEmpty) {
      currentNode = queue.dequeue();
      fun.call(obj, currentNode, i, this);
      i += 1;
      currentNode.childs.forEach(function (childNode) {
        queue.enqueue(childNode);
      });
    }
    return this;
  },


  /**
   * Depth-first at first tracing.
   * @param fun Function
   *   fun(node, index, this)
   * @param obj Object (=null) this in fun.
   * @return Tree
   */
  forEachDepthFirst: function (fun, obj) {
    var currentNode,
        stack = new Stack(),
        i = 0;

    stack.push(this.root);
    while (!stack.isEmpty) {
      currentNode = stack.pop();
      fun.call(obj, currentNode, i, this);
      i += 1;
      reverse(currentNode.childs).forEach(function (childNode) {
        stack.push(childNode):
      });
    }
    return this;
  },


  /**
   * Depth-first at middle tracing.
   * @param fun Function
   *   fun(node, index, this)
   * @param obj Object (=null) this in fun.
   * @return Tree
   */
  forEachDepthMiddle: function (fun, obj) {
  },


  /**
   * Depth-first at lest tracing.
   * @param fun Function
   *   fun(node, index, this)
   * @param obj Object (=null) this in fun.
   * @return Tree
   */
  forEachDepthLast: function (fun, obj) {
    var currentNode = this.root,
        prevNode,
        stack = new Stack(),
        i = 0;

    stack.push(this.root);
    while (!stack.isEmpty) {
      if (!currentNode.isLeaf()) {
        reverse(currentNode.childs).forEach(function (childNode) {
          stack.push(childNode);
        });
        currentNode = stack.pop();
        stack.push(currentNode);
      } else {
        while (currentNode.isLeaf() || currentNode.isParent(prevNode)) {
          fun.call(obj, currentNode, i, this);
          prevNode = stack.pop();
          i += 1;
          currentNode = stack.pop();
          stack.push(currentNode);
        }
      }
    }
    return this;
  }
};