Skip to content

Instantly share code, notes, and snippets.

@KyleMit

KyleMit/index.html

Last active July 26, 2022 08:23
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save KyleMit/dfbf4a376f80f587d476bb484cceac02 to your computer and use it in GitHub Desktop.
Save KyleMit/dfbf4a376f80f587d476bb484cceac02 to your computer and use it in GitHub Desktop.
Download ZIP
Walker's Algorithm
Raw
readme.md
Raw
index.html
<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>
Raw
walker.js
/* 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]);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment