arunsah · October 27, 2020 01:00
diff --git a/walkers-algorithm-with-canvas.js.html b/walkers-algorithm-with-canvas.js.html
 <html>
  <head>
    <meta http-equiv="Content-type" content="text/html; charset=Shift_JIS">
    <title>TEST</title>
  </head>
  <body>
    <div id="example-input">
      <div>
        <div>
          <ul>
            <li><a href="#">ITEM1</a></li>
            <li><a href="#">ITEM2</a></li>
            <li>
              <div>
                ITEM3
                <ul>
                  <li>SUBITEM1</li>
                  <li>
                    <div>
                      <span>SUBSUBITEM1</span>
                      <span>SUBSUBITEM2</span>
                      <span>SUBSUBITEM3</span>
                      <span>
                        <div>WOOHOO1</div>
                        <div>WOOHOO2</div>
                        <div>WOOHOO3</div>
                        <div>WOOHOO4</div>
                      </span>
                    </div>
                  </li>
                </ul>
              </div>
            </li>
          </ul>
          <div>ITEM4</div>
          <div>
            <table>
              <tbody>
                <tr>
                  <th></th>
                  <th>COLUMN1</th>
                  <th>COLUMN2</th>
                </tr>
                <tr>
                  <td>ROW1</td>
                  <td>1-1</td>
                  <td>1-2</td>
                </tr>
                <tr>
                  <td>ROW2</td>
                  <td>2-1</td>
                  <td>2-2</td>
                </tr>
              </tbody>
            </table>
            ITEM5
            <br />
          </div>
          <div>
            ITEM6
            <br />
            <br />
          </div>
        </div>
      </div>
    </div>

    <canvas id="example-output" width="800" height="600"></canvas>

    <script language="Javascript" type="text/javascript">
 <!--
 /* Prints out the given context, this implementation is for Chrome only. */
 var debug = function debug() {
  console.log(this);
 };

 /* Cleans up whitespaces from the given DOM node. */
 var clean = function clean(node) {
  for (var i = 0; i < node.childNodes.length; i++) {
    var child = node.childNodes[i];
    if (child.nodeType == 3 && !/\S/.test(child.nodeValue)) {
      node.removeChild(child);
      i--;
    }
    if (child.nodeType == 1) {
      clean(child);
    }
  }
  return node;
 };

 /*
 * Represents Knuth's threaded node class.
 */
 var Node = function _Class_Of_Node_(_parent, _leftSibling, _rightSibling, _leftNeighbor, _children) {
  // Holds parent node.
  this.parent = _parent ? _parent : null;
  // Holds left sibling node.
  this.leftSibling = _leftSibling ? _leftSibling : null;
  // Holds right sibling node.
  this.rightSibling = _rightSibling ? _rightSibling : null;
  // Holds left neighbor node.
  this.leftNeighbor = _leftNeighbor ? _leftNeighbor : null;
  // Holds child nodes.
  this.children = _children ? _children : [];
  // Holds x coordinate.
  this.x = 0;
  // Holds y coordinate.
  this.y = 0;
  // Holds preliminary coordinate.
  this.preliminary = 0;
  // Holds modifier coordinate.
  this.modifier = 0;
  // Holds level.
  this.level = 0;
 };

 /** Returns the next node in preporder. */
 Node.prototype.nextInPreorder = function nextInPreorder() {
  if (!this.children || this.children.length === 0) {
    var node = this;
    while (node.parent && !node.rightSibling) {
      node = this.parent
    }
    if (node.rightSibling) {
      return node.rightSibling;
    } else {
      return null;
    }
  } else {
    return this.children[0];
  }
 };

 /** Returns the previous node in preporder. */
 Node.prototype.prevInPreorder = function prevInPreorder() {
  if (this.leftSibling) {
    var node = this.leftSibling;
    while (node.children && node.children.length >= 1) {
      node = node.children[node.children.length - 1];
    }
    return node;
  } else {
    if (this.parent) {
      return this.parent;
    } else {
      return null;
    }
  }
 };

 /** Returns the next node in postorder. */
 Node.prototype.nextInPostorder = function nextInPostorder() {
  if (this.rightSibling) {
    var node = this.rightSibling;
    while (node.children && node.children.length >= 1) {
      node = node.children[0];
    }
    return node;
  } else {
    if (this.parent) {
      return this.parent;
    } else {
      return null;
    }
  }
 };

 /** Returns the previous node in postorder. */
 Node.prototype.prevInPostorder = function prevInPostorder() {
  if (!this.children || this.children.length === 0) {
    var node = this;
    while (node.parent && !node.leftSibling) {
      node = this.parent;
    }
    if (node.leftSibling) {
      return node.leftSibling;
    } else {
      return null;
    }
  } else {
    return this.children[this.children.length - 1];
  }
 };

 /** Sets the parent node. */
 Node.prototype.setParent = function setParent(node) {
  this.parent = node;
  return this;
 };

 /** Adds a child node. */
 Node.prototype.addChild = function addChild(node) {
  this.children.push(node);
  return this;
 };

 /** Sets the left sibling node. */
 Node.prototype.setLeftSibling = function setLeftSibling(node) {
  this.leftSibling = node;
  return this;
 };

 /** Sets the right sibling node. */
 Node.prototype.setRightSibling = function setRightSibling(node) {
  this.rightSibling = node;
  return this;
 };

 /** Sets the left neighbor node. */
 Node.prototype.setLeftNeighbor = function setLeftNeighbor(node) {
  this.leftNeighbor = node;
  return this;
 };

 /** Sets the left most node. */
 Node.prototype.getLeftMost = function getLeftMost(depth) {
  if (depth <= 0) {
    return this;
  } else if (!this.children || this.children.length === 0) {
    return null;
  } else {
    var ancestor = this.children[0];
    var leftMost = ancestor.getLeftMost(depth - 1);
    while (!leftMost && ancestor.rightSibling) {
      ancestor = ancestor.rightSibling;
      leftMost = ancestor.getLeftMost(depth - 1);
    }
    return leftMost;
  }
 };

 /** Returns the level. */
 Node.prototype.getLevel = function getLevel() {
  if (this.level) {
    return this.level;
  } else {
    var level = 0;
    var node = this;
    while (node.parent) {
      level++;
      node = node.parent;
    }
    this.level = level;
    return level;
  }
 };

 /*
 * Represents Walker's Tree class.
 */
 var Tree = function _Class_Of_Tree_(node) {
  this.root = node || null;
  return this;
 };

 /** Applies given function to each node in preorder. */
 Tree.prototype.eachInPreorder = function eachInPreorder(callback, context) {
  var node = this.root;
  while (node) {
    callback.apply(node, context);
    node = node.nextInPreorder();
  }
 };

 /** Applies given function to each node in postorder. */
 Tree.prototype.eachInPostorder = function eachInPostorder(callback, context) {
  var node = this.root;
  while (node.children && node.children.length > 0) {
    node = node.children[0];
  }
  while (node) {
    callback.apply(node, context);
    node = node.nextInPostorder();
  }
 };

 /** Sets the tree's x coordinate. */
 Tree.prototype.setX = function setX(x) {
  this.root.x = x ? x : 0;
  return this;
 };

 /** Sets the tree's y coordinate. */
 Tree.prototype.setY = function setY(y) {
  this.root.y = y ? y : 0;
  return this;
 };

 /*
 * Represents queue class.
 */
 var Queue = function _Class_Of_Queue_(array) {
  this.queue = array ? array : [];
  return this;
 };

 /** Enqueues the given item. */
 Queue.prototype.enqueue = function enqueue(item) {
  this.queue.push(item);
 };

 /** Dequeues the currently handling queue. */
 Queue.prototype.dequeue = function dequeue() {
  if (this.queue.length > 0) {
    return this.queue.shift();
  } else {
    return null;
  }
 };

 /** Peeks the currently handling queue. */
 Queue.prototype.peek = function peek() {
  if (this.queue.length > 0) {
    return this.queue[0];
  } else {
    return null;
  }
 };

 /** Returns true if the currently handling queue is empty. */
 Queue.prototype.isEmpty = function isEmpty() {
  if (this.queue.length > 0) {
    return false;
  } else {
    return true;
  }
 };

 /*
 * Pseudo DOM object Class.
 */
 var DOMObject = function _Class_Of_DOM_Object_(node, args) {
  // Inherits from Node class.
  Node.apply(this, args);
  // Holds DOM node type.
  this.nodeType = node.nodeType || -1;
  // Holds DOM node name.
  this.nodeName = node.nodeName || "";
  // THIS IS FOR INTERNAL USE ONLY.
  this._childNodes = node.childNodes;
  // Configures node in accordance with the given context.
  switch (this.nodeType) {
  case DOMObject.TYPE['ELEMENT_NODE']:
    this.attributes = node.attributes || {};
    break;
  case DOMObject.TYPE['TEXT_NODE']:
    this.nodeValue = node.nodeValue;
    break;
  default:
  return null;
  }
  return this;
 };

 // Ad-hoc inheritance.
 DOMObject.prototype = Object.create(Node.prototype);

 /** Definitions for DOM node types. */
 DOMObject.TYPE = {
  'ELEMENT_NODE'                : 1,
  'ATTRIBUTE_NODE'              : 2,
  'TEXT_NODE'                   : 3,
  'CDATA_SECTION_NODE'          : 4,
  'ENTITY_REFERENCE_NODE'       : 5,
  'ENTITY_NODE'                 : 6,
  'PROCESSING_INSTRUCTION_NODE' : 7,
  'COMMENT_NODE'                : 8,
  'DOCUMENT_NODE'               : 9,
  'DOCUMENT_TYPE_NODE'          : 10,
  'DOCUMENT_FRAGMENT_NODE'      : 11,
  'NOTATION_NODE'               : 12
 };

 /** Returns true if the given node is valid. */
 DOMObject.prototype.validate = function validate() {
  if (this.nodeType === DOM.TYPE['ELEMENT_NODE'] || (this.nodeType === DOM.TYPE['TEXT_NODE'] && this.nodeValue.length > 0)) {
    return true;
  } else {
    return false;
  }
 };

 /*
 * Converts DOM to Walker's Tree.
 */
 var parse = function parse(element) {
  var queue = new Queue();
  var root = new DOMObject(element);
  for (var i = 0;  i < root._childNodes.length; i++) {
    var child = new DOMObject(root._childNodes[i]).setParent(root);
    root.addChild(child);
    queue.enqueue(child);
  }
  var leftSibling = null;
  var rightSibling = null;
  var leftNeighbor = null;
  while (!queue.isEmpty()) {
    var node = queue.dequeue();
    for (var i = 0; i < node._childNodes.length; i++) {
      var child = new DOMObject(node._childNodes[i]).setParent(node);
      node.addChild(child);
      queue.enqueue(child);
    }
    rightSibling = (!queue.isEmpty() && node.parent === queue.peek().parent) ? queue.peek() : null;
    node.setLeftSibling(leftSibling).setRightSibling(rightSibling).setLeftNeighbor(leftNeighbor);
    leftSibling = (!queue.isEmpty() && node.parent === queue.peek().parent) ? node : null;
    if (leftSibling != null) {
      leftNeighbor = leftSibling;
    } else {
      leftNeighbor = (!queue.isEmpty() && node.getLevel() === queue.peek().getLevel()) ? node : null;
    }
  }
  return new Tree(root);
 };

 /*
 * Represents Walker's algorithm itself.
 */
 Algorithm = {
  'xAdjustment'       : 10,
  'yAdjustment'       : 10,
  'levelSeparation'   : 40,
  'siblingSeparation' : 40,
  'subtreeSeparation' : 30,
  'nodeWidth'         : 10,
  'nodeHeight'        : 10
 };

 /** Positions tree in accordance with the assigned configuration. */
 Algorithm.position = function position(tree) {
  tree.eachInPostorder(Algorithm.firstWalk);
  Algorithm.xAdjustment = tree.root.x - tree.root.preliminary;
  Algorithm.yAdjustment = tree.root.y;
  Algorithm.secondWalk(tree.root, 0);
 };

 /** Walker's first walk. */
 Algorithm.firstWalk = function firstWalk() {
  if (!this.children || this.children.length === 0) {
    if (this.leftSibling) {
      this.preliminary = this.leftSibling.preliminary
      + Algorithm.siblingSeparation
      + Algorithm.nodeWidth;
    } else {
      this.preliminary = 0;
    }
  } else {
    var leftMost = this.children[0];
    var rightMost = this.children[this.children.length - 1];
    var middle = (leftMost.preliminary + rightMost.preliminary) / 2;
    if (this.leftSibling) {
      this.preliminary = this.leftSibling.preliminary
        + Algorithm.siblingSeparation
        + Algorithm.nodeWidth;
      this.modifier = this.preliminary - middle;
      Algorithm.apportion(this);
    } else {
      this.preliminary = middle;
    }
  }
 };

 /** Apportions for given node in accordance with the handling context. */
 Algorithm.apportion = function apportion(node) {
  var leftMost = node;
  var neighbor = node.leftNeighbor;
  var depth = 0;
  while (leftMost && neighbor) {
    var leftModifier = 0;
    var rightModifier = 0;
    var ancestorLeftMost = leftMost;
    var ancestorNeighbor = neighbor;
    for (var i = 0; i < depth; i++) {
      ancestorLeftMost = ancestorLeftMost.parent;
      ancestorNeighbor = ancestorNeighbor.parent;
      rightModifier += ancestorLeftMost.modifier;
      leftModifier += ancestorNeighbor.modifier;
    }
    var moveDistance = neighbor.preliminary
      + leftModifier
      + Algorithm.nodeWidth
      + Algorithm.subtreeSeparation
      - leftMost.preliminary 
      - rightModifier;
    if (moveDistance > 0) {
      var tmp = node;
      var leftSiblings = 0;
      while (tmp && tmp !== ancestorNeighbor) {
        leftSiblings++;
        tmp = tmp.leftSibling;
      }
      if (tmp) {
        var portion = moveDistance / leftSiblings;
        tmp = node;
        while (tmp && tmp !== ancestorNeighbor) {
          tmp.preliminary = tmp.preliminary + moveDistance;
          tmp.modifier = tmp.modifier + moveDistance;
          moveDistance = moveDistance - portion;
          tmp = tmp.leftSibling;
        }
      } else {
        return;
      }
    }
    depth++;
    leftMost = node.getLeftMost(depth);
    if (leftMost) {
      neighbor = leftMost.leftNeighbor;
    }
  }
 };

 /** Walker's second walk. */
 Algorithm.secondWalk = function secondWalk(node, modifier) {
  node.x = Algorithm.xAdjustment + node.preliminary
    + modifier;
  node.y = Algorithm.yAdjustment
    + (node.getLevel() * Algorithm.levelSeparation);
  if (node.children && node.children.length > 0) {
    Algorithm.secondWalk(node.children[0], modifier + node.modifier);
  }
  if (node.rightSibling) {
    Algorithm.secondWalk(node.rightSibling, modifier);
  }
 };

 /** Draws tree. */
 Algorithm.render = function render(context) {
  context.fillRect(this.x, this.y, Algorithm.nodeWidth, Algorithm.nodeHeight);
  context.fillText(this.nodeName, this.x + Algorithm.nodeWidth * 1.5, this.y + Algorithm.nodeHeight);
  context.beginPath();
  for (var i = 0; i < this.children.length; i++) {
    context.moveTo(this.x + Algorithm.nodeWidth / 2, this.y + Algorithm.nodeHeight);
    context.lineTo(this.children[i].x + Algorithm.nodeWidth / 2, this.children[i].y);
    context.stroke();
  }
 };

 /** Caluculates each node's positions. */
 var tree = parse(clean(document.getElementById('example-input').cloneNode(true)));
 tree.setX(400).setY(0);
 Algorithm.position(tree);

 /** Draws rendered tree in canvas. */
 var canvas = document.getElementById('example-output');
 var context = canvas.getContext('2d');
 context.strokeStyle = 'rgb(00, 00, 00)';
 context.fillStyle = 'rgb(00, 00, 00)';
 tree.eachInPostorder(Algorithm.render, [context]);
 -->
    </script>
  </body>
 </html>
	<html>
	<head>
	<meta http-equiv="Content-type" content="text/html; charset=Shift_JIS">
	<title>TEST</title>
	</head>
	<body>
	<div id="example-input">
	<div>
	<div>
	<ul>
	<li><a href="#">ITEM1</a></li>
	<li><a href="#">ITEM2</a></li>
	<li>
	<div>
	ITEM3
	<ul>
	<li>SUBITEM1</li>
	<li>
	<div>
	<span>SUBSUBITEM1</span>
	<span>SUBSUBITEM2</span>
	<span>SUBSUBITEM3</span>
	<span>
	<div>WOOHOO1</div>
	<div>WOOHOO2</div>
	<div>WOOHOO3</div>
	<div>WOOHOO4</div>
	</span>
	</div>
	</li>
	</ul>
	</div>
	</li>
	</ul>
	<div>ITEM4</div>
	<div>
	<table>
	<tbody>
	<tr>
	<th></th>
	<th>COLUMN1</th>
	<th>COLUMN2</th>
	</tr>
	<tr>
	<td>ROW1</td>
	<td>1-1</td>
	<td>1-2</td>
	</tr>
	<tr>
	<td>ROW2</td>
	<td>2-1</td>
	<td>2-2</td>
	</tr>
	</tbody>
	</table>
	ITEM5
	<br />
	</div>
	<div>
	ITEM6
	<br />
	<br />
	</div>
	</div>
	</div>
	</div>

	<canvas id="example-output" width="800" height="600"></canvas>

	<script language="Javascript" type="text/javascript">
	<!--
	/* Prints out the given context, this implementation is for Chrome only. */
	var debug = function debug() {
	console.log(this);
	};

	/* Cleans up whitespaces from the given DOM node. */
	var clean = function clean(node) {
	for (var i = 0; i < node.childNodes.length; i++) {
	var child = node.childNodes[i];
	if (child.nodeType == 3 && !/\S/.test(child.nodeValue)) {
	node.removeChild(child);
	i--;
	}
	if (child.nodeType == 1) {
	clean(child);
	}
	}
	return node;
	};

	/*
	* Represents Knuth's threaded node class.
	*/
	var Node = function _Class_Of_Node_(_parent, _leftSibling, _rightSibling, _leftNeighbor, _children) {
	// Holds parent node.
	this.parent = _parent ? _parent : null;
	// Holds left sibling node.
	this.leftSibling = _leftSibling ? _leftSibling : null;
	// Holds right sibling node.
	this.rightSibling = _rightSibling ? _rightSibling : null;
	// Holds left neighbor node.
	this.leftNeighbor = _leftNeighbor ? _leftNeighbor : null;
	// Holds child nodes.
	this.children = _children ? _children : [];
	// Holds x coordinate.
	this.x = 0;
	// Holds y coordinate.
	this.y = 0;
	// Holds preliminary coordinate.
	this.preliminary = 0;
	// Holds modifier coordinate.
	this.modifier = 0;
	// Holds level.
	this.level = 0;
	};

	/** Returns the next node in preporder. */
	Node.prototype.nextInPreorder = function nextInPreorder() {
	if (!this.children \|\| this.children.length === 0) {
	var node = this;
	while (node.parent && !node.rightSibling) {
	node = this.parent
	}
	if (node.rightSibling) {
	return node.rightSibling;
	} else {
	return null;
	}
	} else {
	return this.children[0];
	}
	};

	/** Returns the previous node in preporder. */
	Node.prototype.prevInPreorder = function prevInPreorder() {
	if (this.leftSibling) {
	var node = this.leftSibling;
	while (node.children && node.children.length >= 1) {
	node = node.children[node.children.length - 1];
	}
	return node;
	} else {
	if (this.parent) {
	return this.parent;
	} else {
	return null;
	}
	}
	};

	/** Returns the next node in postorder. */
	Node.prototype.nextInPostorder = function nextInPostorder() {
	if (this.rightSibling) {
	var node = this.rightSibling;
	while (node.children && node.children.length >= 1) {
	node = node.children[0];
	}
	return node;
	} else {
	if (this.parent) {
	return this.parent;
	} else {
	return null;
	}
	}
	};

	/** Returns the previous node in postorder. */
	Node.prototype.prevInPostorder = function prevInPostorder() {
	if (!this.children \|\| this.children.length === 0) {
	var node = this;
	while (node.parent && !node.leftSibling) {
	node = this.parent;
	}
	if (node.leftSibling) {
	return node.leftSibling;
	} else {
	return null;
	}
	} else {
	return this.children[this.children.length - 1];
	}
	};

	/** Sets the parent node. */
	Node.prototype.setParent = function setParent(node) {
	this.parent = node;
	return this;
	};

	/** Adds a child node. */
	Node.prototype.addChild = function addChild(node) {
	this.children.push(node);
	return this;
	};

	/** Sets the left sibling node. */
	Node.prototype.setLeftSibling = function setLeftSibling(node) {
	this.leftSibling = node;
	return this;
	};

	/** Sets the right sibling node. */
	Node.prototype.setRightSibling = function setRightSibling(node) {
	this.rightSibling = node;
	return this;
	};

	/** Sets the left neighbor node. */
	Node.prototype.setLeftNeighbor = function setLeftNeighbor(node) {
	this.leftNeighbor = node;
	return this;
	};

	/** Sets the left most node. */
	Node.prototype.getLeftMost = function getLeftMost(depth) {
	if (depth <= 0) {
	return this;
	} else if (!this.children \|\| this.children.length === 0) {
	return null;
	} else {
	var ancestor = this.children[0];
	var leftMost = ancestor.getLeftMost(depth - 1);
	while (!leftMost && ancestor.rightSibling) {
	ancestor = ancestor.rightSibling;
	leftMost = ancestor.getLeftMost(depth - 1);
	}
	return leftMost;
	}
	};

	/** Returns the level. */
	Node.prototype.getLevel = function getLevel() {
	if (this.level) {
	return this.level;
	} else {
	var level = 0;
	var node = this;
	while (node.parent) {
	level++;
	node = node.parent;
	}
	this.level = level;
	return level;
	}
	};

	/*
	* Represents Walker's Tree class.
	*/
	var Tree = function _Class_Of_Tree_(node) {
	this.root = node \|\| null;
	return this;
	};

	/** Applies given function to each node in preorder. */
	Tree.prototype.eachInPreorder = function eachInPreorder(callback, context) {
	var node = this.root;
	while (node) {
	callback.apply(node, context);
	node = node.nextInPreorder();
	}
	};

	/** Applies given function to each node in postorder. */
	Tree.prototype.eachInPostorder = function eachInPostorder(callback, context) {
	var node = this.root;
	while (node.children && node.children.length > 0) {
	node = node.children[0];
	}
	while (node) {
	callback.apply(node, context);
	node = node.nextInPostorder();
	}
	};

	/** Sets the tree's x coordinate. */
	Tree.prototype.setX = function setX(x) {
	this.root.x = x ? x : 0;
	return this;
	};

	/** Sets the tree's y coordinate. */
	Tree.prototype.setY = function setY(y) {
	this.root.y = y ? y : 0;
	return this;
	};

	/*
	* Represents queue class.
	*/
	var Queue = function _Class_Of_Queue_(array) {
	this.queue = array ? array : [];
	return this;
	};

	/** Enqueues the given item. */
	Queue.prototype.enqueue = function enqueue(item) {
	this.queue.push(item);
	};

	/** Dequeues the currently handling queue. */
	Queue.prototype.dequeue = function dequeue() {
	if (this.queue.length > 0) {
	return this.queue.shift();
	} else {
	return null;
	}
	};

	/** Peeks the currently handling queue. */
	Queue.prototype.peek = function peek() {
	if (this.queue.length > 0) {
	return this.queue[0];
	} else {
	return null;
	}
	};

	/** Returns true if the currently handling queue is empty. */
	Queue.prototype.isEmpty = function isEmpty() {
	if (this.queue.length > 0) {
	return false;
	} else {
	return true;
	}
	};

	/*
	* Pseudo DOM object Class.
	*/
	var DOMObject = function _Class_Of_DOM_Object_(node, args) {
	// Inherits from Node class.
	Node.apply(this, args);
	// Holds DOM node type.
	this.nodeType = node.nodeType \|\| -1;
	// Holds DOM node name.
	this.nodeName = node.nodeName \|\| "";
	// THIS IS FOR INTERNAL USE ONLY.
	this._childNodes = node.childNodes;
	// Configures node in accordance with the given context.
	switch (this.nodeType) {
	case DOMObject.TYPE['ELEMENT_NODE']:
	this.attributes = node.attributes \|\| {};
	break;
	case DOMObject.TYPE['TEXT_NODE']:
	this.nodeValue = node.nodeValue;
	break;
	default:
	return null;
	}
	return this;
	};

	// Ad-hoc inheritance.
	DOMObject.prototype = Object.create(Node.prototype);

	/** Definitions for DOM node types. */
	DOMObject.TYPE = {
	'ELEMENT_NODE' : 1,
	'ATTRIBUTE_NODE' : 2,
	'TEXT_NODE' : 3,
	'CDATA_SECTION_NODE' : 4,
	'ENTITY_REFERENCE_NODE' : 5,
	'ENTITY_NODE' : 6,
	'PROCESSING_INSTRUCTION_NODE' : 7,
	'COMMENT_NODE' : 8,
	'DOCUMENT_NODE' : 9,
	'DOCUMENT_TYPE_NODE' : 10,
	'DOCUMENT_FRAGMENT_NODE' : 11,
	'NOTATION_NODE' : 12
	};

	/** Returns true if the given node is valid. */
	DOMObject.prototype.validate = function validate() {
	if (this.nodeType === DOM.TYPE['ELEMENT_NODE'] \|\| (this.nodeType === DOM.TYPE['TEXT_NODE'] && this.nodeValue.length > 0)) {
	return true;
	} else {
	return false;
	}
	};

	/*
	* Converts DOM to Walker's Tree.
	*/
	var parse = function parse(element) {
	var queue = new Queue();
	var root = new DOMObject(element);
	for (var i = 0; i < root._childNodes.length; i++) {
	var child = new DOMObject(root._childNodes[i]).setParent(root);
	root.addChild(child);
	queue.enqueue(child);
	}
	var leftSibling = null;
	var rightSibling = null;
	var leftNeighbor = null;
	while (!queue.isEmpty()) {
	var node = queue.dequeue();
	for (var i = 0; i < node._childNodes.length; i++) {
	var child = new DOMObject(node._childNodes[i]).setParent(node);
	node.addChild(child);
	queue.enqueue(child);
	}
	rightSibling = (!queue.isEmpty() && node.parent === queue.peek().parent) ? queue.peek() : null;
	node.setLeftSibling(leftSibling).setRightSibling(rightSibling).setLeftNeighbor(leftNeighbor);
	leftSibling = (!queue.isEmpty() && node.parent === queue.peek().parent) ? node : null;
	if (leftSibling != null) {
	leftNeighbor = leftSibling;
	} else {
	leftNeighbor = (!queue.isEmpty() && node.getLevel() === queue.peek().getLevel()) ? node : null;
	}
	}
	return new Tree(root);
	};

	/*
	* Represents Walker's algorithm itself.
	*/
	Algorithm = {
	'xAdjustment' : 10,
	'yAdjustment' : 10,
	'levelSeparation' : 40,
	'siblingSeparation' : 40,
	'subtreeSeparation' : 30,
	'nodeWidth' : 10,
	'nodeHeight' : 10
	};

	/** Positions tree in accordance with the assigned configuration. */
	Algorithm.position = function position(tree) {
	tree.eachInPostorder(Algorithm.firstWalk);
	Algorithm.xAdjustment = tree.root.x - tree.root.preliminary;
	Algorithm.yAdjustment = tree.root.y;
	Algorithm.secondWalk(tree.root, 0);
	};

	/** Walker's first walk. */
	Algorithm.firstWalk = function firstWalk() {
	if (!this.children \|\| this.children.length === 0) {
	if (this.leftSibling) {
	this.preliminary = this.leftSibling.preliminary
	+ Algorithm.siblingSeparation
	+ Algorithm.nodeWidth;
	} else {
	this.preliminary = 0;
	}
	} else {
	var leftMost = this.children[0];
	var rightMost = this.children[this.children.length - 1];
	var middle = (leftMost.preliminary + rightMost.preliminary) / 2;
	if (this.leftSibling) {
	this.preliminary = this.leftSibling.preliminary
	+ Algorithm.siblingSeparation
	+ Algorithm.nodeWidth;
	this.modifier = this.preliminary - middle;
	Algorithm.apportion(this);
	} else {
	this.preliminary = middle;
	}
	}
	};

	/** Apportions for given node in accordance with the handling context. */
	Algorithm.apportion = function apportion(node) {
	var leftMost = node;
	var neighbor = node.leftNeighbor;
	var depth = 0;
	while (leftMost && neighbor) {
	var leftModifier = 0;
	var rightModifier = 0;
	var ancestorLeftMost = leftMost;
	var ancestorNeighbor = neighbor;
	for (var i = 0; i < depth; i++) {
	ancestorLeftMost = ancestorLeftMost.parent;
	ancestorNeighbor = ancestorNeighbor.parent;
	rightModifier += ancestorLeftMost.modifier;
	leftModifier += ancestorNeighbor.modifier;
	}
	var moveDistance = neighbor.preliminary
	+ leftModifier
	+ Algorithm.nodeWidth
	+ Algorithm.subtreeSeparation
	- leftMost.preliminary
	- rightModifier;
	if (moveDistance > 0) {
	var tmp = node;
	var leftSiblings = 0;
	while (tmp && tmp !== ancestorNeighbor) {
	leftSiblings++;
	tmp = tmp.leftSibling;
	}
	if (tmp) {
	var portion = moveDistance / leftSiblings;
	tmp = node;
	while (tmp && tmp !== ancestorNeighbor) {
	tmp.preliminary = tmp.preliminary + moveDistance;
	tmp.modifier = tmp.modifier + moveDistance;
	moveDistance = moveDistance - portion;
	tmp = tmp.leftSibling;
	}
	} else {
	return;
	}
	}
	depth++;
	leftMost = node.getLeftMost(depth);
	if (leftMost) {
	neighbor = leftMost.leftNeighbor;
	}
	}
	};

	/** Walker's second walk. */
	Algorithm.secondWalk = function secondWalk(node, modifier) {
	node.x = Algorithm.xAdjustment + node.preliminary
	+ modifier;
	node.y = Algorithm.yAdjustment
	+ (node.getLevel() * Algorithm.levelSeparation);
	if (node.children && node.children.length > 0) {
	Algorithm.secondWalk(node.children[0], modifier + node.modifier);
	}
	if (node.rightSibling) {
	Algorithm.secondWalk(node.rightSibling, modifier);
	}
	};

	/** Draws tree. */
	Algorithm.render = function render(context) {
	context.fillRect(this.x, this.y, Algorithm.nodeWidth, Algorithm.nodeHeight);
	context.fillText(this.nodeName, this.x + Algorithm.nodeWidth * 1.5, this.y + Algorithm.nodeHeight);
	context.beginPath();
	for (var i = 0; i < this.children.length; i++) {
	context.moveTo(this.x + Algorithm.nodeWidth / 2, this.y + Algorithm.nodeHeight);
	context.lineTo(this.children[i].x + Algorithm.nodeWidth / 2, this.children[i].y);
	context.stroke();
	}
	};

	/** Caluculates each node's positions. */
	var tree = parse(clean(document.getElementById('example-input').cloneNode(true)));
	tree.setX(400).setY(0);
	Algorithm.position(tree);

	/** Draws rendered tree in canvas. */
	var canvas = document.getElementById('example-output');
	var context = canvas.getContext('2d');
	context.strokeStyle = 'rgb(00, 00, 00)';
	context.fillStyle = 'rgb(00, 00, 00)';
	tree.eachInPostorder(Algorithm.render, [context]);
	-->
	</script>
	</body>
	</html>