Same as this example, but using a Gosper curve.
(function() {
var height, map, svg, vis, width, zoom;
width = 960;
height = 500;
/* create the SVG
*/
svg = d3.select('body').append('svg').attr('width', width).attr('height', height);
vis = svg.append('g');
map = vis.append('g').attr('transform', "translate(" + (width / 2) + "," + (height / 2) + ")");
/* define a zoom behavior
*/
zoom = d3.behavior.zoom().scaleExtent([1, 10]).on('zoom', function() {
/* whenever the user zooms,
*/
/* modify translation and scale of the zoom group accordingly
*/ return vis.attr('transform', "translate(" + (zoom.translate()) + ")scale(" + (zoom.scale()) + ")");
});
/* bind the zoom behavior to the main SVG
*/
svg.call(zoom);
/* read flare data
*/
d3.json('flare-imports.json', function(data) {
/* package tree
*/
var cells2fontsize, defs, hierarchy, leaves, nodes, scale, size2cellscale, tree;
tree = flare_reader.tree(data);
hierarchy = d3.layout.hierarchy();
nodes = hierarchy(tree);
/* imports links
*/
/* this tree is unordered, we need a canonical ordering for it
*/
tree_utils.canonical_sort(tree);
/* obtain the sequence of leaves
*/
leaves = tree_utils.get_leaves(tree);
/* compute the subtree height for each node
*/
tree_utils.compute_height(tree);
/* VISUALIZATION
*/
/* compute the space-filling curve layout
*/
scale = 26;
sfc_layout.displace(leaves, sfc_layout.GOSPER, scale, -Math.PI / 6);
/* compute also the position of internal nodes
*/
sfc_layout.displace_tree(tree);
/* define a bundle layout
*/
/* define a color scale for leaf depth
*/
/* define a thickness scale for region height
*/
/* translate size to cell scale
*/
size2cellscale = d3.scale.sqrt().domain([
0, d3.max(nodes, function(d) {
return d.size;
})
]).range([0, scale]);
/* translate cells to label font size
*/
cells2fontsize = d3.scale.pow().exponent(0.3).domain([1, leaves.length]).range([4, 80]);
/* compute all the internal nodes regions
*/
jigsaw.treemap(tree, scale, jigsaw.HEX_CELL);
/* define the level zero region (the land)
*/
defs = svg.append('defs');
defs.append('path').attr('id', 'land').attr('d', jigsaw.get_svg_path(tree.region));
/* faux land glow (using filters takes too much resources)
*/
map.append('use').attr('class', 'land-glow-outer').attr('xlink:href', '#land');
map.append('use').attr('class', 'land-glow-inner').attr('xlink:href', '#land');
/* draw the land border (behind cells)
*/
map.append('use').attr('class', 'land-fill').attr('xlink:href', '#land');
/* draw labels
*/
map.selectAll('.label').data(nodes.filter(function(d) {
return d.depth === 1;
})).enter().append('text').attr('class', 'label').attr('font-size', function(d) {
return cells2fontsize(d.leaf_descendants.length);
}).attr('dy', '0.35em').attr('transform', function(d) {
return "translate(" + d.x + "," + d.y + ")";
}).text(function(d) {
return d.name.split('.').reverse()[0];
}).attr('opacity', 0.2);
/* draw the cells
*/
map.selectAll('.cell').data(leaves).enter().append('path').attr('class', 'cell').attr('d', function(d) {
return jigsaw.hex_generate_svg_path(size2cellscale(d.size));
}).attr('transform', function(d) {
return "translate(" + d.x + "," + d.y + ")";
}).attr('fill', 'orange');
/* draw the level one boundaries
*/
map.selectAll('.region').data(nodes.filter(function(d) {
return d.depth === 1;
})).enter().append('path').attr('class', 'region').attr('d', function(d) {
return jigsaw.get_svg_path(d.region);
}).attr('stroke-width', '0.2px');
/* draw the graph links
*/
/* draw the leaf labels
*/
return map.selectAll('.leaf_label').data(leaves).enter().append('text').attr('class', 'leaf_label').attr('font-size', '2.5').attr('dy', '0.35em').attr('transform', function(d) {
return "translate(" + d.x + "," + d.y + ")";
}).text(function(d) {
return d.name.split('.').reverse()[0];
});
});
}).call(this);
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>Gosper treemap (area encoding)</title>
<link type="text/css" href="index.css" rel="stylesheet"/>
<script src="//d3js.org/d3.v3.min.js"></script>
<script src="//jsclipper.sourceforge.net/6.1.3.1/clipper.js"></script>
<script src="zip.js"></script>
<script src="flare_reader.js"></script>
<script src="tree_utils.js"></script>
<script src="sfc_layout.js"></script>
<script src="jigsaw.js"></script>
</head>
<body>
</body>
<script src="index.js"></script>
</html>### read flare-imports data and provide it in form of tree (for the package hierarchy) and links (for the imports) ###
### code adapted from http://bl.ocks.org/mbostock/4341134 ###
`
window.flare_reader = {
// Lazily construct the package hierarchy from class names.
tree: function(classes) {
var map = {};
function find(name, data) {
var node = map[name], i;
if (!node) {
node = map[name] = data || {name: name, children: []};
if (name.length) {
node.parent = find(name.substring(0, i = name.lastIndexOf(".")));
node.parent.children.push(node);
node.key = name.substring(i + 1);
}
}
return node;
}
classes.forEach(function(d) {
find(d.name, d);
});
var flare = map['flare'];
delete flare.parent; // CHANGED root node is not ""
return flare;
},
// Return a list of imports for the given array of nodes.
imports: function(nodes) {
var map = {},
imports = [];
// Compute a map from name to node.
nodes.forEach(function(d) {
map[d.name] = d;
});
// For each import, construct a link from the source to target node.
nodes.forEach(function(d) {
if (d.imports) d.imports.forEach(function(i) {
imports.push({source: map[d.name], target: map[i]});
});
});
return imports;
}
};
`
/* read flare-imports data and provide it in form of tree (for the package hierarchy) and links (for the imports)
*/
/* code adapted from http://bl.ocks.org/mbostock/4341134
*/
(function() {
window.flare_reader = {
// Lazily construct the package hierarchy from class names.
tree: function(classes) {
var map = {};
function find(name, data) {
var node = map[name], i;
if (!node) {
node = map[name] = data || {name: name, children: []};
if (name.length) {
node.parent = find(name.substring(0, i = name.lastIndexOf(".")));
node.parent.children.push(node);
node.key = name.substring(i + 1);
}
}
return node;
}
classes.forEach(function(d) {
find(d.name, d);
});
var flare = map['flare'];
delete flare.parent; // CHANGED root node is not ""
return flare;
},
// Return a list of imports for the given array of nodes.
imports: function(nodes) {
var map = {},
imports = [];
// Compute a map from name to node.
nodes.forEach(function(d) {
map[d.name] = d;
});
// For each import, construct a link from the source to target node.
nodes.forEach(function(d) {
if (d.imports) d.imports.forEach(function(i) {
imports.push({source: map[d.name], target: map[i]});
});
});
return imports;
}
};
;
}).call(this);
width = 960
height = 500
### create the SVG ###
svg = d3.select('body').append('svg')
.attr('width', width)
.attr('height', height)
vis = svg.append('g')
map = vis.append('g')
.attr('transform', "translate(#{width/2},#{height/2})")
### define a zoom behavior ###
zoom = d3.behavior.zoom()
.scaleExtent([1,10]) # min-max zoom
.on 'zoom', () ->
### whenever the user zooms, ###
### modify translation and scale of the zoom group accordingly ###
vis.attr('transform', "translate(#{zoom.translate()})scale(#{zoom.scale()})")
### bind the zoom behavior to the main SVG ###
svg.call(zoom)
### read flare data ###
d3.json 'flare-imports.json', (data) ->
### package tree ###
tree = flare_reader.tree(data)
hierarchy = d3.layout.hierarchy()
nodes = hierarchy(tree)
### imports links ###
# graph_links = flare_reader.imports(nodes)
### this tree is unordered, we need a canonical ordering for it ###
tree_utils.canonical_sort(tree)
### obtain the sequence of leaves ###
leaves = tree_utils.get_leaves(tree)
### compute the subtree height for each node ###
tree_utils.compute_height(tree)
### VISUALIZATION ###
### compute the space-filling curve layout ###
scale = 26
sfc_layout.displace(leaves, sfc_layout.GOSPER, scale, -Math.PI/6)
### compute also the position of internal nodes ###
sfc_layout.displace_tree(tree)
### define a bundle layout ###
# bundle = d3.layout.bundle()
# bundles = bundle(graph_links)
# link_generator = d3.svg.line()
# .interpolate('bundle')
# .tension(0.99)
# .x((d) -> d.x)
# .y((d) -> d.y)
### define a color scale for leaf depth ###
# depth_color = d3.scale.linear()
# .domain([1, d3.max(leaves,(d)->d.depth)])
# .range(['#FFF7DB', '#F0A848'])
# .interpolate(d3.interpolateHcl)
### define a thickness scale for region height ###
# height2thickness = d3.scale.linear()
# .domain([1, tree.height])
# .range([0.001, 1])
### translate size to cell scale ###
size2cellscale = d3.scale.sqrt()
.domain([0, d3.max(nodes,(d)->d.size)])
.range([0,scale])
### translate cells to label font size ###
cells2fontsize = d3.scale.pow()
.exponent(0.3)
.domain([1, leaves.length])
.range([4,80])
### compute all the internal nodes regions ###
jigsaw.treemap(tree, scale, jigsaw.HEX_CELL)
### define the level zero region (the land) ###
defs = svg.append('defs')
defs.append('path')
.attr('id', 'land')
.attr('d', jigsaw.get_svg_path tree.region)
### faux land glow (using filters takes too much resources) ###
map.append('use')
.attr('class', 'land-glow-outer')
.attr('xlink:href', '#land')
map.append('use')
.attr('class', 'land-glow-inner')
.attr('xlink:href', '#land')
### draw the land border (behind cells) ###
map.append('use')
.attr('class', 'land-fill')
.attr('xlink:href', '#land')
### draw labels ###
map.selectAll('.label')
.data(nodes.filter((d)->d.depth is 1))
.enter().append('text')
.attr('class', 'label')
.attr('font-size', (d) -> cells2fontsize(d.leaf_descendants.length))
.attr('dy', '0.35em')
.attr('transform', (d) -> "translate(#{d.x},#{d.y})")
.text((d) -> d.name.split('.').reverse()[0])
.attr('opacity', 0.2)
### draw the cells ###
map.selectAll('.cell')
.data(leaves)
.enter().append('path')
.attr('class', 'cell')
.attr('d', (d) -> jigsaw.hex_generate_svg_path size2cellscale(d.size) )
# .attr('d', jigsaw.hex_generate_svg_path scale )
.attr('transform', (d) -> "translate(#{d.x},#{d.y})")
# .attr('fill', (d) -> depth_color(d.depth))
.attr('fill', 'orange')
# .attr('stroke', (d) -> depth_color(d.depth))
# .attr('stroke', 'white')
### draw the level one boundaries ###
map.selectAll('.region')
.data(nodes.filter((d)->d.depth is 1))
.enter().append('path')
.attr('class', 'region')
.attr('d', (d) -> jigsaw.get_svg_path d.region)
# .attr('stroke-width', (d) -> height2thickness(d.height))
.attr('stroke-width', '0.2px')
### draw the graph links ###
# map.selectAll('.graph_link')
# .data(bundles)
# .enter().append('path')
# .attr('class', 'graph_link')
# .attr('d', link_generator)
### draw the leaf labels ###
map.selectAll('.leaf_label')
.data(leaves)
.enter().append('text')
.attr('class', 'leaf_label')
.attr('font-size', '2.5')
.attr('dy', '0.35em')
.attr('transform', (d) -> "translate(#{d.x},#{d.y})")
.text((d) -> d.name.split('.').reverse()[0])
.land-glow-outer {
fill: none;
stroke: #eeeeee;
stroke-width: 16px;
}
.land-glow-inner {
fill: none;
stroke: #dddddd;
stroke-width: 8px;
}
.land-fill {
fill: white;
stroke: #444444;
stroke-width: 0.5px;
}
.cell {
stroke-width: 1px;
}
.region {
fill: none;
stroke: #444444;
}
@font-face {
font-family: "Lacuna";
src: url("lacuna.ttf");
}
.label, .leaf_label {
fill: #333333;
text-anchor: middle;
pointer-events: none;
font-family: "Lacuna";
-webkit-touch-callout: none;
-webkit-user-select: none;
-khtml-user-select: none;
-moz-user-select: none;
-ms-user-select: none;
user-select: none;
}
.graph_link {
stroke: teal;
stroke-width: 0.05;
fill: none;
pointer-events: none;
}
.land-glow-outer
fill: none
stroke: #EEE
stroke-width: 16px
.land-glow-inner
fill: none
stroke: #DDD
stroke-width: 8px
.land-fill
fill: white
stroke: #444
stroke-width: 0.5px
.cell
stroke-width: 1px
.region
fill: none
stroke: #444
@font-face
font-family: "Lacuna"
src: url("lacuna.ttf")
.label, .leaf_label
fill: #333
text-anchor: middle
pointer-events: none
font-family: "Lacuna"
-webkit-touch-callout: none
-webkit-user-select: none
-khtml-user-select: none
-moz-user-select: none
-ms-user-select: none
user-select: none
.graph_link
stroke: teal
stroke-width: 0.05
fill: none
pointer-events: none
window.jigsaw = {
hex_generate_svg_path: (scale) ->
a = scale/2
r = a / Math.sin(Math.PI/3)
return "M#{r} 0 L#{r/2} #{a} L#{-r/2} #{a} L#{-r} 0 L#{-r/2} #{-a} L#{r/2} #{-a} Z"
square_generate_svg_path: (scale) ->
a = scale/2
return "M#{-a} #{-a} L#{-a} #{a} L#{a} #{a} L#{a} #{-a} Z"
HEX_CELL: (node, scale) ->
a = scale/2
r = a / Math.sin(Math.PI/3)
region = [[{X:node.x+r, Y:node.y}, {X:node.x+r/2, Y:node.y+a}, {X:node.x-r/2, Y:node.y+a}, {X:node.x-r, Y:node.y}, {X:node.x-r/2, Y:node.y-a}, {X:node.x+r/2, Y:node.y-a}]]
return region
SQUARE_CELL: (node, scale) ->
a = scale/2
region = [[{X:node.x-a, Y:node.y-a}, {X:node.x-a, Y:node.y+a}, {X:node.x+a, Y:node.y+a}, {X:node.x+a, Y:node.y-a}]]
return region
treemap: (node, scale, base) ->
if not node.children?
node.region = base(node, scale)
return node.region
children_paths = (jigsaw.treemap(child, scale, base) for child in node.children).reduce((a, d) -> a.concat(d))
upscale = 100
ClipperLib.JS.ScaleUpPaths(children_paths, upscale)
cpr = new ClipperLib.Clipper()
cpr.AddPaths(children_paths, ClipperLib.PolyType.ptSubject, true)
node.region = new ClipperLib.Paths()
cpr.Execute(ClipperLib.ClipType.ctUnion, node.region, ClipperLib.PolyFillType.pftNonZero, ClipperLib.PolyFillType.pftNonZero)
ClipperLib.JS.ScaleDownPaths(children_paths, upscale)
ClipperLib.JS.ScaleDownPaths(node.region, upscale)
return node.region
### Converts Paths to SVG path string ###
### and scales down the coordinates ###
### from http://jsclipper.sourceforge.net/6.1.3.1/index.html?p=starter_boolean.html ###
get_svg_path: (paths, scale) ->
svgpath = ''
if not scale?
scale = 1
for path in paths
for p, i in path
if i is 0
svgpath += 'M'
else
svgpath += 'L'
svgpath += p.X/scale + ", " + p.Y/scale
svgpath += 'Z'
if svgpath is ''
svgpath = 'M0,0'
return svgpath
}(function() {
window.jigsaw = {
hex_generate_svg_path: function(scale) {
var a, r;
a = scale / 2;
r = a / Math.sin(Math.PI / 3);
return "M" + r + " 0 L" + (r / 2) + " " + a + " L" + (-r / 2) + " " + a + " L" + (-r) + " 0 L" + (-r / 2) + " " + (-a) + " L" + (r / 2) + " " + (-a) + " Z";
},
square_generate_svg_path: function(scale) {
var a;
a = scale / 2;
return "M" + (-a) + " " + (-a) + " L" + (-a) + " " + a + " L" + a + " " + a + " L" + a + " " + (-a) + " Z";
},
HEX_CELL: function(node, scale) {
var a, r, region;
a = scale / 2;
r = a / Math.sin(Math.PI / 3);
region = [
[
{
X: node.x + r,
Y: node.y
}, {
X: node.x + r / 2,
Y: node.y + a
}, {
X: node.x - r / 2,
Y: node.y + a
}, {
X: node.x - r,
Y: node.y
}, {
X: node.x - r / 2,
Y: node.y - a
}, {
X: node.x + r / 2,
Y: node.y - a
}
]
];
return region;
},
SQUARE_CELL: function(node, scale) {
var a, region;
a = scale / 2;
region = [
[
{
X: node.x - a,
Y: node.y - a
}, {
X: node.x - a,
Y: node.y + a
}, {
X: node.x + a,
Y: node.y + a
}, {
X: node.x + a,
Y: node.y - a
}
]
];
return region;
},
treemap: function(node, scale, base) {
var child, children_paths, cpr, upscale;
if (!(node.children != null)) {
node.region = base(node, scale);
return node.region;
}
children_paths = ((function() {
var _i, _len, _ref, _results;
_ref = node.children;
_results = [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
child = _ref[_i];
_results.push(jigsaw.treemap(child, scale, base));
}
return _results;
})()).reduce(function(a, d) {
return a.concat(d);
});
upscale = 100;
ClipperLib.JS.ScaleUpPaths(children_paths, upscale);
cpr = new ClipperLib.Clipper();
cpr.AddPaths(children_paths, ClipperLib.PolyType.ptSubject, true);
node.region = new ClipperLib.Paths();
cpr.Execute(ClipperLib.ClipType.ctUnion, node.region, ClipperLib.PolyFillType.pftNonZero, ClipperLib.PolyFillType.pftNonZero);
ClipperLib.JS.ScaleDownPaths(children_paths, upscale);
ClipperLib.JS.ScaleDownPaths(node.region, upscale);
return node.region;
},
/* Converts Paths to SVG path string
*/
/* and scales down the coordinates
*/
/* from http://jsclipper.sourceforge.net/6.1.3.1/index.html?p=starter_boolean.html
*/
get_svg_path: function(paths, scale) {
var i, p, path, svgpath, _i, _len, _len2;
svgpath = '';
if (!(scale != null)) scale = 1;
for (_i = 0, _len = paths.length; _i < _len; _i++) {
path = paths[_i];
for (i = 0, _len2 = path.length; i < _len2; i++) {
p = path[i];
if (i === 0) {
svgpath += 'M';
} else {
svgpath += 'L';
}
svgpath += p.X / scale + ", " + p.Y / scale;
}
svgpath += 'Z';
}
if (svgpath === '') svgpath = 'M0,0';
return svgpath;
}
};
}).call(this);
### FIXME update this code to the optimized version ###
### compute a Lindenmayer system given an axiom, a number of steps and rules ###
fractalize = (config) ->
input = config.axiom
for i in [0...config.steps]
output = ''
for char in input
if char of config.rules
output += config.rules[char]
else
output += char
input = output
return output
### execute a curve string and return all the generated points ###
execute = (curve_string, angle, scale, orientation) ->
points = [{x: 0, y: 0}]
for char in curve_string
if char == '+'
orientation += angle
else if char == '-'
orientation -= angle
else if char == 'F'
last_point = points[points.length-1]
points.push {
x: last_point.x + scale * Math.cos(orientation),
y: last_point.y + scale * Math.sin(orientation)
}
return points
### custom base for logarithm (see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log) ###
base_log = (x, base) -> Math.log(x) / Math.log(base)
window.sfc_layout = {
GOSPER: {
base: 7
angle: Math.PI/3
axiom: 'A'
rules:
A: 'A+BF++BF-FA--FAFA-BF+'
B: '-FA+BFBF++BF+FA--FA-B'
}
HILBERT: {
base: 4
angle: Math.PI/2
axiom: 'A'
rules:
A: '-BF+AFA+FB-'
B: '+AF-BFB-FA+'
}
displace: (seq, curve_cfg, scale, orientation) ->
scale = if scale? then scale else 10
orientation = if orientation? then orientation else 0
### create the minimal curve that can accommodate the whole sequence ###
steps = Math.ceil(base_log(seq.length, curve_cfg.base))
### generate the Lindenmayer system string for the requested curve ###
curve_string = fractalize
steps: steps
axiom: curve_cfg.axiom
rules: curve_cfg.rules
### execute the string, producing the actual points of the curve ###
curve = execute(curve_string, curve_cfg.angle, scale, orientation)
### stores the coordinates in the given sequence ###
for [d,point] in zip(seq, curve)
d.x = point.x
d.y = point.y
### center the layout coordinates in the center of its bounding box ###
max_x = d3.max(seq, (d)->d.x)
max_y = d3.max(seq, (d)->d.y)
min_x = d3.min(seq, (d)->d.x)
min_y = d3.min(seq, (d)->d.y)
for d in seq
d.x -= (max_x+min_x)/2
d.y -= (max_y+min_y)/2
### recursively assign positions to internal nodes too. also compute leaf descendants ###
displace_tree: (node) ->
if not node.children?
### this is a leaf ###
node.leaf_descendants = [node]
return node.leaf_descendants
### an internal node's position is the centroid of its leaf descendants ###
node.leaf_descendants = (sfc_layout.displace_tree(c) for c in node.children).reduce((a, d) -> a.concat(d))
node.x = d3.mean(node.leaf_descendants, (d)->d.x)
node.y = d3.mean(node.leaf_descendants, (d)->d.y)
### pass descendants up to the hierarchy ###
return node.leaf_descendants
}
/* FIXME update this code to the optimized version
*/
/* compute a Lindenmayer system given an axiom, a number of steps and rules
*/
(function() {
var base_log, execute, fractalize;
fractalize = function(config) {
var char, i, input, output, _i, _len, _ref;
input = config.axiom;
for (i = 0, _ref = config.steps; 0 <= _ref ? i < _ref : i > _ref; 0 <= _ref ? i++ : i--) {
output = '';
for (_i = 0, _len = input.length; _i < _len; _i++) {
char = input[_i];
if (char in config.rules) {
output += config.rules[char];
} else {
output += char;
}
}
input = output;
}
return output;
};
/* execute a curve string and return all the generated points
*/
execute = function(curve_string, angle, scale, orientation) {
var char, last_point, points, _i, _len;
points = [
{
x: 0,
y: 0
}
];
for (_i = 0, _len = curve_string.length; _i < _len; _i++) {
char = curve_string[_i];
if (char === '+') {
orientation += angle;
} else if (char === '-') {
orientation -= angle;
} else if (char === 'F') {
last_point = points[points.length - 1];
points.push({
x: last_point.x + scale * Math.cos(orientation),
y: last_point.y + scale * Math.sin(orientation)
});
}
}
return points;
};
/* custom base for logarithm (see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/log)
*/
base_log = function(x, base) {
return Math.log(x) / Math.log(base);
};
window.sfc_layout = {
GOSPER: {
base: 7,
angle: Math.PI / 3,
axiom: 'A',
rules: {
A: 'A+BF++BF-FA--FAFA-BF+',
B: '-FA+BFBF++BF+FA--FA-B'
}
},
HILBERT: {
base: 4,
angle: Math.PI / 2,
axiom: 'A',
rules: {
A: '-BF+AFA+FB-',
B: '+AF-BFB-FA+'
}
},
displace: function(seq, curve_cfg, scale, orientation) {
var curve, curve_string, d, max_x, max_y, min_x, min_y, point, steps, _i, _j, _len, _len2, _ref, _ref2, _results;
scale = scale != null ? scale : 10;
orientation = orientation != null ? orientation : 0;
/* create the minimal curve that can accommodate the whole sequence
*/
steps = Math.ceil(base_log(seq.length, curve_cfg.base));
/* generate the Lindenmayer system string for the requested curve
*/
curve_string = fractalize({
steps: steps,
axiom: curve_cfg.axiom,
rules: curve_cfg.rules
});
/* execute the string, producing the actual points of the curve
*/
curve = execute(curve_string, curve_cfg.angle, scale, orientation);
/* stores the coordinates in the given sequence
*/
_ref = zip(seq, curve);
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
_ref2 = _ref[_i], d = _ref2[0], point = _ref2[1];
d.x = point.x;
d.y = point.y;
}
/* center the layout coordinates in the center of its bounding box
*/
max_x = d3.max(seq, function(d) {
return d.x;
});
max_y = d3.max(seq, function(d) {
return d.y;
});
min_x = d3.min(seq, function(d) {
return d.x;
});
min_y = d3.min(seq, function(d) {
return d.y;
});
_results = [];
for (_j = 0, _len2 = seq.length; _j < _len2; _j++) {
d = seq[_j];
d.x -= (max_x + min_x) / 2;
_results.push(d.y -= (max_y + min_y) / 2);
}
return _results;
},
/* recursively assign positions to internal nodes too. also compute leaf descendants
*/
displace_tree: function(node) {
var c;
if (!(node.children != null)) {
/* this is a leaf
*/
node.leaf_descendants = [node];
return node.leaf_descendants;
}
/* an internal node's position is the centroid of its leaf descendants
*/
node.leaf_descendants = ((function() {
var _i, _len, _ref, _results;
_ref = node.children;
_results = [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
c = _ref[_i];
_results.push(sfc_layout.displace_tree(c));
}
return _results;
})()).reduce(function(a, d) {
return a.concat(d);
});
node.x = d3.mean(node.leaf_descendants, function(d) {
return d.x;
});
node.y = d3.mean(node.leaf_descendants, function(d) {
return d.y;
});
/* pass descendants up to the hierarchy
*/
return node.leaf_descendants;
}
};
}).call(this);
tcmp = (a,b) ->
children_a = (if a.children? then a.children else [])
children_b = (if b.children? then b.children else [])
for [ai, bi] in zip(children_a,children_b)
ci = tcmp(ai,bi)
if ci isnt 0
return ci
return children_b.length-children_a.length
rsort = (t) ->
children = (if t.children? then t.children else [])
for c in children
rsort(c)
children.sort(tcmp)
window.tree_utils = {
### sort the given unordered tree using a canonical ordering ###
### see Constant time generation of free trees - Wright et al. 1986 ###
canonical_sort: (tree) ->
rsort(tree)
### return the ordered sequence of leaves of a given tree ###
get_leaves: (tree) ->
seq = []
parse_leaves = (node) ->
if not node.children?
seq.push node
else
for c in node.children
parse_leaves(c)
parse_leaves(tree)
return seq
### compute the height of each node ###
compute_height: (node) ->
if not node.children?
node.height = 1
else
node.height = d3.max((tree_utils.compute_height(c) for c in node.children)) + 1
return node.height
}(function() {
var rsort, tcmp;
tcmp = function(a, b) {
var ai, bi, children_a, children_b, ci, _i, _len, _ref, _ref2;
children_a = (a.children != null ? a.children : []);
children_b = (b.children != null ? b.children : []);
_ref = zip(children_a, children_b);
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
_ref2 = _ref[_i], ai = _ref2[0], bi = _ref2[1];
ci = tcmp(ai, bi);
if (ci !== 0) return ci;
}
return children_b.length - children_a.length;
};
rsort = function(t) {
var c, children, _i, _len;
children = (t.children != null ? t.children : []);
for (_i = 0, _len = children.length; _i < _len; _i++) {
c = children[_i];
rsort(c);
}
return children.sort(tcmp);
};
window.tree_utils = {
/* sort the given unordered tree using a canonical ordering
*/
/* see Constant time generation of free trees - Wright et al. 1986
*/
canonical_sort: function(tree) {
return rsort(tree);
},
/* return the ordered sequence of leaves of a given tree
*/
get_leaves: function(tree) {
var parse_leaves, seq;
seq = [];
parse_leaves = function(node) {
var c, _i, _len, _ref, _results;
if (!(node.children != null)) {
return seq.push(node);
} else {
_ref = node.children;
_results = [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
c = _ref[_i];
_results.push(parse_leaves(c));
}
return _results;
}
};
parse_leaves(tree);
return seq;
},
/* compute the height of each node
*/
compute_height: function(node) {
var c;
if (!(node.children != null)) {
node.height = 1;
} else {
node.height = d3.max((function() {
var _i, _len, _ref, _results;
_ref = node.children;
_results = [];
for (_i = 0, _len = _ref.length; _i < _len; _i++) {
c = _ref[_i];
_results.push(tree_utils.compute_height(c));
}
return _results;
})()) + 1;
}
return node.height;
}
};
}).call(this);
### python-like zip ###
window.zip = () ->
args = [].slice.call(arguments)
shortest = if args.length == 0 then [] else args.reduce(((a,b) ->
if a.length < b.length then a else b
))
return shortest.map(((_,i) ->
args.map((array) -> array[i])
))
/* python-like zip
*/
(function() {
window.zip = function() {
var args, shortest;
args = [].slice.call(arguments);
shortest = args.length === 0 ? [] : args.reduce((function(a, b) {
if (a.length < b.length) {
return a;
} else {
return b;
}
}));
return shortest.map((function(_, i) {
return args.map(function(array) {
return array[i];
});
}));
};
}).call(this);