JavaScript implementation of Walker's Algorithm by John Q. Walker (1989) based on Shingo OKAWA's implementation
Demo available at bl.ocks.org
JavaScript implementation of Walker's Algorithm by John Q. Walker (1989) based on Shingo OKAWA's implementation
Demo available at bl.ocks.org
<html> | |
<head> | |
<meta http-equiv="Content-type" content="text/html; charset=Shift_JIS"> | |
<title>Walkers</title> | |
</head> | |
<body> | |
<header> | |
<h1>Walker's Algorithm</h1> | |
<p>Source on <a href="https://gist.github.com/KyleMit/dfbf4a376f80f587d476bb484cceac02">gist</a> </p> | |
</header> | |
<main> | |
<textarea id="example-input"> | |
{ | |
"title": "Jones", | |
"children": [ | |
{ | |
"title": "Smith", | |
"children": [ | |
{ | |
"title": "A" | |
}, | |
{ | |
"title": "B", | |
"children": [ | |
{ | |
"title": "AA3" | |
}, | |
{ | |
"title": "BA4" | |
}, | |
{ | |
"title": "CA5" | |
} | |
] | |
}, | |
{ | |
"title": "C", | |
"children": [ | |
{ | |
"title": "Smith", | |
"children": [ | |
{ | |
"title": "A3" | |
}, | |
{ | |
"title": "B4" | |
}, | |
{ | |
"title": "C5" | |
} | |
] | |
} | |
] | |
} | |
] | |
} | |
] | |
} | |
</textarea> | |
<canvas id="example-output" width="800" height="600"></canvas> | |
</main> | |
<script src="./walker.js" type="text/javascript"></script> | |
<style> | |
*, | |
*:before, | |
*:after { | |
box-sizing: border-box; | |
} | |
html, | |
body { | |
margin: 0; | |
padding: 0; | |
min-height: 100vh; | |
} | |
body { | |
padding: 15px; | |
} | |
header { | |
text-align: center; | |
margin-bottom: 30px; | |
} | |
p { | |
margin-top: -10px; | |
} | |
main { | |
display: flex; | |
height: 80%; | |
flex-grow: 1; | |
} | |
textarea#example-input { | |
height: 100%; | |
width: 30%; | |
padding: 10px; | |
flex-grow: 1; | |
font-family: monospace; | |
} | |
canvas#example-output { | |
height: 100%; | |
width: 60%; | |
flex-grow: 2; | |
} | |
</style> | |
</body> | |
</html> |
/* 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.title || ""; | |
// THIS IS FOR INTERNAL USE ONLY. | |
this._childNodes = node.children || []; | |
// 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]) | |
child.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(); | |
} | |
}; | |
let inputArea = document.getElementById('example-input') | |
inputArea.addEventListener("change", updateTree) | |
inputArea.addEventListener("input", updateTree) | |
// run on startup | |
updateTree() | |
function updateTree() { | |
let inputText = inputArea.value | |
let inputObj = JSON.parse(inputText) | |
var tree = parse(inputObj); | |
debugger; | |
/** Calculates each node's positions. */ | |
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.clearRect(0, 0, canvas.width, canvas.height); | |
context.strokeStyle = 'rgb(00, 00, 00)'; | |
context.fillStyle = 'rgb(00, 00, 00)'; | |
tree.eachInPostorder(Algorithm.render, [context]); | |
} |