xantus/mojo-tree.pl

## mojo-tree.pl
#!/usr/bin/perl
# Copyright 2010 (c) David Davis - http://xant.us/
# BSD License

# built using webtreemap
# http://github.com/martine/webtreemap

# *DOWNLOAD MOJO FIRST*
# git clone http://github.com/kraih/mojo.git

use lib 'mojo/lib';

use strict;
use warnings;

use Mojolicious::Lite;
use JSON ();

# set your tree root here
my $root = app->home->rel_dir( 'mojo' );

# default to daemon mode
@ARGV = qw( daemon ) unless @ARGV;

# routes
get '/' => 'index';

# convert the tree to json once for speed
crawl( $root, '/', my $tree = {} );
$tree = 'var kTree = '.JSON::encode_json( $tree ).';';

get '/data/tree.js' => sub { shift->render_text( $tree, type => 'text/javascript' ) };

app->start;


sub crawl {
    my $dir = shift;
    my $name = shift;
    my $data = shift;

    $dir .= '/' unless $dir =~ m/\/$/;

    opendir( my $d, $dir ) or warn $! && return [];
    my @files = grep { !/^\./ } readdir( $d );
    close( $d );

    my $total = 0;
    foreach my $file ( @files ) {
        stat( $dir.$file );
        if ( -d _ ) {
            $total += crawl( $dir.$file, $file, my $subtree = {} );
            push( @{ $data->{children} ||= [] }, $subtree );
            next;
        }
        my $size = -s _;
        push( @{ $data->{children} ||= [] }, { name => $file.' '.pretty( $size ), data => { '$area' => int $size } } );
        $total += $size;
    }

    $data->{name} = $name.' '.pretty( $total );
    $data->{data} = { '$area' => int $total };

    return $total;
}

sub pretty {
    my $b = shift;
    return sprintf( '%.1fm', $b = $b / 1.0e6 ) if $b > 1e6;
    return sprintf( '%.1fk', $b = $b / 1.0e3 ) if $b > 1e3;
    return $b;
}

__DATA__

@@ index.html.ep
<!DOCTYPE html>
<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<title>Directory tree size browser</title>
<script src="data/tree.js"></script>
<link rel="stylesheet" href="css/webtreemap.css"/>
<style>
body {
  font-family: sans-serif;
  font-size: 0.8em;
  margin: 2ex 4ex;
}

tt, pre {
  font-family: WebKitWorkaround, monospace;
}

h1, h2 {
  font-weight: normal;
}
h2 {
  margin-top: 4ex;
}

#map {
  width: 100%;
  height: 550px;

  position: relative;
  cursor: pointer;
  -webkit-user-select: none;
}
</style>
</head>
<body><h1>Directory tree size browser</h1>

<p>Click on a box to zoom in.  Click on the outermost box to zoom out.</p>

<div id="map"></div>

<script src="js/webtreemap.js"></script>

<script>
appendTreemap(document.getElementById('map'), kTree);
</script>
</body>
</html>

@@ css/webtreemap.css
.webtreemap-node {
  /* Required attributes. */
  position: absolute;
  overflow: hidden;   /* To hide overlong captions. */
  background: white;  /* Nodes must be opaque for zIndex layering. */
  border: solid 1px black;  /* Calculations assume 1px border. */

  /* Optional: CSS animation. */
  -webkit-transition: top    0.3s,
                      left   0.3s,
                      width  0.3s,
                      height 0.3s;
}

/* Optional: highlight nodes on mouseover. */
.webtreemap-node:hover {
  background: #eee;
}

/* Optional: Different borders depending on level. */
.webtreemap-level0 {
  border: solid 1px #444;
}
.webtreemap-level1 {
  border: solid 1px #666;
}
.webtreemap-level2 {
  border: solid 1px #888;
}
.webtreemap-level3 {
  border: solid 1px #aaa;
}
.webtreemap-level4 {
  border: solid 1px #ccc;
}

/* Optional: styling on node captions. */
.webtreemap-caption {
  font-family: sans-serif;
  font-size: 11px;
  padding: 2px;
  text-align: center;
}

/* Optional: styling on captions on mouse hover. */
/*.webtreemap-node:hover > .webtreemap-caption {
  text-decoration: underline;
}*/
@@ js/webtreemap.js
// Size of border around nodes.
// We could support arbitrary borders using getComputedStyle(), but I am
// skeptical the extra complexity (and performance hit) is worth it.
var kBorderWidth = 1;

// Padding around contents.
// TODO: do this with a nested div to allow it to be CSS-styleable.
var kPadding = 4;

var focused = null;

function focus(tree) {
  focused = tree;

  // Hide all visible siblings of all our ancestors by lowering them.
  var level = 0;
  var root = tree;
  while (root.parent) {
    root = root.parent;
    level += 1;
    for (var i = 0, sibling; sibling = root.children[i]; ++i) {
      if (sibling.dom)
        sibling.dom.style.zIndex = 0;
    }
  }
  var width = root.dom.offsetWidth;
  var height = root.dom.offsetHeight;
  // Unhide (raise) and maximize us and our ancestors.
  for (var t = tree; t.parent; t = t.parent) {
    // Shift off by border so we don't get nested borders.
    // TODO: actually make nested borders work (need to adjust width/height).
    position(t.dom, -kBorderWidth, -kBorderWidth, width, height);
    t.dom.style.zIndex = 1;
  }
  // And layout into the topmost box.
  layout(tree, level, width, height);
}

function makeDom(tree, level) {
  var dom = document.createElement('div');
  dom.style.zIndex = 1;
  dom.className = 'webtreemap-node webtreemap-level' + Math.min(level, 4);

  dom.onmousedown = function(e) {
    if (e.button == 0) {
      if (focused && tree == focused && focused.parent) {
        focus(focused.parent);
      } else {
        focus(tree);
      }
    }
    e.stopPropagation();
    return true;
  };

  var caption = document.createElement('div');
  caption.className = 'webtreemap-caption';
  caption.innerHTML = tree.name;
  dom.appendChild(caption);

  tree.dom = dom;
  return dom;
}

function position(dom, x, y, width, height) {
  // CSS width/height does not include border.
  width -= kBorderWidth*2;
  height -= kBorderWidth*2;

  dom.style.left   = x + 'px';
  dom.style.top    = y + 'px';
  dom.style.width  = Math.max(width, 0) + 'px';
  dom.style.height = Math.max(height, 0) + 'px';
}

// Given a list of rectangles |nodes|, the 1-d space available
// |space|, and a starting rectangle index |start|, compute an span of
// rectangles that optimizes a pleasant aspect ratio.
//
// Returns [end, sum], where end is one past the last rectangle and sum is the
// 2-d sum of the rectangles' areas.
function selectSpan(nodes, space, start) {
  // Add rectangle one by one, stopping when aspect ratios begin to go
  // bad.  Result is [start,end) covering the best run for this span.
  // http://scholar.google.com/scholar?cluster=5972512107845615474
  var node = nodes[start];
  var rmin = node.data['$area'];  // Smallest seen child so far.
  var rmax = rmin;                // Largest child.
  var rsum = 0;                   // Sum of children in this span.
  var last_score = 0;             // Best score yet found.
  for (var end = start; node = nodes[end]; ++end) {
    var size = node.data['$area'];
    if (size < rmin)
      rmin = size;
    if (size > rmax)
      rmax = size;
    rsum += size;

    // This formula is from the paper, but you can easily prove to
    // yourself it's taking the larger of the x/y aspect ratio or the
    // y/x aspect ratio.  The additional magic fudge constant of 5
    // makes us prefer wider rectangles to taller ones.
    var score = Math.max(5*space*space*rmax / (rsum*rsum),
                         1*rsum*rsum / (space*space*rmin));
    if (last_score && score > last_score) {
      rsum -= size;  // Undo size addition from just above.
      break;
    }
    last_score = score;
  }
  return [end, rsum];
}

function layout(tree, level, width, height) {
  if (!('children' in tree))
    return;

  var total = tree.data['$area'];

  // XXX why do I need an extra -1/-2 here for width/height to look right?
  var x1 = 0, y1 = 0, x2 = width - 1, y2 = height - 2;
  x1 += kPadding; y1 += kPadding;
  x2 -= kPadding; y2 -= kPadding;
  y1 += 14;  // XXX get first child height for caption spacing

  var pixels_to_units = Math.sqrt(total / ((x2 - x1) * (y2 - y1)));

  for (var start = 0, child; child = tree.children[start]; ++start) {
    if (x2 - x1 < 60 || y2 - y1 < 40) {
      if (child.dom) {
        child.dom.style.zIndex = 0;
        position(child.dom, -2, -2, 0, 0);
      }
      continue;
    }

    // In theory we can dynamically decide whether to split in x or y based
    // on aspect ratio.  In practice, changing split direction with this
    // layout doesn't look very good.
    //   var ysplit = (y2 - y1) > (x2 - x1);
    var ysplit = true;

    var space;  // Space available along layout axis.
    if (ysplit)
      space = (y2 - y1) * pixels_to_units;
    else
      space = (x2 - x1) * pixels_to_units;

    var span = selectSpan(tree.children, space, start);
    var end = span[0], rsum = span[1];

    // Now that we've selected a span, lay out rectangles [start,end) in our
    // available space.
    var x = x1, y = y1;
    for (var i = start; i < end; ++i) {
      child = tree.children[i];
      if (!child.dom) {
        child.parent = tree;
        child.dom = makeDom(child, level + 1);
        tree.dom.appendChild(child.dom);
      } else {
        child.dom.style.zIndex = 1;
      }
      var size = child.data['$area'];
      var frac = size / rsum;
      if (ysplit) {
        width = rsum / space;
        height = size / width;
      } else {
        height = rsum / space;
        width = size / height;
      }
      width /= pixels_to_units;
      height /= pixels_to_units;
      width = Math.round(width);
      height = Math.round(height);
      position(child.dom, x, y, width, height);
      if ('children' in child) {
        layout(child, level + 1, width, height);
      }
      if (ysplit)
        y += height;
      else
        x += width;
    }

    // Shrink our available space based on the amount we used.
    if (ysplit)
      x1 += Math.round((rsum / space) / pixels_to_units);
    else
      y1 += Math.round((rsum / space) / pixels_to_units);

    // end points one past where we ended, which is where we want to
    // begin the next iteration, but subtract one to balance the ++ in
    // the loop.
    start = end - 1;
  }
}

function appendTreemap(dom, data) {
  var style = getComputedStyle(dom, null);
  var width = parseInt(style.width);
  var height = parseInt(style.height);
  makeDom(data, 0);
  dom.appendChild(data.dom);
  position(data.dom, 0, 0, width, height);
  layout(data, 0, width, height);
}
	#!/usr/bin/perl
	# Copyright 2010 (c) David Davis - http://xant.us/
	# BSD License

	# built using webtreemap
	# http://github.com/martine/webtreemap

	# DOWNLOAD MOJO FIRST
	# git clone http://github.com/kraih/mojo.git

	use lib 'mojo/lib';

	use strict;
	use warnings;

	use Mojolicious::Lite;
	use JSON ();

	# set your tree root here
	my $root = app->home->rel_dir( 'mojo' );

	# default to daemon mode
	@ARGV = qw( daemon ) unless @ARGV;

	# routes
	get '/' => 'index';

	# convert the tree to json once for speed
	crawl( $root, '/', my $tree = {} );
	$tree = 'var kTree = '.JSON::encode_json( $tree ).';';

	get '/data/tree.js' => sub { shift->render_text( $tree, type => 'text/javascript' ) };

	app->start;


	sub crawl {
	my $dir = shift;
	my $name = shift;
	my $data = shift;

	$dir .= '/' unless $dir =~ m/\/$/;

	opendir( my $d, $dir ) or warn $! && return [];
	my @files = grep { !/^\./ } readdir( $d );
	close( $d );

	my $total = 0;
	foreach my $file ( @files ) {
	stat( $dir.$file );
	if ( -d _ ) {
	$total += crawl( $dir.$file, $file, my $subtree = {} );
	push( @{ $data->{children} \|\|= [] }, $subtree );
	next;
	}
	my $size = -s _;
	push( @{ $data->{children} \|\|= [] }, { name => $file.' '.pretty( $size ), data => { '$area' => int $size } } );
	$total += $size;
	}

	$data->{name} = $name.' '.pretty( $total );
	$data->{data} = { '$area' => int $total };

	return $total;
	}

	sub pretty {
	my $b = shift;
	return sprintf( '%.1fm', $b = $b / 1.0e6 ) if $b > 1e6;
	return sprintf( '%.1fk', $b = $b / 1.0e3 ) if $b > 1e3;
	return $b;
	}

	__DATA__

	@@ index.html.ep
	<!DOCTYPE html>
	<html><head>
	<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
	<title>Directory tree size browser</title>
	<script src="data/tree.js"></script>
	<link rel="stylesheet" href="css/webtreemap.css"/>
	<style>
	body {
	font-family: sans-serif;
	font-size: 0.8em;
	margin: 2ex 4ex;
	}

	tt, pre {
	font-family: WebKitWorkaround, monospace;
	}

	h1, h2 {
	font-weight: normal;
	}
	h2 {
	margin-top: 4ex;
	}

	#map {
	width: 100%;
	height: 550px;

	position: relative;
	cursor: pointer;
	-webkit-user-select: none;
	}
	</style>
	</head>
	<body><h1>Directory tree size browser</h1>

	<p>Click on a box to zoom in. Click on the outermost box to zoom out.</p>

	<div id="map"></div>

	<script src="js/webtreemap.js"></script>

	<script>
	appendTreemap(document.getElementById('map'), kTree);
	</script>
	</body>
	</html>

	@@ css/webtreemap.css
	.webtreemap-node {
	/* Required attributes. */
	position: absolute;
	overflow: hidden; /* To hide overlong captions. */
	background: white; /* Nodes must be opaque for zIndex layering. */
	border: solid 1px black; /* Calculations assume 1px border. */

	/* Optional: CSS animation. */
	-webkit-transition: top 0.3s,
	left 0.3s,
	width 0.3s,
	height 0.3s;
	}

	/* Optional: highlight nodes on mouseover. */
	.webtreemap-node:hover {
	background: #eee;
	}

	/* Optional: Different borders depending on level. */
	.webtreemap-level0 {
	border: solid 1px #444;
	}
	.webtreemap-level1 {
	border: solid 1px #666;
	}
	.webtreemap-level2 {
	border: solid 1px #888;
	}
	.webtreemap-level3 {
	border: solid 1px #aaa;
	}
	.webtreemap-level4 {
	border: solid 1px #ccc;
	}

	/* Optional: styling on node captions. */
	.webtreemap-caption {
	font-family: sans-serif;
	font-size: 11px;
	padding: 2px;
	text-align: center;
	}

	/* Optional: styling on captions on mouse hover. */
	/*.webtreemap-node:hover > .webtreemap-caption {
	text-decoration: underline;
	}*/
	@@ js/webtreemap.js
	// Size of border around nodes.
	// We could support arbitrary borders using getComputedStyle(), but I am
	// skeptical the extra complexity (and performance hit) is worth it.
	var kBorderWidth = 1;

	// Padding around contents.
	// TODO: do this with a nested div to allow it to be CSS-styleable.
	var kPadding = 4;

	var focused = null;

	function focus(tree) {
	focused = tree;

	// Hide all visible siblings of all our ancestors by lowering them.
	var level = 0;
	var root = tree;
	while (root.parent) {
	root = root.parent;
	level += 1;
	for (var i = 0, sibling; sibling = root.children[i]; ++i) {
	if (sibling.dom)
	sibling.dom.style.zIndex = 0;
	}
	}
	var width = root.dom.offsetWidth;
	var height = root.dom.offsetHeight;
	// Unhide (raise) and maximize us and our ancestors.
	for (var t = tree; t.parent; t = t.parent) {
	// Shift off by border so we don't get nested borders.
	// TODO: actually make nested borders work (need to adjust width/height).
	position(t.dom, -kBorderWidth, -kBorderWidth, width, height);
	t.dom.style.zIndex = 1;
	}
	// And layout into the topmost box.
	layout(tree, level, width, height);
	}

	function makeDom(tree, level) {
	var dom = document.createElement('div');
	dom.style.zIndex = 1;
	dom.className = 'webtreemap-node webtreemap-level' + Math.min(level, 4);

	dom.onmousedown = function(e) {
	if (e.button == 0) {
	if (focused && tree == focused && focused.parent) {
	focus(focused.parent);
	} else {
	focus(tree);
	}
	}
	e.stopPropagation();
	return true;
	};

	var caption = document.createElement('div');
	caption.className = 'webtreemap-caption';
	caption.innerHTML = tree.name;
	dom.appendChild(caption);

	tree.dom = dom;
	return dom;
	}

	function position(dom, x, y, width, height) {
	// CSS width/height does not include border.
	width -= kBorderWidth*2;
	height -= kBorderWidth*2;

	dom.style.left = x + 'px';
	dom.style.top = y + 'px';
	dom.style.width = Math.max(width, 0) + 'px';
	dom.style.height = Math.max(height, 0) + 'px';
	}

	// Given a list of rectangles \|nodes\|, the 1-d space available
	// \|space\|, and a starting rectangle index \|start\|, compute an span of
	// rectangles that optimizes a pleasant aspect ratio.
	//
	// Returns [end, sum], where end is one past the last rectangle and sum is the
	// 2-d sum of the rectangles' areas.
	function selectSpan(nodes, space, start) {
	// Add rectangle one by one, stopping when aspect ratios begin to go
	// bad. Result is [start,end) covering the best run for this span.
	// http://scholar.google.com/scholar?cluster=5972512107845615474
	var node = nodes[start];
	var rmin = node.data['$area']; // Smallest seen child so far.
	var rmax = rmin; // Largest child.
	var rsum = 0; // Sum of children in this span.
	var last_score = 0; // Best score yet found.
	for (var end = start; node = nodes[end]; ++end) {
	var size = node.data['$area'];
	if (size < rmin)
	rmin = size;
	if (size > rmax)
	rmax = size;
	rsum += size;

	// This formula is from the paper, but you can easily prove to
	// yourself it's taking the larger of the x/y aspect ratio or the
	// y/x aspect ratio. The additional magic fudge constant of 5
	// makes us prefer wider rectangles to taller ones.
	var score = Math.max(5spacespacermax / (rsumrsum),
	1rsumrsum / (spacespacermin));
	if (last_score && score > last_score) {
	rsum -= size; // Undo size addition from just above.
	break;
	}
	last_score = score;
	}
	return [end, rsum];
	}

	function layout(tree, level, width, height) {
	if (!('children' in tree))
	return;

	var total = tree.data['$area'];

	// XXX why do I need an extra -1/-2 here for width/height to look right?
	var x1 = 0, y1 = 0, x2 = width - 1, y2 = height - 2;
	x1 += kPadding; y1 += kPadding;
	x2 -= kPadding; y2 -= kPadding;
	y1 += 14; // XXX get first child height for caption spacing

	var pixels_to_units = Math.sqrt(total / ((x2 - x1) * (y2 - y1)));

	for (var start = 0, child; child = tree.children[start]; ++start) {
	if (x2 - x1 < 60 \|\| y2 - y1 < 40) {
	if (child.dom) {
	child.dom.style.zIndex = 0;
	position(child.dom, -2, -2, 0, 0);
	}
	continue;
	}

	// In theory we can dynamically decide whether to split in x or y based
	// on aspect ratio. In practice, changing split direction with this
	// layout doesn't look very good.
	// var ysplit = (y2 - y1) > (x2 - x1);
	var ysplit = true;

	var space; // Space available along layout axis.
	if (ysplit)
	space = (y2 - y1) * pixels_to_units;
	else
	space = (x2 - x1) * pixels_to_units;

	var span = selectSpan(tree.children, space, start);
	var end = span[0], rsum = span[1];

	// Now that we've selected a span, lay out rectangles [start,end) in our
	// available space.
	var x = x1, y = y1;
	for (var i = start; i < end; ++i) {
	child = tree.children[i];
	if (!child.dom) {
	child.parent = tree;
	child.dom = makeDom(child, level + 1);
	tree.dom.appendChild(child.dom);
	} else {
	child.dom.style.zIndex = 1;
	}
	var size = child.data['$area'];
	var frac = size / rsum;
	if (ysplit) {
	width = rsum / space;
	height = size / width;
	} else {
	height = rsum / space;
	width = size / height;
	}
	width /= pixels_to_units;
	height /= pixels_to_units;
	width = Math.round(width);
	height = Math.round(height);
	position(child.dom, x, y, width, height);
	if ('children' in child) {
	layout(child, level + 1, width, height);
	}
	if (ysplit)
	y += height;
	else
	x += width;
	}

	// Shrink our available space based on the amount we used.
	if (ysplit)
	x1 += Math.round((rsum / space) / pixels_to_units);
	else
	y1 += Math.round((rsum / space) / pixels_to_units);

	// end points one past where we ended, which is where we want to
	// begin the next iteration, but subtract one to balance the ++ in
	// the loop.
	start = end - 1;
	}
	}

	function appendTreemap(dom, data) {
	var style = getComputedStyle(dom, null);
	var width = parseInt(style.width);
	var height = parseInt(style.height);
	makeDom(data, 0);
	dom.appendChild(data.dom);
	position(data.dom, 0, 0, width, height);
	layout(data, 0, width, height);
	}