block by nitaku 8784278

Jigsaw treemap (Gosper)

Full Screen

A jigsaw treemap that uses a Gosper space-filling curve layout to represent the flare software package hierarchy. Use the mouse to zoom and pan.

Only the first level of the tree is displayed, to avoid cluttering the map. Label placement is naively performed by placing text at the region’s centroid, so the results are far from ideal. Labels are scaled according to the region area.

index.js

(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, depth_color, hierarchy, leaves, nodes, scale, 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);
    /* 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
    */
    depth_color = d3.scale.linear().domain([
      1, d3.max(leaves, function(d) {
        return d.depth;
      })
    ]).range(['#FFF7DB', '#F0A848']).interpolate(d3.interpolateHcl);
    /* define a thickness scale for region depth
    */
    /* translate size to cell 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 cells
    */
    /* draw the land border (above cells)
    */
    map.append('use').attr('class', 'land-fill').attr('xlink:href', '#land');
    /* draw the level one region 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 labels
    */
    return 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];
    });
    /* draw the leaf labels
    */
  });

}).call(this);

index.html

<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <title>Jigsaw treemap (Gosper)</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>

flare_reader.coffee

### 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;
  }
};
`

flare_reader.js


/* 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);

index.coffee

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)
    
    
    ### 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 depth ###
    # depth_thickness = d3.scale.sqrt()
        # .domain([0, d3.max(leaves,(d)->d.depth)-1])
        # .range([4, 0.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 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', 'white')
        # .attr('stroke', (d) -> depth_color(d.depth))
        # .attr('stroke', 'white')
        
    ### draw the land border (above cells) ###
    map.append('use')
        .attr('class', 'land-fill')
        .attr('xlink:href', '#land')
        
    ### draw the level one region 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) -> depth_thickness(d.depth))
        .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 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])
        
    ### draw the leaf labels ###
    # map.selectAll('.label')
        # .data(leaves)
      # .enter().append('text')
        # .attr('class', 'label')
        # .attr('font-size', '4px')
        # .attr('dy', '0.35em')
        # .attr('transform', (d) -> "translate(#{d.x},#{d.y})")
        # .text((d) -> d.name.split('.').reverse()[0])

index.css

.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 {
  fill: #333333;
  text-anchor: middle;
  pointer-events: none;
  font-family: "Lacuna";
}

.graph_link {
  stroke: teal;
  stroke-width: 0.05;
  fill: none;
  pointer-events: none;
}

index.sass

.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
    fill: #333
    text-anchor: middle
    pointer-events: none
    font-family: "Lacuna"
    
.graph_link
    stroke: teal
    stroke-width: 0.05
    fill: none
    pointer-events: none

jigsaw.coffee

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
        
}

jigsaw.js

(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);

sfc_layout.coffee

### 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
}

sfc_layout.js


/* 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);

tree_utils.coffee

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
}

tree_utils.js

(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;
    }
  };

}).call(this);

zip.coffee

### 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])
    ))

zip.js


/* 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);